JavaのStringのhashCode（）が乗数として31を使用するのはなぜですか？

StackOverflow https://stackoverflow.com/questions/299304

  •  08-07-2019
  •  | 
  •  

質問

Javaのドキュメントごとに、 Stringオブジェクトのハッシュコードは次のように計算されます：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     

int算術を使用します。s[i]は    文字列の i 番目の文字、nは    文字列。^はべき乗を示します。

乗数として31が使用される理由

乗数は比較的大きな素数でなければならないことを理解しています。では、なぜ29、37、または97でもないのですか？

役に立ちましたか？

解決

Joshua Blochの効果的なJava （ stackoverflowに関する継続的な言及のおかげで十分に推奨され、私が購入した）：

  

奇数の素数であるため、値31が選択されました。偶数で乗算がオーバーフローした場合、2による乗算はシフトに相当するため、情報は失われます。プライムを使用する利点はそれほど明確ではありませんが、伝統的です。 31の優れた特性は、乗算をシフトと減算で置き換えてパフォーマンスを向上できることです：31 * i == (i << 5) - i。最新のVMは、この種の最適化を自動的に実行します。

（第3章、項目9：「等しい」をオーバーライドするときは常にハッシュコードをオーバーライドする、48ページ）

他のヒント

Goodrich and Tamassia が指摘しているように、50,000語以上の英単語を使用する場合（結合として形成されるUnixの2つのバリエーションで提供されている単語リストの）、定数31、33、37、39、および41を使用すると、各ケースで7回未満の衝突が発生します。これを知っていれば、多くのJava実装がこれらの定数のいずれかを選択しても驚くことではありません。

偶然にも、私は<！> quot;多項式ハッシュコード<！> quot;セクションを読んでいた最中です。この質問を見たとき。

編集：ここでは、上記で参照している〜10mb PDFブックへのリンクを示します。 Javaのデータ構造とアルゴリズム

（ほとんど）古いプロセッサでは、31を掛けると比較的安価になります。たとえば、ARMでは、1つの命令のみです。

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

他のほとんどのプロセッサでは、個別のシフトおよび減算命令が必要です。ただし、乗数が遅い場合、これはまだ勝ちです。最近のプロセッサは高速な乗算器を使用する傾向があるため、32が正しい側である限り、大きな違いはありません。

これは優れたハッシュアルゴリズムではありませんが、1.0コードよりも十分に優れています（1.0仕様よりもはるかに優れています！）。

乗算により、ビットは左にシフトされます。これにより、利用可能なハッシュコードのスペースがより多く使用され、衝突が減少します。

2のべき乗を使用しないことで、下位の右端のビットにもデータが入力され、ハッシュに入力される次のデータと混合されます。

式n * 31は(n << 5) - nと同等です。

<！> quot; Comments <！> quot;でBlochの元の推論を読むことができます。 http://bugs.java.com/bugdatabase/view_bug.do?bug_id = 4045622 。彼は、結果の<！> quot;平均チェーンサイズ<！> quot;に関して、異なるハッシュ関数のパフォーマンスを調査しました。ハッシュテーブル。 P(31)は、彼がK <！> amp; Rの本で見つけた当時の一般的な機能の1つでした（しかし、KernighanとRitchieでさえ、どこから来たのか覚えていませんでした）。最終的に彼は基本的に1つを選択しなければならなかったので、十分に機能しているように見えたのでP(33)を取りました。 <=>はそれほど悪くなく、33による乗算も同様に高速に計算できますが（5によるシフトと加算）、33は素数ではないため31を選択しました：

  

残りの   4、RISCで計算するのが最も安いので、おそらくP（31）を選択します。   マシン（31は2の2のべき乗の差であるため）。 P（33）は   同様に計算は安価ですが、パフォーマンスはわずかに劣ります。   33は合成なので、少し緊張します。

したがって、ここでの答えの多くが暗示しているように、推論は合理的ではありませんでした。しかし、私たちはすべて、腸の決定の後に合理的な理由を考え出すのに優れています（そしてブロッホでさえその傾向があるかもしれません）。

実際には、37個で十分です。 z：= 37 * xはy := x + 8 * x; z := x + 4 * yとして計算できます。両方のステップは1つのLEA x86命令に対応しているため、これは非常に高速です。

実際、偶数のより大きい素数 73 との乗算は、y := x + 8 * x; z := x + 8 * yを設定することで同じ速度で実行できます。

73または37（31ではなく）を使用すると、デンサーコードにつながるため、より適切な場合があります。2つのLEA命令は、6バイトしかかかりません。ここで使用される3引数LEA命令は、IntelのSandyブリッジアーキテクチャ上で遅くなり、レイテンシが3サイクル増加しました。

さらに、 73 はシェルドンクーパーのお気に入りの番号です。

Neil Coffey 説明 31バイアス。

基本的に31を使用すると、ハッシュ関数のセットビット確率分布がより均一になります。

JDK-4045622 から、Joshua Blochが理由を説明しています特定の（新しい）String.hashCode()実装が選択された理由

  

以下の表は、さまざまなハッシュのパフォーマンスをまとめたものです   上記の関数、3つのデータセット：

     

1）Merriam-Websterのエントリを持つすべての単語とフレーズ          第2の国際要約辞書（文字列311,141、平均長10文字）。

     

2）/ bin / 、/ usr / bin / 、/ usr / lib / 、/ usr / ucb / 内のすべての文字列          および/ usr / openwin / bin / *（66,304文字列、平均21文字）。

     

3）Webクローラーによって収集されたURLのリストは、複数の          昨夜（28,372文字列、平均49文字）。

     

表に示されているパフォーマンスメトリックは、<！> quot;平均チェーンサイズ<！> quotです。   ハッシュテーブル内のすべての要素（つまり、   要素を検索するために比較するキーの数）。

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439
     

この表を見ると、以下を除くすべての機能が明らかになっています。   現在のJava関数とWeinbergerの2つの壊れたバージョン   関数は、優れた、ほとんど区別できないパフォーマンスを提供します。私   このパフォーマンスは本質的に   <！> quot;理論上の理想<！> quot ;、これは真のランダムを使用した場合に得られるものです   ハッシュ関数の代わりに番号ジェネレーター。

     

その仕様には乱数のページが含まれているため、WAIS関数を除外します。そのパフォーマンスは、   はるかに単純な関数。残りの6つの機能のいずれかは   優れた選択肢ですが、1つを選択する必要があります。私は除外するだろうと思う   VoのバリアントとWeinbergerの機能が追加されたため   複雑ではありますが、マイナーです。残りの4つのうち、おそらく選択します   P（31）、RISCマシンで計算するのが最も安いため（31   2の2のべき乗の差です）。 P（33）は同様に安価です   計算しますが、パフォーマンスはわずかに悪く、33は   コンポジット。少し緊張します。

     

ジョシュ

確信はありませんが、素数のサンプルをテストしたところ、31が可能なストリングのサンプル全体で最良の分布を示したことがわかりました。

Blochはこれにはあまり触れませんが、私がこれまで聞いていた/信じていた理論的根拠は、これが基本代数であるということです。ハッシュは、乗算とモジュラス演算に要約されます。つまり、共通の要因を持つ数値を使用することはできますが、それを使用したくないということです。言い換えれば、比較的素数は答えの均等な分布を提供します。

ハッシュを使用して構成する数値は通常次のとおりです。

  • 挿入するデータ型のモジュラス （2 ^ 32または2 ^ 64）
  • ハッシュテーブル内のバケットカウントのモジュラス（さまざま。javaではかつて素数でしたが、現在は2 ^ n）
  • ミキシング関数でマジックナンバーを乗算またはシフトします
  • 入力値

実際には、これらの値のいくつかを制御するだけなので、もう少し注意が必要です。

JDKの最新バージョンでは、まだ31が使用されています。 https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#hashCode（）

ハッシュ文字列の目的は

  • 一意（ハッシュコード計算ドキュメントの演算子^を参照してください。一意になります）
  • 計算の低コスト

31は、8ビット（= 1バイト）のレジスタに入れることができる最大値です。 1バイトのレジスタに入れることができる最大の素数、奇数です。

乗算31は<！> lt; <！> lt; 5で、それ自体を減算するため、安価なリソースが必要です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top