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

Java の String の hashCode() の 31 乗数の背後にある理由を詳しく調べる

Java の String 実装では、特定の式を使用してハッシュ コードを計算します。

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

ここで、s[i] は、文字列、n はその長さを表し、^ は累乗を表します。しかし、適切な疑問が生じます: なぜ乗数は 31 に設定されているのでしょうか?

この選択は、Joshua Bloch の有名な書籍「Effective Java, Second Edition」で概説されている原則に基づいています。ブロッホの理論的根拠は、乗数に関する 2 つの重要な基準を中心にしています。それは、比較的大きな素数であることです。

奇数素数乗数の利点

Bloch は、乗数を使用することを強調しています。 31 のような奇数の素数乗数を使用すると、乗算演算でオーバーフローによる情報損失が発生しないことが保証されます。乗数が偶数の場合、オーバーフローが発生する可能性があり、2 による乗算はシフトに似ているため、重要な情報が侵害される可能性があります。

プライム乗数の微妙な特典

素数乗数を選択する具体的な利点はあまり明らかではありませんが、慣例と一致しています。特に、31 にはユニークな属性があります。これにより、乗算をシフトと減算に効率的に置き換えることができ、パフォーマンスの向上につながります。この最適化は、多くの場合、最新の仮想マシン (VM) によって自動的に実行されます。

The Consensus

要約すると、Java は String の hashCode() メソッドの乗数として 31 を使用します。奇数の素数としてのステータスに由来します。この選択により、オーバーフローによる情報損失が防止され、乗算をシフトと減算に置き換えることによりパフォーマンスの向上が可能になります。

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