HashMap如何确保使用密钥的哈希码计算的索引在可用范围内？

Question

我浏览了HashMap的源代码，并提出了一些问题。PUT 方法采用键和值并执行

>

密钥哈希码的哈希函数。

使用从上一步获得的哈希计算这对的桶位置

public V put(K key, V value) {
   int hash = hash(key.hashCode());
   int i = indexFor(hash, table.length);
   .....
}


static int hash(int h) {
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}


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

例：

• 创建大小为 10 的哈希映射。
• 调用 put（k，v） 三次，并假设这 3 个占用存储桶 loc 7、8 和 9
• 调用 put 第 4 个 K，V 对，并且发生以下
  • hash（） 使用 key.hashcode（） 和 hash 计算来调用
  • indexFor 是根据哈希计算的

  问题:

  1. 如果第4个k， v的计算桶位置超出现有边界怎么办？比如位置11？

  提前谢谢，Akh

Answer 1

让我们更详细地讨论，hashmap如何初始化bucket大小？

以下代码来自HashMap.java

而（i

如果您通过初始10，则上述代码用于使功率大小为2。因此使用上述代码HashMap初始化存储桶大小16；

以下代码用于计算存储桶索引，

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

Answer 2

哈希地图通常会使用哈希代码来修改存储桶的数量。发生冲突时会发生什么取决于实现（不确定Java的哈希图）。有两种基本策略：保留落在存储桶中的项目列表，或者如果您的存储桶已满，则向前跳到其他存储桶。我的猜测是哈希地图使用列表存储桶方法。

Answer 3

对于你的第一个问题：地图总是使用2的幂作为大小（如果你给它一个容量10，它实际上将使用16），这意味着索引

不清楚你的第二个和第三个问题与什么有关。我不认为＜code＞HashMap＜code＞会重新分配一切，除非需要。