なぜ Java の「String.hashCode()」は乗数として 31 を使用するのでしょうか?

String の Java の hashCode() が乗数として 31 を使用する理由

Java では、String オブジェクトの hashCode() メソッドは次を使用します。式:

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

ここで、s[i] はi 番目の文字、n は文字列の長さ、^ は累乗を表します。ここで疑問が生じます: なぜ 31 が乗数として特に選ばれるのでしょうか?

素数乗数の理論的根拠

ドキュメントでは、比較的大きな素数を乗数として使用することを推奨しています。ハッシュテーブル内の衝突を最小限に抑えます。異なるオブジェクトが同じハッシュ コードを生成すると衝突が発生し、パフォーマンスの問題が発生する可能性があります。素数はハッシュ コードの分散を改善し、衝突の可能性を減らします。

なぜ他の素数ではないのですか?

他の素数の中から 31 を選択したのは、2 つの素数によるものと考えられます。要因:

1. オーバーフロー防止:乗数が偶数で乗算がオーバーフローすると、情報が失われます。これは、2 の乗算がシフト演算と同等であるためです。
2. パフォーマンスの最適化: 値 31 により、乗算をシフトと減算で置き換えることができる最適化が可能になります: 31 * i = = (i

したがって、31 は、Java で String オブジェクトの効率的なハッシュ操作を可能にしながら、衝突を防ぐ素数であるという両方の基準を満たします。

以上がなぜ Java の「String.hashCode()」は乗数として 31 を使用するのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。