pet*_*ter 3 java hashtable hashmap time-complexity
我想知道Java HashMap当负载系数超过阈值时,调整大小的时间复杂度是多少？据我所知,HashMap的表大小始终是2的偶数,所以每当我们调整表的大小时,我们都不需要重新调整所有键(如果我错了就纠正我),我们需要做的就是是没有分配额外的空格并复制旧表中的所有条目(我不太确定JVM如何在内部处理它),对吗？而对于Hashtable因为它使用一个素数作为表的大小,所以我们需要所有的老调重弹,每当我们重新大小的条目表.所以我的问题是它还需要O(n)线性时间来调整大小HashMap吗？
所以我的问题是,在HashMap上调整大小仍然需要O(n)线性时间.
基本上,是的.
...所以每当我们调整表格大小时,我们都不需要重新调整所有密钥(如果我错了,请纠正我.
实际上,你将需要重提所有的键.当您将哈希表大小加倍时,需要拆分哈希链.为此,您需要测试每个键的哈希值映射到的两个链中的哪一个.(实际上,如果哈希表也有一个开放的组织,你需要做同样的事情.)
但是,在当前一代HashMap实现中(派生自Sun/Oracle代码库),哈希码值缓存在链接的条目对象中,因此不需要重新计算密钥的哈希码.
| 归档时间： |
|
| 查看次数： |
4803 次 |
| 最近记录： |