Java 的 Arraylist 操作的运行时间是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15712784/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the runtime of operations on Java's Arraylist?
提问by turtlesoup
It seems like there is no official benchmarks for some of the very commonly used classes, for example ArrayList.
对于一些非常常用的类，例如ArrayList，似乎没有官方基准。
I could not find the documentation on the runtime for insert or remove. Compared to Python's List, which is similar to ArrayList, there is a well documented runtime complexity (see link above).
我找不到有关插入或删除运行时的文档。与类似于 ArrayList 的Python 的List相比，有一个有据可查的运行时复杂性（参见上面的链接）。
This post, gave some somewhat detailed benchmark on removing and copying elements from an ArrayList, but it still doesn't give the exact complexity analysis. I'm working on a project which takes extremely long data (~500,000 data points) so I can't sit back and assume removing or inserting data from ArrayList operates in constant time like magic. Where can I find this information?
这篇文章给出了一些关于从 ArrayList 中删除和复制元素的详细基准，但它仍然没有给出确切的复杂性分析。我正在处理一个需要极长数据（约 500,000 个数据点）的项目，所以我不能坐视不管，假设从 ArrayList 中删除或插入数据像魔术一样在恒定时间内运行。我在哪里可以找到这些信息？
采纳答案by Kirby
For some quick references of Java complexities:
有关 Java 复杂性的一些快速参考：
- http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf
- http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html
- http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf
- http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html
But really, nothing beats looking to the source, which can be found here.
但实际上，没有什么比寻找来源更好的了，可以在这里找到。
Regarding the particular question of adding to an ArrayList, for example, we can see:
例如，关于添加到 ArrayList 的特定问题，我们可以看到：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
The complexity for this operation clearly depends on ensureCapacityInternal:
此操作的复杂性显然取决于ensureCapacityInternal：
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Which depends on grow:
这取决于成长：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
So we can see that the grow operation happens conditionally, and that in many cases, adding will be an O(1) operation. But you can also see from this the details of whenthe array will grow.
所以我们可以看到增长操作是有条件地发生的，在很多情况下，添加将是一个 O(1) 操作。但你也可以从这个细节看时，该阵列将增长。
