java - 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) 操作。但是您也可以从中看到数组何时增长的详细信息。