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.

您可以使用修改后的程序版本检测精确的增长点:

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

负责增加列表的源代码在ensureCapacity方法中，如下:

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

这相当于整数乘以 1.5.

This is an equivalent of integer multiplication by 1.5.

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