我想知道时间复杂度是多少Java HashMap当负载因子超过阈值时调整大小？据我了解，HashMap 的表大小始终是 2 的偶数次幂，因此每当我们调整表大小时，我们不需要重新散列所有键（如果我错了，请纠正我），我们需要做的就是是分配额外的空间而不复制旧表中的所有条目（我不太确定JVM内部如何处理它），对吗？而对于Hashtable因为它使用素数作为表大小，所以每当我们调整表大小时，我们都需要重新哈希所有条目。所以我的问题是调整大小是否仍然需要 O(n) 线性时间HashMap ?
还需要吗O(N)调整大小的时间HashMap?
基本上，是的。
结果是插入操作这会导致调整大小将采取O(N)时间。但这发生在O(1/N)所有插入，所以（在某些假设下）average插入时间是O(1).
那么良好的负载因子会影响这种性能吗？喜欢比更好更快O(N)?
负载因子的选择会影响性能，但不会影响复杂性。
如果我们对哈希函数和键聚类进行正常假设，当负载因子较大时：
- 平均哈希链长度更长，但仍然
O(1),
- 调整大小的频率减少，但仍然存在
O(1/N),
- 调整大小的成本保持不变，并且复杂性仍然是
O(N).
...所以每当我们调整表的大小时，我们都不需要重新哈希所有键（如果我错了，请纠正我。
其实，你would需要重新散列所有密钥。当哈希表大小加倍时，需要拆分哈希链。为此，您需要测试每个键的哈希值映射到两个链中的哪一个。 （事实上，如果哈希表也有开放的组织，则您需要执行相同的操作。）
然而，在当前这一代HashMap实现中，哈希码值为cached在链接的条目对象中，因此不需要重新计算键的哈希码。
一条评论提到了一种退化情况，即所有键都散列到相同的散列码。发生这种情况的原因可能是哈希函数设计不当，或者密钥分布不均。
这会影响查找、插入和其他操作的性能，但不会影响调整大小的成本或频率。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
