JAVA集合－ArrayList原理

ArrayList概述

ArrayList是一个底层基于数组实现的动态数组。在数据大小未知的情况下，可以一直往其中添加元素，ArrayList通过动态扩容来保证容器的容量可以满足元素的写入。

ArrayList的实现

private transient Object[] elementData;
private int size;

ArrayList底层采用了一个Object[]数组来保存存入list的元素，用size来记录list中存入元素的数量。其操作基本上是对数组elementData的操作。

主要操作

• 构造方法
  1、无参构造器。构造一个空的集合，默认初始容量大小10。
  2、指定capacity的构造器。构造一个空的集合，初始容量大小为传入参数的大小。
  3、传入一个已有的集合，构造一个ArrayList。将传入的集合转换成数组，放到elementData中。
• add(element)
  1、判断容量是否足够并扩容。如果底层数组elementData的length小于当前size+1时，进行扩容，扩容后的容量大约为之前的1.5倍。
  2、将元素加至elementData数组最后一个元素之后。
  3、size值加1

ArrayList扩容图解.png

步骤1和2分别通过Array.newInstance和System.arraycopy方法来实现。

• add(index, element)
  1、检查index是否越界。
  2、判断容量是否足够并扩容。 和上面一样。
  3、index之前的元素不变，index之后的元素同时往后挪动一个下标。
  4、index位置的数据置为element。

  例如，add(4, 8) 的图解：

  
  ArrayList add图解.png

• set(index,element)
  1、检查index是否越界。
  2、将下标对应的元素直接替换为传入的新元素。elementData[index] = element

• remove(index)
  1、检查set的下标是否越界。
  2、index之前的元素不变，index之后的元素同时往前挪动一个下标。
  3、数组末尾size-1下标位置置为null，同时size值减1。

  例如，remove(4) 图解

ArrayList remove图解.png

• get(index)
  直接返回elementData[index]

通过观察，我们可以发现，ArrayList在get／set随机读取操作的时候，效率非常高，而在进行add／remove等操作时，需要对数组中部分元素进行移动。查看源码可以发现，元素前后移动的过程中，主要使用了System.arraycopy进行数组拷贝来实现。

在add中自动扩容的时候，需要用Array.newInstance创建一个容量更大的新数组，然后通过System.arraycopy进行旧数组和新数组之间的数据copy。如果在预先能够知道元素总数的情况下，可以直接构造指定大小容量的集合。或者在大批量数据添加之前，如果知道要添加的元素的总数，可以通过调用ensureCapacity方法一次性增加集合的容量，避免递增式的扩容带来的程序消耗。

ArrayList多线程下的使用

ArrayList不是线程安全的，在多线程环境下遍历，遇到并发修改时，会使用Fail-Fast机制，抛出ConcurrentModificationException。在多线程下可以考虑用Collections.synchronizedList(List list)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。

总结

1. ArrayList底层基于数组实现，用Object[]来存储元素，用size来记录元素个数。
2. ArrayList get／set直接对数组索引处进行操作效率很高，add／remove需要对数组进行元素进行拷贝移动。
3. ArrayList 在元素数量可预知的情况下，可提前扩容，减少递增扩容带来的消耗。
4. ArrayList是非线程安全的，可以用Collections工具类返回同步的list，或者用并发包下的CopyOnWriteArrayList。