6

重複の可能性:
Java の hashCode() in String が乗数として 31 を使用するのはなぜですか?
hashCode で素数を使用する理由

有効な Java 項目 9から: equals をオーバーライドするときは、常に hashCode をオーバーライドする オブジェクト クラスで定義された hashcode() をオーバーライドする次の関連コード スニペットを検討してください。

public final class PhoneNumber {
  private final short areaCode;
  private final short prefix;
  private final short lineNumber;
  ......//Rest ignored on purpose
  .....

private volatile int hashCode; // (See Item 71)
@Override public int hashCode() {
   int result = hashCode;
   if (result == 0) {
    result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    hashCode = result;
   }
 return result;
 }
}

ゼロ以外の初期値「17」が選択される理由がわかりました。また、フィールドの順序が計算において重要な役割を果たすように、各ステップで乗算が行われることも理解していhashcode()ます。しかし、乗算の値として 31 を選択する理由がわかりません。誰かが私に理由を説明できますか? これは Bloch が 31 について言わなければならないことですが、私にはよくわかりません。以下のイタリック体の行を特に理解できません。

奇素数であるため、値 31 が選択されました。偶数で乗算がオーバーフローした場合、2 による乗算はシフトと同等であるため、情報が失われます。素数を使用する利点はあまり明確ではありませんが、伝統的なものです。

4

3 に答える 3

11

左にシフトすると、右側にゼロが導入され、数値のバイナリ表現の左側が少し失われるため、明らかに情報が失われます。このプロセスを繰り返すと、以前の計算で蓄積されたすべての情報が徐々に失われます。つまり、ハッシュコード計算に入力するフィールドが多いほど、初期のフィールドの最終結果への影響が少なくなります。

于 2012-07-18T08:20:13.983 に答える
3

素数を使用する理由は、ランダムなパターンを生成する可能性が高いためです。たとえば 9 を使用すると、3 の倍数でオーバーラップできます。

AFAIK31は文字列に使用されます。アルファベットは 31 文字未満であるため、最大 6 文字のすべての単語に一意のハッシュ コードがあることを意味します。たとえば、61 (64 未満の素数) を使用すると、最大 5 文字で一意のコードが生成され、13 (16 未満の素数) を使用すると、2 文字の単語と衝突する可能性があります。

于 2012-07-18T08:26:41.123 に答える
1

別の数字の答えを説明しますが、理由は似ているのではないかと思います。文字 X のハッシュ値への寄与は X*B^k です。この場合、B は 31 であり、k は文字列内の X の位置とその長さに依存します。この算術演算は通常、ワード サイズを法として行われます。このため、k の値が異なると B^k が異なるようにする必要があります。

現在、Gonnet と Baeza-Yates による「Handbook of Algorithms and Data Structures」セクション 3.3.1「Pratical hashing functions」では、「B^i は最大サイクル mod 2 であるため、この関数には値 B=131 が推奨されます。 8 <= k <= 64 の場合は ^k。" mod 2^32 の周期の長さ 31 は何ですか? 31 は Sparc の即値オペランドに適合すると思いますが、131 は適合しません。

于 2012-07-18T17:51:17.737 に答える