Java HashMap调整大小的时间复杂度

Question

我想知道当负载因子超过阈值时，Java HashMap 扩容的时间复杂度是多少？据我了解，HashMap 的表格大小始终是2的幂次方（即偶数），因此无论何时我们调整表格大小，我们不必重新哈希所有的键（如果我理解有误，请纠正我），我们只需要分配额外的空间并将所有条目从旧表格复制到新表格（我不太确定JVM在内部如何处理这个问题），对吗？而对于Hashtable，由于它使用质数作为表格大小，因此每当我们调整表格大小时，我们需要重新哈希所有的条目。那么我的问题是，在HashMap上调整大小仍然需要O(n)线性时间吗？

- peter

---

你可以随时学习HashMap的源代码。 :) - Ted Hopp

Answer 1

调整一个HashMap的大小仍需要 O(N) 的时间成本。

因此，导致resize的插入操作将花费 O(N) 的时间。但这只会发生在所有插入操作中的 O(1/N) 次，所以（在某些假设下）平均插入时间为 O(1)。

负载因子的选择会影响性能，但不会影响复杂度。

如果我们对哈希函数和键聚类进行正常假设，那么当负载因子更大时：

- 平均哈希链长度更长，但仍为 O(1)； - 重新调整大小的频率减少，但仍为 O(1/N)； - 调整大小的成本保持不变，并且复杂度仍为 O(N)。

实际上，每当调整哈希表的大小时，您都需要重新计算所有键的哈希值。当您将哈希表大小加倍时，需要拆分哈希链。为此，您需要测试每个键的哈希值映射到两个链表中的哪一个。（事实上，如果哈希表具有开放式组织，则需要执行相同的操作。）

但是，在当前一代HashMap实现中，哈希码值被缓存在链接条目对象中，因此不需要重新计算键的哈希码。

还有一种特殊情况，即所有键都散列到相同的哈希码。这可能是由于糟糕的哈希函数设计或键的分布不均匀导致的。 这会影响查找、插入和其他操作的性能，但不会影响重新调整大小的成本或频率。

- Stephen C

---

这是否意味着在最坏的情况下插入需要O(n)时间复杂度？ - peter

只有在所有的键都散列到相同的值时，插入才会是O(n)。 - Jim Garrison

@user1389813 - 在这种情况下，是的。HashMap.insert()的平均成本为O(1)，但最坏情况为O(N)。但这并不奇怪。StringBuffer.append、追加到ArrayList等操作也会出现相同的情况。 - Stephen C

@StephenC，一个好的负载因子是否会影响性能？比如说比O(N)更好更快？ - peter

@AlexDiCarlo - 另外，如果您进行插入并且该插入触发了调整大小，则该插入操作将是O(N)。 插入的O(1)特征是哈希表生命周期内的平均值。 - Stephen C

Answer 2

当表格被调整大小时，原始表格的全部内容必须复制到新表格中，因此调整表格大小需要O(n)时间，其中n是原始表格中元素的数量。对于HashMap上的任何操作（假设均匀散列假设成立），其平摊成本为O(1)，但是，单个插入操作的最坏情况成本为O(n)。

- Alex DiCarlo