java HashMap如何确保使用键的hashcode计算的索引在可用范围内？

Question

我浏览了HashMap的源代码，有几个问题。PUT方法获取键和值，并执行以下操作

1. 密钥的哈希代码的哈希函数

2. 使用从上一步获得的散列计算该对的bucket位置

   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）三次，并假设这三个函数分别占用存储桶loc 7、8和9
• 调用put第4个K、V对，并发生以下情况
  • 使用键调用hash（）。hashcode（）和哈希值已计算
  • indexFor是基于哈希计算的

问题：

1. 如果第四个k，v的计算铲斗位置超出现有界限，该怎么办？说位置11

提前谢谢 阿克

Answer 1

让我们更详细地了解一下，hashmap将如何初始化存储桶大小

下面的代码来自HashMap。爪哇

while（i<；paramInt） 我<<；=1;

如果你通过了初始值10，那么上面的代码将用于生成幂2的大小。 所以使用上面的代码HashMap初始化bucket size 16

下面的代码用于计算桶指数

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

Answer 2

HashMaps通常会使用哈希代码来调整存储桶的数量。发生冲突时会发生什么取决于实现（不确定Java的HashMap）。有两种基本策略：保存一份落在桶里的物品清单，或者如果你的桶满了，就跳转到其他桶。我猜HashMap使用列表桶方法

Answer 3

对于你的第一个问题：地图的大小总是使用2的幂（如果你给它一个10的容量，它实际上会使用16），这意味着index & (length - 1)总是在范围内[0, length)，所以它总是在范围内

不清楚你的第二个和第三个问题与什么有关。除非需要，否则我不会重新分配一切