Java の String hashCode() が乗数として 31 を使用するのはなぜですか?

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

Java では、String オブジェクトのハッシュ コードは、式:

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

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

素数乗数の重要性

この式の重要な側面の 1 つは、次の用途です。素数を使用すると、ハッシュ衝突の可能性が減るという利点があります。素数以外の乗数が使用された場合、同じハッシュ値を持つ 2 つの文字列が共通の因数を共有する可能性があり、ハッシュの衝突が発生しやすくなります。

Why Not Another Prime Number?

31 は奇数の素数ですが、29、37、97 など、他の素数も選択できます。

• オーバーフローの回避: 31 は比較的小さい素数であるため、乗算プロセス中の整数オーバーフローのリスクが軽減されます。偶数素数が使用されている場合、2 を乗算するときにオーバーフローが発生し、情報が失われる可能性があります。
• パフォーマンスの最適化: Joshua Bloch が「Effective Java」で述べているように、31 を乗算すると、より効率的なシフトアンド減算演算: 31 * i == (i
• 伝統: ハッシュ関数に素数乗算器を使用することは長年行われており、31 が特によく選ばれています。 31 が特に選ばれた決定的な理由はありませんが、多くのプログラミング言語やアプリケーションで標準的な選択肢となっています。

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