java - Java での HashMap の実装。バケット インデックスの計算はどのように機能しますか?

Question

私はHashMapJavaでの実装を検討していますが、ある時点で立ち往生しています。
関数はどのようにindexFor計算されますか?

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

ありがとう

Answer 1

The hash itself is calculated by the hashCode() method of the object you're trying to store.

What you see here is calculating the "bucket" to store the object based on the hash h. Ideally, to evade collisions, you would have the same number of buckets as is the maximum achievable value of h - but that could be too memory demanding. Therefore, you usually have a lower number of buckets with a danger of collisions.

If h is, say, 1000, but you only have 512 buckets in your underlying array, you need to know where to put the object. Usually, a mod operation on h would be enough, but that's too slow. Given the internal property of HashMap that the underlying array always has number of buckets equal to 2^n, the Sun's engineers could use the idea of h & (length-1), it does a bitwise AND with a number consisting of all 1's, practically reading only the n lowest bits of the hash (which is the same as doing h mod 2^n, only much faster).

Example:

     hash h: 11 1110 1000  -- (1000 in decimal)
   length l: 10 0000 0000  -- ( 512 in decimal)
      (l-1): 01 1111 1111  -- ( 511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000  -- ( 488 in decimal which is a result of 1000 mod 512)

Answer 2

hashを計算するのではなく、 bucketを計算します。

この式は、ビットマスクのような を使用h & (length-1)してビットごとANDに処理を行い、 の下位ビットのみを返すため、 の超高速バリアントが作成されます。hlength-1hh % length

Answer 3

エントリ (キーと値のペア) が格納されるハッシュ マップのバケットを計算しています。バケット ID はhashvalue/buckets lengthです。

ハッシュ マップはバケットで構成されます。オブジェクトは、バケット ID に基づいてこれらのバケットに配置されます。

オブジェクトの値に基づいて、実際には任意の数のオブジェクトが同じバケットに分類される可能性がありhash code / buckets lengthます。これを「衝突」と呼びます。

多くのオブジェクトが同じバケットに分類される場合、検索中に equals() メソッドが呼び出されて曖昧さが解消されます。

衝突の数は、バケットの長さに間接的に比例します。