ArrayList的容量大小增加了奇怪的行为 [英] ArrayList capacity size increasing strange behaviour

问题描述

当ArrayList想要存储比实际容量更多的元素时，它将增加容量。因为我们实际上将所有数据从以前的ArrayList复制到更大容量的新ArrayList，所以这是非常节省成本的操作。但是我想知道当ArrayList只需要更多空间时，也许没有进行某些具有容量的操作-但是要早得多。我不知道我的唯一想法就是花这么长时间才能从输出中获得慢索引并增加容量。这是我的代码：

When ArrayList wants to store more elements than actual capacity it increases the capacity. It is very cost efficient operation since we actually copy all data from previous ArrayList to new ArrayList with larger capacity. However I wonder that maybe some operations with capacity are not proceeded when ArrayList just needs more space - but much before. I wonder what takes such long time for "slow indexes" from my output and increasing capacity is my only one idea. Here is my code:

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

推荐答案

ArrayList 代码为优化后的容量可以从10开始，并在需要更多空间时每次增加1.5倍。

ArrayList code is optimized to start the capacity at 10, and grow it by 1.5 times each time when more space is needed.

您可以使用经过改进的程序来检测精确的增长点m：

You can detect precise grows points with a modified version of your program:

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

此打印以下数字：

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

The 负责列表增长的源代码在 ensureCapacity 方法中，如下所示：

The source code responsible for growing the list is in ensureCapacity method, it goes as follows:

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

这等效于1.5的整数乘法。

This is an equivalent of integer multiplication by 1.5.

这篇关于ArrayList的容量大小增加了奇怪的行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！