Java数据结构-ArrayList最细致的解析笔记

ArrayList是一个类，这个类有一个数组参数elementData，ArrayList集合中的元素正是保存在这个数组中，它继承了数组查询的高性能，参考第3篇。ArrayList还封装了很多方法，便于对数组中的数据进行操作处理，其中就包括上一篇说的扩容，建议先理解第3篇数组。

扩容原理

在eclipse中调试以下代码，如下设置四个断点，打开调试视图。

public static void main(String[] args) {

List list = new ArrayList();

System.out.println("断点1");

list.add(1);

System.out.println("断点2");

list.add(2);

list.add(3);

list.add(4);

list.add(5);

list.add(6);

list.add(7);

list.add(8);

list.add(9);

list.add(10);

System.out.println("断点3");

list.add(11);

System.out.println("断点4");

}

断点1：list的数组参数elementData的值为Object[0]，表示数组初始长度为0。

Java数据结构-ArrayList最细致的解析笔记

断点2：在集合中添加了第一个元素，elementData数组长度变成了10。即初始扩容长度为10。

Java数据结构-ArrayList最细致的解析笔记

断点3：在集合中一共添加了10个元素，elementData长度仍然为10，此时无需扩容。

Java数据结构-ArrayList最细致的解析笔记

断点4：添加第11个元素，即超出了原数组长度。elementData长度扩容为15，即第二次以后的扩容，长度为原长度的1.5倍。

Java数据结构-ArrayList最细致的解析笔记

注意看图，elementData在断点1时标识是29，在断点2和断点3处的标识都是31，而在断点4时标识46，第2篇讲过，这说明elementData引用变量前后一共指向了三个不同的数组对象。也就是说，elementData并没有真正的扩容，而是创建了一个容量更大的数组对象来替代之前的数组，并且复制之前的数组内容。

元素类型Object

第3篇讲过，数组元素的长度必须是一致的。而以上代码中，我添加的都是int类型数据。假如我添加一个long型数据，如下，也是可以的。而int（4字节）和long（8字节）的长度是不一样的，这是为什么？

list.add(1);

list.add(1l);

假如声明时使用List，就指定了固定元素类型。而我的代码中并没有使用泛型，所以它的类型可以是任意Object，但不能是基本类型。当添加int元素时，会自动转换为Integer。当添加long元素时，会自动转换为Long。因此，最终list所有的元素类型都是引用类型（4字节），长度相同，这是实现数组高性能查询所必需的。以后讲其他集合的元素类型时，也和ArrayList是一样的原理，不再解释。

在尾部添加

第3篇在数组中添加了5亿个元素，很快就执行完成。假如用同样的方法在ArrayList中添加5亿元素会怎么样？

int size=500000000;

List list = new ArrayList();

long t1 = System.currentTimeMillis();

for(int i=0;i<size;i++){

list.add(i);

}

long t2 = System.currentTimeMillis();

System.out.println(t2-t1);

运行结果：内存溢出

一直运行了n分钟没有结果，最终报错内存溢出。因为在这个过程中，会不断的扩容，不断的创建新数组对象，最终把内存撑爆。要解决这个问题，可以在创建ArrayList时传入一个int参数，根据参数值会直接初始一个较大的数组，就不用再频繁的扩容了。注意：如果初始数组太大又不使用，也会让费内存空间。修改代码，将new ArrayList()改成new ArrayList(size)

List list = new ArrayList(size);

只是这样做还不够，因为上面说了，list.add(i)实际上是创建了5亿个对象，数据量太大内存仍然不足。再次修改添加代码，将list.add(i)改成list.add(1)，1会转换成new Integer(1)，5亿个new Integer(1)仍然是5亿个对象。但是java对一些对象做了缓存，其中包括new Integer(0至127)，以后会讲。现在只需知道，i改成1后只会有一个new Integer(1)对象，而不会创建5亿个对象。之后文章都会使用1作为集合参数，不再解释。修改代码如下，再次运行

list.add(1);

耗时：1080毫秒

add()方法默认是在尾部添加数据，ArrayList的size可以帮助数组瞬间完成定位，然后直接添加，所以这样的性能是很高的。

Java数据结构-ArrayList最细致的解析笔记