JAVA Hashmap内部实现 - 如果bin变得太大会怎样

Question

在内部,Hashmaps使用a hashfunction来查找bin查询key所属的内容.这些中的每一个bins本身就是一个LinkedList.

我不明白如果访问时间LinkedLists变得非常长,访问时间可以是恒定的,并且LinkedLists没有持续的访问时间,而是线性访问时间.

Collections即使垃圾箱由于某种原因而变得太大,Java 库如何设法保证持续的访问时间？内部发生了什么？Java在内部做了什么来减少这种负面影响？

Answer 1

每个bin中的平均元素数量由一个小常量绑定.通过保持箱的数量至少与条目总数乘以载荷因子(其默认值为0.75)一样高来维持这一点.

为了保持这种不变性,条目数随着条目数的增加而增加.

这是相关代码(Java 7):

void 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);
}

哪里size是条目的数量,table.length是仓的数量和threshold为table.length * loadFactor.

如果您使用默认加载因子0.75(或任何加载因子<1),则bin的数量将始终高于条目数,因此除非您的密钥类的hashCode非常糟糕,否则每个bin都不会平均有多个条目.