java ArrayList容量大小增加奇怪的行为

Question

当ArrayList希望存储的元素多于实际容量时，它会增加容量。这是一种非常经济高效的操作，因为我们实际上将所有数据从以前的ArrayList复制到容量更大的新ArrayList。然而，我想知道的是，当ArrayList只需要更多的空间时，可能一些具有容量的操作并没有继续进行——但这已经是很久以前的事了。我想知道为什么要花这么长时间才能从我的输出中获得“慢索引”，而增加容量是我唯一的想法。这是我的密码：

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;

public class MainArr {
    ArrayList<Integer> normalList = new ArrayList<Integer>();

    public static void main(String[] args) throws Exception {
        MainArr m = new MainArr();
        m.addElements();
    }

    public void addElements() throws Exception {
        long startTime = System.currentTimeMillis();
        for (int j = 0; j < 20000000; j++) {
            if (j % 500000 == 0) {
            System.out.println("j:" + j + " capacity:" + getCapacity(this.normalList));
        }
        long addTime = System.currentTimeMillis();
        this.normalList.add(j);
        if (System.currentTimeMillis() - addTime > 50) {
            System.out.println("slow index-" + j + " - time:" + (System.currentTimeMillis() - addTime));
        }
    }
    System.out.println("End after:" + (System.currentTimeMillis() - startTime));
}

int getCapacity(List al) throws Exception {
    Field field = ArrayList.class.getDeclaredField("elementData");
    field.setAccessible(true);
    return ((Object[]) field.get(al)).length;
    }
}

输出：

j:0 capacity:0
j:500000 capacity:540217
j:1000000 capacity:1215487
j:1500000 capacity:1823230
j:2000000 capacity:2734845
j:2500000 capacity:2734845
j:3000000 capacity:4102267
j:3500000 capacity:4102267
j:4000000 capacity:4102267
slow index-4102267 - time:1203 //We need more space in ArrayList.That's why it takes some time.
j:4500000 capacity:6153400
j:5000000 capacity:6153400
j:5500000 capacity:6153400
j:6000000 capacity:6153400
j:6500000 capacity:9230100
slow index-6758010 - time:1477 //We dont need to increase capacity. But we stop for a moment...
j:7000000 capacity:9230100 //... and we have the same capacity
j:7500000 capacity:9230100
j:8000000 capacity:9230100
j:8500000 capacity:9230100
j:9000000 capacity:9230100
j:9500000 capacity:13845150 // Somehow capacity is increased insanely fast
j:10000000 capacity:13845150
j:10500000 capacity:13845150
j:11000000 capacity:13845150
j:11500000 capacity:13845150
j:12000000 capacity:13845150
slow index-12426474 - time:3168 //We dont need to increase capacity. But we stop for a moment...
j:12500000 capacity:13845150 //... and we have the same capacity
j:13000000 capacity:13845150
j:13500000 capacity:13845150
j:14000000 capacity:20767725  // Somehow capacity is increased insanely fast
j:14500000 capacity:20767725
slow index-14639924 - time:144  
j:15000000 capacity:20767725
j:15500000 capacity:20767725
j:16000000 capacity:20767725
j:16500000 capacity:20767725
j:17000000 capacity:20767725
j:17500000 capacity:20767725
j:18000000 capacity:20767725
j:18500000 capacity:20767725
j:19000000 capacity:20767725
j:19500000 capacity:20767725
slow index-19980735 - time:218
End after:6990

Answer 1

为了提高性能，请尝试在ArrayList实例化上定义大容量。例如：

List<Users> users = new ArrayList<>(100000);
users.add(new User("John", "Doe"));

只有在您事先知道所需容量的情况下，这才会对您有所帮助。如果你不知道会有多少个实例，那就考虑使用另一个数据结构。

例如，看一下Queue接口的实现，特别是LinkedList。这个数据结构有一个添加新元素的固定时间，但是当它们在列表中间时，索引对元素的获取是不好的。请注意LinkedList还实现了List接口以及ArrayList，因此以下语法有效：

List<Users> users = new LinkedList<>();
users.add(new User("John", "Doe"));

Answer 2

ArrayList代码经过优化，以10开始容量，并在需要更多空间时每次将容量增加1.5倍

您可以通过修改后的程序检测精确的生长点：

public void addElements() throws Exception {
    int lastCap = -1;
    for (int j = 0; j < 1000000; j++) {
        this.normalList.add(j);
        int cap = getCapacity(this.normalList);
        if (cap != lastCap) {
            System.out.println("size:" + normalList.size() + " capacity:" + cap);
            lastCap = cap;
        }
    }
}

int getCapacity(List al) throws Exception {
    Field field = ArrayList.class.getDeclaredField("elementData");
    field.setAccessible(true);
    return ((Object[]) field.get(al)).length;
}

此prints包含以下数字：

size:1 capacity:10
size:11 capacity:15
size:16 capacity:22
size:23 capacity:33
size:34 capacity:49
size:50 capacity:73
size:74 capacity:109
... // And so on

source code responsible for growing the list在ensureCapacity方法中，它如下所示：

int newCapacity = (oldCapacity * 3)/2 + 1;

这相当于整数乘以1.5

Answer 3

每次调用add函数时，它都会调用ensureCapacity函数，其中size+1作为minCapacity参数（列表的大小，而不是列表后面的数组）

您可以在下面看到ensureCapacity的代码：

 public void ensureCapacity(int minCapacity) {
         modCount++;
         int oldCapacity = elementData.length;
         if (minCapacity > oldCapacity) {
             Object oldData[] = elementData;
             int newCapacity = (oldCapacity * 3)/2 + 1;
             if (newCapacity < minCapacity)
                 newCapacity = minCapacity;
             // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
         }
     }

请注意，只有当minCapacity参数大于数组的当前大小时，它才会创建一个新数组

编辑（谢谢@jyotsananandwani）：

In JDK 1.7, new way to calculate resize is :

int newCapacity = oldCapacity + (oldCapacity >> 1)

where right shift operator makes sure to increase the capacity by 50% of old capacity, i.e. 1.5 times