Java HashMap调整大小的时间复杂度 [英] Time complexity for Java HashMap resizing

问题描述

我想知道当负载因子超过阈值时， Java HashMap 调整大小的时间复杂度是多少？据我所知HashMap的表大小始终是2的偶数，所以无论何时调整表的大小，我们都不需要重新哈希所有的键（如果我错了，就纠正我），我们需要做的是分配额外的空间而没有复制旧表中的所有条目（我不太清楚JVM如何在内部处理），对吗？而对于 Hashtable ，因为它使用素数作为表大小，所以无论何时重新调整表的大小，我们都需要重新哈希所有条目。所以我的问题是，它仍然需要O（n）线性时间调整大小 HashMap ？

解决方案

所以我的问题是它是否仍然需要O（n）线性时间来调整HashMap的大小。 b $ b

基本上，是的。

...所以每当我们调整表格大小时，我们都不需要重新哈希全部（如果我错了，请纠正我）

其实，您会需要重新提供所有的当你加倍散列表大小时，散列链需要被拆分，为此，你需要测试两个链中每个键的散列值映射到哪一个（确实，如果）

然而，在当前一代 HashMap 实现中（派生自Sun / Oracle代码库）中，哈希代码值在链接的条目对象中被缓存，因此密钥的哈希码不需要重新计算。

I am wondering what would be the time complexity on Java HashMap resizing when the load factor exceeds the threshold ? As far as I understand for HashMap the table size is always power of 2 an even number, so whenever we resize the table we don't necessary need to rehash all the keys (correct me if i am wrong), all we need to do is to allocate additional spaces without and copy over all the entries from the old table (I am not quite sure how does JVM deal with that internally), correct ? Whereas for Hashtable since it uses a prime number as the table size, so we need to rehash all the entries whenever we re-size the table. So my question is does it still take O(n) linear time for resizing on HashMap ?

解决方案

So my question is does it still take O(n) linear time for resizing on HashMap.

Basically, yes.

... so whenever we resize the table we don't necessary need to rehash all the keys (correct me if i am wrong.

Actually, you would need to rehash all of the keys. When you double the hash table size, the hash chains need to be split. To do this, you need to test which of two chains the hash value for every key maps to. (Indeed, you need to do the same if the hash table had an open organization too.)

However, in the current generation of HashMap implementations (derived from the Sun/Oracle codebases), the hashcode values are cached in the chained entry objects, so that the hashcode for a key doesn't ever need to be recomputed.

这篇关于Java HashMap调整大小的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！