Java：ArrayList add（）和remove（）性能，实现？

本文介绍了Java：ArrayList add（）和remove（）性能，实现？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我已经读过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.