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 ?
我想知道当加载因子超过阈值时，Java HashMap调整大小的时间复杂度是多少？据我所知，对于HashMap，表大小始终是2的偶数，所以每当我们调整表的大小时，我们都不需要重新调整所有键（如果我错了就纠正我），我们需要做的就是是没有分配额外的空格并复制旧表中的所有条目（我不太确定JVM如何在内部处理它），对吗？而对于Hashtable，因为它使用素数作为表大小，所以每当我们重新调整表的大小时，我们都需要重新散列所有条目。所以我的问题是，在HashMap上调整大小还需要O（n）线性时间吗？
2 个解决方案
#1
6
So my question is does it still take O(n) linear time for resizing on HashMap.
所以我的问题是它是否仍需要O（n）线性时间来调整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.
但是，在当前生成的HashMap实现（从Sun / Oracle代码库派生）中，哈希码值缓存在链接的条目对象中，因此不需要重新计算键的哈希码。
#2
0
When the table is resized, the entire contents of the original table must be copied to the new table, so it takes O(n) time to resize the table, where n is the number of elements in the original table. The amortized cost of any operation on a HashMap (assuming the uniform hashing assumption) is O(1), but yes, the worst case cost of a single insertion operation is O(n).
调整表的大小时，必须将原始表的全部内容复制到新表中，因此需要花费O（n）时间来调整表的大小，其中n是原始表中元素的数量。 HashMap上任何操作的摊余成本（假设统一散列假设）是O（1），但是，单个插入操作的最坏情况成本是O（n）。
#1
6
So my question is does it still take O(n) linear time for resizing on HashMap.
所以我的问题是它是否仍需要O（n）线性时间来调整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.
但是，在当前生成的HashMap实现（从Sun / Oracle代码库派生）中，哈希码值缓存在链接的条目对象中，因此不需要重新计算键的哈希码。
#2
0
When the table is resized, the entire contents of the original table must be copied to the new table, so it takes O(n) time to resize the table, where n is the number of elements in the original table. The amortized cost of any operation on a HashMap (assuming the uniform hashing assumption) is O(1), but yes, the worst case cost of a single insertion operation is O(n).
调整表的大小时，必须将原始表的全部内容复制到新表中，因此需要花费O（n）时间来调整表的大小，其中n是原始表中元素的数量。 HashMap上任何操作的摊余成本（假设统一散列假设）是O（1），但是，单个插入操作的最坏情况成本是O（n）。