Java的Arraylist操作的运行时间是多少？

Question

对于一些非常常用的类，例如ArrayList，似乎没有官方基准测试。

我找不到有关插入或删除运行时的文档。与与 ArrayList 类似的Python 的List相比，它具有详细记录的运行时复杂性（请参阅上面的链接）。

这篇文章给出了一些关于从 ArrayList 中删除和复制元素的详细基准，但它仍然没有给出准确的复杂性分析。我正在开发一个需要极长数据（约 500,000 个数据点）的项目，因此我不能坐下来假设从 ArrayList 中删除或插入数据就像魔术一样在恒定时间内进行。我在哪里可以找到这些信息？

Answer 1

有关 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

但实际上，没有什么比寻找源代码更好的了，可以在这里找到源代码。

例如，关于添加到 ArrayList 的特定问题，我们可以看到：

public boolean add(E e) {
           ensureCapacityInternal(size + 1);  // Increments modCount!!
           elementData[size++] = e;
           return true;
       }

此操作的复杂性显然取决于EnsureCapacityInternal：

private void ensureCapacityInternal(int minCapacity) {
               modCount++;
               // overflow-conscious code
               if (minCapacity - elementData.length > 0)
                   grow(minCapacity);
           }

这取决于成长：

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);
       }

所以我们可以看到增长操作是有条件发生的，并且在许多情况下，添加将是一个 O(1) 操作。但您还可以从中看到数组何时增长的详细信息。