Java：ArrayList add（）和remove（）性能，实现？ [英] Java: ArrayList add() and remove() performance, implementation?

问题描述

我已经读过ArrayList的 add（）和 remove（）操作在amortized constant时间运行。

在 add（item）的实现中，我可以看到它ArrayList使用一个数组缓冲区，它是在最多3/2的列表大小，并且如果它是满的，则调用System.arraycopy（），其应该在O（n）中执行，而不是O（1）时间。那么System.arraycopy是否会尝试做一些比将元素逐个复制到新创建的数组中更聪明的事情，因为时间实际上是O（1）？

---

结论： add（item）以摊销的常量时间运行，但 add（item，index）

解决方案

我读过某处，ArrayList的add（）和remove（）操作在摊销常量时间运行。

我认为 remove（）非常情况。

• A remove（Object）元素平均必须在列表中的一半条目上调用 equals ，然后复制另一半的引用。




• 
  

remove（...）的唯一情况是 O（1）平均（例如摊销）是当你使用 remove（int）的列表。

I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time. What does this mean exactly?

In the implementation of add(item) I can see that it ArrayList uses an array buffer, which is at most 3/2 of the list't size, and if it is full, System.arraycopy() is called, which should execute in O(n), not O(1) time. Is it then that System.arraycopy attempts to do something smarter than copying elements one by one into newly created array, since the time is actually O(1)?

---

Conclusion: add(item) runs in amortized constant time, but add(item, index) and remove(index) don't, they run in linear time (as explained in answers).

解决方案

I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time.

I don't think that is true for remove() except under unusual conditions.

• A remove(Object) call for a random element on average has to call equals on half of entries in the list, and then copy the references for the other half.

• A remove(int) call for a random element on average has to copy the references for half of the elements.

The only cases where remove(...) is going to be O(1) on average (e.g. amortized) is when you are using remove(int) to remove elements some constant offset from the end of the list.

这篇关于Java：ArrayList add（）和remove（）性能，实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！