所以我正在阅读有关 Java 集合 api 的信息,并且想知道 HashMap put()
api,根据文档,它说它是一个常量时间操作,但让我感到困惑的是是否考虑了重新散列考虑是否作为时间复杂度计算的一部分。
ArrayList
add()
另一边的 api 清楚地说明了它的摊销 o(n) 即添加 n 个元素将花费 n 个时间,为什么不呢?它适用于 HashMap
吗?尽管 HashMap
在达到负载因子时动态创建更大的桶,并将哈希重新应用于现有的整体以确定新的桶位置。
任何对上述解释的帮助将不胜感激,让我知道是否需要将此问题移至其他部分,然后再投票。
谢谢。
最佳答案
每当表变得太满时,就会分配一个更大的常数因子(例如,两倍大)的新表,并将所有元素从旧表移动到新表。因此,对 put() 的单个特定调用有时可以在 Θ(n) 时间内运行,但是(从空表开始)对 put() 的 n 次调用的整个序列将始终在预期的 O(n) 时间内运行——这平均每个操作的预期 O(1) 时间。
关于java - HashMap put() api 时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41443216/