HashMap 与 ArrayList 插入性能混淆

Question

根据我的理解，hashmap 插入是 O(1)，对于 arraylist，插入是 O(n)，因为对于 hashmap，hashfunction 计算 hashcode 和索引并插入条目，数组列表每次输入新时都会进行比较元素。

Answer 1

首先，复杂度为 O(1) 的操作并不总是比复杂度为 O(n) 的操作花费的时间少。O(1) 仅意味着操作需要一个常数时间（可以是任何值），而不管输入的大小。O(n) 意味着操作所需的时间随着输入的大小线性增加。这意味着仅当 n 为无穷大时，O(1) 理论上保证比 O(n) 花费更少的时间。

现在ArrayList.add()来看您的示例，操作以分摊的常数时间运行，这意味着尽管特定迭代可能需要 O(n) 时间，但随时间分布的平均复杂度为 O(1)。有关摊销常数时间的更多信息，请参阅此问题。