5

我浏览了 HashMap 的源代码并有几个问题。PUT 方法采用 Key 和 Value 并执行

  1. 键的哈希码的哈希函数。

  2. 使用从上一步获得的哈希计算该对的存储桶位置

    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 的 HashMap。
  • 调用 put(k,v) 三次并假设这 3 个占用桶 loc 7 ,8 和 9
  • 看涨看跌第 4 对 K,V 对并发生以下情况
    • 使用 key.hashcode() 调用 hash() 并计算哈希值
    • indexFor是根据hash计算的

问题：

  1. 如果计算的第 4 个 k,v 的存储桶位置超出现有范围怎么办？说位置 11？

提前感谢阿赫

4

3 回答 3

2

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

目前尚不清楚您的第二个和第三个问题与什么有关。我认为 HashMap除非需要，否则不会重新分配所有内容。

于 2012-09-25T18:21:17.203 回答
1

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

于 2012-09-25T18:21:41.913 回答
0

让我们更详细地说，hashmap 将如何初始化存储桶大小？

以下代码来自 HashMap.java

而 (i < paramInt) i <<= 1;

如果您传递初始 10，则上面的代码用于制作大小为 2 的幂。因此使用上面的代码 HashMap 初始化桶大小 16；

下面的代码用于计算桶索引，

static int indexFor(int h, int length) {
        return h & (length - 1);
    }
于 2017-10-10T09:55:42.823 回答