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