java - ハッシュマップのindexFor?

Question

コードを見て、の仕組みを理解しようとしているだけJava HashMapです。要素が追加されると、次のことが起こります。

1. キーのハッシュコードを取得
2. 結果にハッシュ関数が適用されます
3. メソッド indexFor が 2 の結果に適用されます。これにより、適切なバケットの最初のエントリが得られます。次に、バケット内のリンクされたリストが繰り返されます - 最後が見つかり、要素が追加されます。

indexO fの実装は次のとおりです。

int indexOf(int h, int length) {
     return h & (length-1);
}

indexOf メソッドで行われているトリックがわかりません。誰でも説明できますか？

ありがとう。

Answer 1

これが機能するのは、JavaHashMapsが常に容量、つまりバケットの数を 2 の累乗として持っているためです。256 の容量、つまり 0x100 で作業してみましょう。しかし、2 の任意の累乗でも機能します。ビットごとに必要な正確なビット マスクと、適切なバケット インデックスを取得するための0ハッシュlength - 1。

256 - 1 = 255
0x100 - 0x1 = 0xFF

たとえば、257 (0x101) のハッシュは 0xFF とビットごとに論理積され、バケット番号 1 が生成されます。