536

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

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

は文字列の i番目の文字、 は文字列の長さで、累乗を示しintます。s[i]n^

乗数として 31 が使用されるのはなぜですか?

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

4

13 に答える 13

443

Joshua Bloch の「Effective Java」(十分に推奨できない本であり、stackoverflow に関する継続的な言及のおかげで購入した本) によると:

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

(第 3 章、項目 9: equals をオーバーライドするときは常にハッシュコードをオーバーライドする、48 ページから)

于 2008-11-18T18:53:24.447 に答える
86

Goodrich と Tamassia は、定数 31、33、37、39、および 41 を使用すると、50,000 を超える英語の単語 (Unix の 2 つのバリアントで提供される単語リストの和集合として形成される) から計算して、それぞれの場合で 7 回未満の衝突を生成します。これが、非常に多くの Java 実装がそのような定数を選択する理由かもしれません。

Data Structures and Algorithms in Javaのセクション 9.2 Hash Tables (page 522) を参照してください。

于 2008-11-18T20:56:28.757 に答える
59

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

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

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

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

于 2008-11-18T17:01:45.563 に答える
38

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

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

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

于 2009-05-19T18:10:57.263 に答える
33

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

残りの 4 つのうち、おそらく P(31) を選択します。これは、RISC マシンで計算するのが最も安価であるためです (31 は 2 の 2 乗の差であるため)。P(33) も同様に計算が簡単ですが、パフォーマンスはわずかに悪く、33 は合成であるため、少し神経質になります。

したがって、ここでの回答の多くが暗示しているように思われるほど、その推論は合理的ではありませんでした。しかし、私たちは直感的な決定の後に合理的な理由を考え出すのが得意です (そして、Bloch でさえその傾向があるかもしれません)。

于 2016-02-10T00:46:26.533 に答える
23

実際、37 はかなりうまく機能します。z := 37 * x は として計算できますy := x + 8 * x; z := x + 4 * y。どちらのステップも 1 つの LEA x86 命令に対応するため、これは非常に高速です。

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

(31 の代わりに) 73 または 37 を使用する方がよい場合があります。これは、より高密度のコードにつながるためです。ここで使用されている 3 引数の LEA 命令は、Intel の Sandy ブリッジ アーキテクチャでは遅くなり、レイテンシが 3 サイクル増加しました。

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

于 2011-07-27T19:37:44.703 に答える
19

Neil Coffeyは、なぜ 31 が使用されるのかについて説明しています。

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

于 2011-12-07T15:27:18.477 に答える
14

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

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

1) Merriam-Webster の 2nd Int'l Unabridged Dictionary (311,141 文字列、平均長 10 文字) にエントリがあるすべての単語とフレーズ。

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

3) 昨夜数時間実行された Web クローラーによって収集された URL のリスト (28,372 文字列、平均長さ 49 文字)。

表に示されているパフォーマンス メトリックは、ハッシュ テーブル内のすべての要素の「平均チェーン サイズ」です (つまり、要素を検索するために比較されるキーの数の期待値)。

                          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 つの壊れたバージョンを除くすべての関数が優れた、ほとんど見分けがつかないパフォーマンスを提供することが明らかです。このパフォーマンスは本質的に「理論上の理想」であると強く推測します。これは、ハッシュ関数の代わりに真の乱数ジェネレーターを使用した場合に得られるものです。

WAIS 関数の仕様には乱数のページが含まれており、そのパフォーマンスははるかに単純な関数のどれよりも優れていないため、WAIS 関数を除外します。残りの 6 つの関数はどれも優れた選択肢のように思えますが、1 つを選択する必要があります。Vo のバリアントと Weinberger の関数は、マイナーではありますが、複雑さが増しているため、除外すると思います。残りの 4 つのうち、おそらく P(31) を選択します。これは、RISC マシンで計算するのが最も安価であるためです (31 は 2 の 2 乗の差であるため)。P(33) も同様に計算が簡単ですが、パフォーマンスはわずかに悪く、33 は合成であるため、少し神経質になります。

ジョシュ

于 2017-06-12T21:17:03.210 に答える
5

Bloch はこれについて詳しく説明していませんが、私が常に聞いたり信じたりしてきた理論的根拠は、これが基本的な代数だということです。ハッシュは、乗算と剰余演算に要約されます。つまり、できることなら、共通の因数を持つ数値を使用したくないということです。言い換えれば、互いに素な数は、答えの均等な分布を提供します。

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

  • 入れたデータ型のモジュラス (2^32 または 2^64)
  • ハッシュテーブルのバケット数のモジュラス (さまざまです。Java では素数でしたが、現在は 2^n です)
  • ミキシング関数でマジックナンバーを乗算またはシフトします
  • 入力値

実際に制御できるのはこれらの値の 2 つだけなので、少し注意が必要です。

于 2010-04-28T22:39:13.817 に答える
3

よくわかりませんが、素数のサンプルをテストしたところ、31が可能な文字列のサンプル全体で最良の分布を示していることがわかりました。

于 2008-11-18T16:58:03.683 に答える
1

ハッシュ関数からの大きな期待はhash(x) % N、N が任意の数 (および多くの場合、2 の累乗) であるような操作を行っても、その結果の一様ランダム性が存続することです。その理由の 1 つは、そのような操作が、スロットを決定するためのハッシュ テーブルで一般的に使用されることです。 . ハッシュを計算するときに素数の乗数を使用すると、乗数と N が除数を共有する確率が低下し、演算の結果が均一にランダムでなくなります。

他の人は、31 による乗算が乗算と減算によって実行できるという優れた特性を指摘しています。そのような素数を表す数学用語があることを指摘したいだけです: Mersenne Prime

すべてのメルセンヌ素数は 2 のべき乗よりも 1 小さいため、次のように記述できます。

p = 2^n - 1

x に p を掛ける:

x * p = x * (2^n - 1) = x * 2^n - x = (x << n) - x

シフト (SAL/SHL) と減算 (SUB) は、通常、多くのマシンで乗算 (MUL) よりも高速です。Agner Fog の指示表を参照してください

そのため、GCC はメルセンヌ素数による乗算をシフトとサブに置き換えることで最適化しているようです。こちらを参照してください。

しかし、私の意見では、このような小さな素数はハッシュ関数には適していません。比較的優れたハッシュ関数を使用すると、ハッシュの上位ビットでランダム性が期待できます。ただし、Java ハッシュ関数では、短い文字列では上位ビットでランダム性がほとんどありません (下位ビットでのランダム性は依然として非常に疑わしいものです)。これにより、効率的なハッシュ テーブルを構築することがより困難になります。Java ハッシュ関数ではできなかったこの素晴らしいトリックをご覧ください。

一部の回答では、31 が 1 バイトに収まるのは良いことだと信じていると述べています。これは実際には役に立たない:

(1) 乗算の代わりにシフトを実行するため、乗数のサイズは関係ありません。

(2) 私の知る限り、8 バイト値を 1 バイト値で乗算する特定の x86 命令はありません。hereを参照してください。64ビットレジスタ全体を乗算します。

(実際、127 は 1 バイトに収まる最大のメルセンヌ素数です。)

値が小さいほど、中下位ビットのランダム性が高くなりますか? たぶん、しかしそれはまた、衝突の可能性を大幅に増加させるようです:)。

さまざまな問題を挙げることができますが、一般的には、混乱と拡散という 2 つの主要な原則がうまく満たされていないことに要約されます。

しかし、それは速いですか？あまり効果がないからでしょうね。ただし、ここでパフォーマンスが本当に重要な場合、ループごとに 1 文字では非常に非効率的です。このように、長い文字列のループ反復ごとに一度に 4 文字 (8 バイト) を実行しないのはなぜですか? まあ、それは、すべての文字を個別に乗算する必要がある現在のハッシュの定義では難しいでしょう (これを解決するためのちょっとしたハックがあれば教えてください:D)。

于 2020-06-23T23:54:38.877 に答える