java - HashMap vs. ArrayList 插入性能混淆

Question

根据我的理解， HashMap 插入是 O(1)，对于数组列表，插入是 O(n)，因为对于 HashMap ，哈希函数计算哈希码和索引并插入条目，而数组列表每次都进行比较输入一个新元素。

Answer 1

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

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