HashMap与ArrayList插入性能混淆 [英] HashMap vs. ArrayList insertion performance confusion

问题描述

根据我的理解，hashmap插入是O（1），对于一个arraylist插入是O（n），因为对于hashmap，hash函数计算散列码和索引并插入条目，每次数组列表进行一次比较进入一个新的元素。

解决方案

首先，复杂度O（1）的操作并不总是比操作复杂度O（n）。 O（1）仅意味着操作需要一个固定的时间（可以是任何值），而不管输入的大小如何。 O（n）表示操作所需的时间随输入大小线性增加。这意味着只有当n是无穷大时，O（1）在理论上才能保证比O（n）花费更少的时间。 现在来看你的例子， ArrayList.add（）操作以摊销常量时间运行，这意味着尽管对于特定迭代它可能花费O（n）时间，但随时间推移的平均复杂度为O（1 ）。有关分期固定时间的更多信息，请参阅此问题。

From my understanding a hashmap insertion is O(1) and for an arraylist the insertion is O(n) since for the hashmap the hashfunction computes the hashcode and index and inserts the entry and an array list does a comparison every time it enters a new element.

解决方案

Firstly, an operation of complexity O(1) does not always take lesser time than an operation of complexity O(n). O(1) only means that the operation takes a constant time (which could be any value), regardless of the size of the input. O(n) means that the time required for the operation increases linearly with the size of the input. This means that O(1) is theoretically guaranteed to take lesser time than O(n) only when n is infinity.

Now coming to your examples, ArrayList.add() operation runs in amortized constant time, which means although it could take up to O(n) time for a particular iteration, the average complexity spread out over time is O(1). For more information on amortized constant time, refer to this question.

这篇关于HashMap与ArrayList插入性能混淆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！