JAVA Hashmap 内部实现 - 如果 bin 变得太大怎么办

Question

在内部，Hashmaps 使用 hashfunction 查找查询的 key 所属的 bin。每个 bins 本身就是一个 LinkedList.

我不明白如果这些 LinkedLists 可能会变得很长，访问时间怎么会是恒定的，并且 LinkedLists 没有恒定的访问时间，而是线性访问时间。

Java Collections 图书馆如何设法保证恒定的访问时间，即使 bin 由于某种原因变得太大了？内部发生了什么？ Java 在内部做了什么来最大限度地减少这种负面影响？

Answer 1

每个 bin 中元素的平均数量受一个小常数的限制。这是通过保持 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 是 bin 数，threshold 是 table.length * loadFactor。

如果您使用默认的加载因子 0.75（或任何小于 1 的加载因子），bin 的数量将始终高于条目的数量，所以除非您的键的 hashCode 非常糟糕 class, 每个 bin 平均不会超过一个条目。

Answer 2

documentation tells you，如果负载因子太高会发生什么：

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

此外，您可以查看源代码，其中包含implementation notes的列表。最重要的是：

This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap.

进一步：

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins.

简而言之：

当单个 bin 变得太大时，它们的元素会转换为树节点，并且您将使用 t bin 的大小进行 O(ln(t)) 搜索。所以 large bins 有一个二叉树悬挂在它们上面。
当整个地图的负载因子变高时，箱子的数量加倍，整个地图重新散列（这仍然可能导致一些箱子再次成为树箱）。

Answer 3

如果散列 table 太满，则需要重新散列。为了重新散列 table，将创建另一个具有更多桶的 table，并将所有元素插入到新的 table 中。原来的table被舍弃

负载因子决定何时重新哈希。默认值为 0.75，因此当 table 超过 75% 满时，它会自动重新散列两倍的桶。

为了在 table 中找到一个位置，计算散列码并以桶数为模进行缩减。这个想法是散列函数应该随机分布对象，所以冲突的次数应该很少，所以不应该有太多的比较。

Answer 4

I don't understand how access time can be constant if these linked lists could get very long

HashMap 不提供有保证的恒定访问时间。它提供 摊销常数 时间，这是另一回事：n 项的总体访问平均为 O(1)，但每个单独的访问可能为 O(n ).

此外，摊销常数时间只有在散列函数为"good"时才能实现。当散列函数不好时（例如，返回一个常量，这是一个有效但非常糟糕的散列函数）库是无能为力的：访问时间将是线性的，无论实现试图做什么。

当多个哈希码相同时，链表将以桶数为模增长。但是，由于HashMap的桶计数选择素数，所以链表变长的最常见情况是许多哈希码实际上是相同的，而不考虑模数。因此，简单地将桶的数量增加到更大的素数不会减少列表的长度：它会将列表移动到不同的桶，或者将其留在原来的位置，但列表的长度不会减少。

JAVA Hashmap 内部实现 - 如果 bin 变得太大怎么办

JAVA Hashmap internal implementation - what if bins get too large

java

hashmap

data-structures