7

Java doc说-当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表被重新哈希

在下面的程序中 -

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

Key 是Integer类型，在插入第 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 次插入时显示预期行为

4

1 回答 1

5

看起来这种行为是由于最近版本的 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 版本！谢谢斯蒂芬

于 2014-11-14T10:33:04.650 回答