java - 在 HashMap 中，为什么阈值(调整大小的下一个大小值)是容量 * 负载因子。为什么不等于 map 的大小或容量

Question

在 HashMap 中，为什么阈值(调整大小的下一个大小值)是容量 * 负载 因子。为什么不等于大小 或 map 的容量。

例如，初始默认容量 = 16，负载因子 = 0.75，因此 threshold = (capacity * load factor) = (16 * 0.75) = 12。

当我们添加第 13 个元素时 map 调整大小为什么会这样，为什么 map 的作者决定保留它 capacity * load factor(即 12)？为什么与容量(即 16)不同。

为什么不保持阈值等于容量，以便仅在 hashmap 已满时才进行重新散列？

Answer 1

Javadoc，Javadoc，Javadoc。那是你首先看的地方。在 HashMap 上它说:

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

根据 HashMap 的理论 - 如果您的映射已满，那么您正在做一些非常非常错误的事情。到那时，您可能会在 O(sqrt(N)) 上查找随机数据 - BAD。您从不希望您的 HashMap 已满。但是非常稀疏的 map 会浪费太多空间(正如您所指出的)，并且迭代时间会太长。因此，应该有一个负载因子，在大多数用例中小于 1。

注意:“浪费的空间”与 map 大小成正比，与加载因子成反比。然而，查找时间具有更复杂的预期性能函数。这意味着相同的负载因子不适用于不同大小的 HashMap - 因为这将意味着不同的规模权衡。

---

可以在 Knuth“The Art of Computer Programming”第 3 卷中找到权衡的一般概述。