jdk源码浅读-ArrayList
一、ArrayList概述
首先我们来说一下ArrayList是什么？它解决了什么问题？ArrayList其实是一个数组，但是有区别于一般的数组，它是一个可以动态改变大小的动态数组。ArrayList的关键特性也是这个动态的特性了，ArrayList的设计初衷就是为了解决Java数组长度不可变的问题。我们都知道在Java中数组一旦被创建出来，那么这个数组的大小就不可以改变了，而且初始化的时候就必须要指定数组的大小。在开发的场景中很多时候我们并不知道我们的数据量有多少，如果数组创建得太大就会造成极大的空间资源的浪费，如果太小了又会报数组下标越界异常。这是我们在开发的过程中使用数组来存储数据时经常会遇到的问题，但是如果使用ArrayList的话，就可以轻易的解决这个问题，它能够根据你存放的数据的大小动态的改变数组的大小（本质创建新数组），所以我们在写代码的时候就不需要关心数组的大小了，我觉得这也是ArrayList创建出来所需要解决的问题。当然，如果在知道数组的大小且对数组的数据不增加的话，建议使用数组的存储数据，这样对性能的提升有一定的帮助。
那么，ArrayList是怎么动态扩展数组大小的呢？下面通过源码一步一步揭开ArrayList的神秘面纱吧。
二、ArrayList全局变量
/** * Default initial capacity. */ //默认的初始化大小 private static final int DEFAULT_CAPACITY = 10; /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ //这个是用来存放数据用的数组，add进来的数据都是放到这个数组里面的 transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * * @serial */ //数组的大小 private int size;
三、ArrayList构造函数
ArrayList的构造函数有三个：
1、ArrayList(int initialCapacity)：initialCapacity，数组的初始化大小，该构造器创建一个指定大小的空数组。
2、ArrayList（）：创建一个默认大小为0的空数组
3、ArrayList(Collection<? extends E> c)：创建一个与c一样大小的数组，并将c的元素赋值到数组中。
**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {//创建一个 initialCapacity大小的空数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {//创建空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
//将c转换成数组，toArray方法返回的数组类型有可能不是Object类型的
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//数组类型不是Object类型，需要将类型转换成Object类，避免后面调用方法
// 的时候出现类型转换异常
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
这里我们主要看一下Arrays.copyOf()方法是如何转换类型的：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
这个方法中，如果传入的类型为Object类型，那么就直接创建一个Object数组，否则创建一个对应类型的数组。然后调用System.arraycopy方法，将原数组赋值到新创建的数组中，强调一下，凡是使用到数组的地方就一定会使用到arraycopy的方法，这个方法我在String源码阅读有说到过，在这里我再跟大家说一下这个方法吧。
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
这是一个本地方法所以无法继续往下看源码了，但是从源码中可以知道每个参数代表的含义
src：原数组
srcPos：原数组中开始复制的位置
dest：新数组，即目标数组
destPos：目标数组存放的位置，即从原数组的复制过来的元素从这个位置开始放
length：复制数组的长度
举个代码示例：
public static void main(String[] args) { int[] src = {1,2,3,4,5}; int[] dest = new int[6]; for (int i : dest) { System.out.print(i + " "); } System.out.println(); System.arraycopy(src,0,dest,0,src.length); for (int i : dest) { System.out.print(i + " "); } } //运行结果： //0 0 0 0 0 0 //1 2 3 4 5 0
看示例代码应该能够懂，第一次打印的时候dest只是被初始化没有赋值，所以里面每个元素存放的都是默认值，而int的默认值为0，所以打印出来的都是0，之后arraycopy后将src的所有数据复制到dest从0位置开始，所以打印的结果是 1 2 3 4 5 0
四、add方法
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { //确认当前数组大小不会发生越界异常，否者对数组进行扩容 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { //检查传入的下标是否在数组的范围之内 rangeCheckForAdd(index); //检查数组是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! //在index位置的元素全部往后移一位，为添加进来的元素腾出一个位置 System.arraycopy(elementData, index, elementData, index + 1, size - index); //将元素放入到index位置上 elementData[index] = element; size++; }
添加元素之前都需要检查一下当前的数组是否已经满了，如果满了就按照添加元素后的大小进行扩容。可以说在整个ArrayList类中最核心的方法就是ensureCapacityInternal了，这个方法就是用来动态扩容的。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) { //修改次数+1，主要实现快速失败机制的 modCount++; // overflow-conscious code //如果最小所需容量比当前数组的长度大的话就进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //每次扩容都是扩大原来数组大小的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: //创建一个新的数组，长度为 newCapacity，然后将原来数组的元素复制到新数组上并返回新数组，达到动态扩容数组的目的 elementData = Arrays.copyOf(elementData, newCapacity); }
在每次添加数据的时候都需要检查一下添加数据后的长度是否大于当前数组的长度，大于的话就创建一个大小为原来数组的1.5倍的新数组，然后将原数组的数据都复制到新数组中，最后将原数组的引用指向新数组，从而达到了扩容的目标。
五、get方法
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { rangeCheck(index); return elementData(index); } // Positional Access Operations @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
获取数据的方法比较简单，直接根据数组的下标index找到元素就行了，所以查找的速度比较快。
六、delete方法
/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); //移动区间 int numMoved = size - index - 1; if (numMoved > 0) //在删除位置后面的所有元素都往前挪一位 System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } /** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */ public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /* * Private remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }
删除有两个重载的方法，一个是传入一个数组的下标，另一个是传入具体的内容，但是最总还是根据equals方法查到index，然后根据index删除元素。假设有个数组为 String[] strs = {“a”,”b”,”c”,”d”,”e”}，现在调用 remove(3),那个大概流程为：
七、ArrayList的使用：
public static void main(String[] args) { List<Integer> list = new ArrayList<>(); //添加操作 list.add(1); list.add(2); list.add(3); //删除操作 list.remove(0); //查询操作 //1、随机访问： for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } //增强for循环遍历 for (Integer integer : list) { System.out.println(integer); } //使用迭代器遍历 Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()){ Integer integer = iterator.next(); System.out.println(integer); } }
八、总结：
1、ArrayList的增删改查等所有操作，其内部都是对数组进行操作。
2、ArrayList的动态扩容其本质是创建一个更大的数组。
3、每次扩容都扩大到原来的1.5倍，1.5倍是比较理想的，如果每次扩容太小的话就会频繁扩容，每次扩容都需要进行数组的复制，性能消耗比较大，应该尽量避免。如果扩容的倍数太大可能会造成空间的浪费。
4、ArrayList允许存放null值。
九、建议：
1、在知道数据大小且后期不会在添加数据的情况下建议使用数组，而不是ArrayList；
2、初始化前估计数据量的大小，尽量指定ArrayList的初始化容量，避免进行频繁的数组复制操作；
3、在删除比较多场景中不建议使用ArrayList；
4、在查多删少的场景中建议使用ArrayList，原因是这个类查找的速度非常快，时间复杂度为O(1),即不管数据量有多大，查找速度都一样的，而且非常快。但是删除操作是比较慢的，上面我也有提到过，ArrayList中每一次删除一个数据，后面所有的元素都要往前挪一位。如果数据量非常大，删除的数据刚好在第一个位置，那个后面的所有元素都要前移，时间复杂度为O(N),这样是非常耗费时间的。
5、ArrayList是非线程安全的，如果在多线程环境中对安全的要求比较高的，建议使用 CopyOnWriteArrayList这个类，不懂得可以百度一下，或者将ArrayList转成线程安全得，使用这种方式就可以：List list = Collections.synchronizedList(new ArrayList());
最后，我自己也手写了一个ArrayList，基本功能都能够实现，项目地址：https://github.com/rainple1860/MyCollection