Java的Arraylist上的操作运行时是什么？

Question

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

我在运行时中找不到用于插入或删除的文档。与类似于ArrayList的Python的List相比，它的运行时复杂性得到了很好的证明（参见上面的链接）

This post给出了一些关于从ArrayList中删除和复制元素的详细基准测试，但仍然没有给出确切的复杂性分析。我正在从事一个需要非常长的数据（约500000个数据点）的项目，因此我不能坐视不管，假设从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

但事实上，没有什么比查找源代码更好的了，源代码可以找到here

---

例如，关于添加到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);
       }

因此，我们可以看到grow操作是有条件的，在许多情况下，加法将是一个O（1）操作。但是您也可以从中看到阵列何时增长的细节