Java Hashmap 中的容量和 indexFor

Question

在查看Java HashMap的源代码时，我们可以看到一个键的第一个桶是用下面的方法确定的：

 static int indexFor(int h, int length) { //h = hash of key 
     return h & (length-1);               //length = capacity of array at 
 }                                        //         current time

根据我的理解，如果初始大小是 16 (length-1 = 15 = 1111) 并且如果密钥 k1 的生成散列是 108378 (1 10100111 01011010 ），然后 indexFor() 方法将 return 10 (1010)。

现在，假设经过一些添加后容量已更改为 32。现在，如果我想搜索键 k1（哈希值为 108378），它将再次使用相同的 indexFor() 方法检查存储桶。现在 h & (length-1) 代码片段将 return 26。 (108378 & 31).

我的问题是，如果 table 调整大小，此 get 方法将如何找到正确的存储桶？

Answer 1

如果 table 调整了大小，则长度参数将改变并且 indexFor 方法将 return 一个不同的值。当 table 调整大小时，当前在 table 中的值必须移动到新的 table 中，因此将为每个值计算一个新索引。

Answer 2

当达到负载因子的最大阈值时，会发生称为 Rehashing 的过程，所有元素都会移动到新的 table。

When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations.

Answer 3

您看到的 length 不是 map.size() 报告的值。它是一个内部长度，表示散列的大小 table。该长度在人口稠密的哈希映射中可以小于 size()，也可以在人口稀疏的哈希映射中大于 size()。它越小，就会发现越多的键对 h & (length-1) 具有相同的评估，这意味着更多的键将被分组到桶中。

在某个时间点（希望尽可能少）地图决定 length 太小，导致太多的碰撞，（每个桶中的键太多，）所以它重组映射，将散列table 重新分配到更大的大小，重新计算所有散列值，并重新分配存储桶中的键，以便h & (length-1) 对于所有散列值仍然正确。

Java Hashmap 中的容量和 indexFor

Capacity and indexFor in Java Hashmap

java

hash

hashtable

hashmap