当达到阈值时，HashMap容量未增加

Question

在Java文档中，它说："当哈希表中的条目数超过装载因子和当前容量的乘积时，哈希表会被重新哈希。"。

下面是一个示例程序 -

HashMap<Integer, String> map = new HashMap<Integer, String>();
int i = 1;
while(i<16) {
    map.put(i, new Integer(i).toString());
    i++;
}

键的类型是整数，在插入第13到15个元素时，HashMap的容量仍为16，阈值仍为12，为什么？

在地图中添加第13个元素后的调试截图 -

args                 String[0] (id=16)
map HashMap<K,V> (id=19)
 entrySet   null
 hashSeed   0
 KeySet     null
 loadFactor 0.75
 modCount   13
 size       13
 table      HashMap$Entry<K,V>[16] (id=25)
 threshold  12
 values     null
i   14

[null, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 10=10, 11=11, 12=12, 13=13, null, null] 

使用String类型作为键的HashMap - HashMap<String, String> 或自定义类 - Map<Employee,Integer> 在第13个插入操作后表现如何。

- anmolmore

---

阅读代码，那会解释清楚。可能实现中的某些更改意味着javadoc不再完全正确。但这并不重要（依我看），因为没有明智的程序员会依赖于哈希表调整大小的精确行为。 - Stephen C

只是试图找出为什么将键设置为整数时实现行为不同。如果我尝试使用HashMap<String，String>，它会在第13个插入处调整映射大小。 - anmolmore

哪个Java版本（包括更新）？ - Random42

@m3th0dman Java 版本 - 1.7.0_67-b01 - anmolmore

Answer 1

看起来这种行为是由于Java 7版本的最近内部实现HashMap PUT方法的更改所致。经过查阅多个版本的源代码，我找到了我的问题的答案。

HashMap put方法调用addEntry()添加一个新条目 -

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

jdk7-b147 HashMap.addEntry 方法如下所示 -

addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

版本1.7.0_67-b01的源代码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

因此，在最近的Java版本中，HashMap可能不仅基于阈值而调整大小。如果桶为空，则条目仍将进入而不会调整HashMap的大小。

Java 8可能具有不同的行为，版本8-b132的源代码显示PUT已完全重新实现 -

put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    ....
}

final Node<K,V>[] resize() {
     //many levels of checks before resizing   
}

Java文档可能没有Java版本那么频繁地更新！感谢Stephen。

- anmolmore