8

我想知道Java HashMap当负载因子超过阈值时调整大小的时间复杂度是多少？据我了解，对于 HashMap，表大小始终是 2 的幂次方偶数，所以每当我们调整表的大小时，我们不需要重新散列所有键（如果我错了，请纠正我），我们需要做的就是是分配额外的空间，并复制旧表中的所有条目（我不太确定JVM如何在内部处理），对吗？而Hashtable因为它使用素数作为表格大小，所以我们需要在重新调整表格大小时重新散列所有条目。所以我的问题是调整大小是否仍需要 O(n) 线性时间HashMap？

4

2 回答 2

9

调整大小还需要O(N)时间HashMap吗？

基本上，是的。

结果是导致调整大小的插入操作需要O(N)时间。但这发生在O(1/N)所有插入中，因此（在某些假设下）平均插入时间为O(1).

那么一个好的负载因子会影响这个性能吗？比更好更快O(N)？

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

如果我们对散列函数和键聚类做出正常假设，当负载因子较大时：

  • 平均哈希链长度更长，但仍然O(1),
  • 调整大小的频率减少了，但仍然是O(1/N)，
  • 调整大小的成本保持不变，复杂性仍然是O(N).

...因此，每当我们调整表格大小时，我们都不需要重新散列所有键（如果我错了，请纠正我。

实际上，您需要重新散列所有密钥。当您将哈希表大小加倍时，需要拆分哈希链。为此，您需要测试每个键的哈希值映射到两条链中的哪一条。（事实上​​，如果哈希表也有一个开放的组织，你也需要这样做。）

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

一条评论提到了所有键散列到相同散列码的退化情况。这可能是由于设计不良的散列函数或键的倾斜分布而发生的。

这会影响查找、插入和其他操作的性能，但不会影响调整大小的成本或频率。

于 2013-01-10T05:30:13.013 回答
0

调整表大小时，必须将原表的全部内容复制到新表中，因此调整表的大小需要 O(n) 时间，其中 n 是原表中的元素个数。HashMap 上任何操作的摊销成本（假设统一散列假设）是 O(1)，但是是的，单个插入操作的最坏情况成本是 O(n)。

于 2013-01-10T05:37:07.217 回答