jdk ArrayList工作原理分析

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

list是一个有序的集合，通常也会被称为序列。使用list接口可以精确的控制每个元素的插入，可以通过索引访问list中的各个项，也可以在list中查询元素。

上面这段话摘自jdk的官方文档。

这里的源码分析基于jdk 1.8。

ArrayList源码分析

首先我们先分析list接口的实现类之一，也是最常用的，ArrayList的源码。

ArrayList的底层使用一个数组完成数据的添加、查询、修改、删除。这个数组就是下面字段中的elementdata。

字段

//集合的默认容量
private static final int DEFAULT_CAPACITY = 10;
//一个空集合数组，容量为0
private static final Object[] EMPTY_ELEMENTDATA = {};
//存储集合数据缓冲区的数组，默认为null
transient Object[] elementData;
//ArrayList中的元素个数，比如数组的容量是5，size是1，表示容量为5的数组目前有一条记录
private int size;

构造函数

//带有指定集合容量参数的构造函数
public ArrayList(int initialCapacity) {
    //如果集合容量大于0，初始化elementData属性，确定容量
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //如果集合容量等于0，设定elementdata为空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //如果集合容量小于0，抛出非法参数异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
//没有参数的构造函数
public ArrayList() {
    //设定ArrayList数组缓冲区为空数组，使用默认的容量10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//参数是一个集合的构造函数
public ArrayList(Collection<? extends E> c) {
    //elementData使用参数集合内部的数组
    elementData = c.toArray();
    //如果集合内部参数
    if ((size = elementData.length) != 0) {
        // c.toArray可能不会返回Object[]，需要进一步判断 (see 6260652) 
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 如果参数集合内部为空数组，则设定内部数组为空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

方法

我们挑选几个重要的方法讲解一下

boolean add(E e) 方法

把元素添加到集合的最后面。

public boolean add(E e) {
    //调用ensureCapacityInternal，参数是集合当前元素长度+1。确保容量够大，不够大时扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果数组是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，说明调用的是无参的构造函数，则使用默认容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果集合需要的最小容量比数组容量要打，则需要扩容。（溢出检查
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//扩容实现
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);
    // 将原始数组拷贝到新长度数组中。(这一步其实是new了一个容量为newCapacity的新数组，然后将原始数组elementData拷贝到新数组中，所以这里比较耗性能的)
    elementData = Arrays.copyOf(elementData, newCapacity);
}

下面通过一个例子讲解下ArrayList的扩容机制：

//初始化一个容量为5的数组
ArrayList<String> stringArrayList=new ArrayList<String>(5);
stringArrayList.add("1");
stringArrayList.add("2");
stringArrayList.add("3");
stringArrayList.add("4");
stringArrayList.add("5");
//当添加第6个元素时，检查到容量不够，扩容1.5倍
stringArrayList.add("6");

上面2个白色区域就是扩容出来的，第6个元素被添加，最后一个元素还没被设置。

void add(int index, E element)

在指定位置插入元素，移动当前位置元素和右侧一连串的元素（索引加1）。

public void add(int index, E element) {
    rangeCheckForAdd(index);
    //溢出检查
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //拷贝index位置开始到结束的元素到新数组，从新数组index+1位置开始
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //设置指定位置为插入的元素
    elementData[index] = element;
    //数组中元素数量+1
    size++;
}

上图显示了要在容量为5的数组中的第4个位置插入6这个元素，会进行3个步骤：

​ 1.容量为5的元素，再次加入元素，需要扩容，扩容出两个白色空间

​ 2.扩容之后，4和5这两个元素拷贝到新数组索引+1的位置

​ 3.拷贝之后，设置指定4的位置 为元素 6

E remove(int index)

移除指定位置的元素

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);
    //移除尾部的元素，让gc回收
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

比如要移除5个元素中的第3个元素，首先要把4和5这两个位置上的元素分别拷贝到3和4这两个位置，然后把最后一个位置也就是第5位置set为null。

boolean remove(Object o)

移除指定元素在数组中第一次出现的位置元素

public boolean remove(Object o) {
    if (o == null) {
        //ArrayList允许元素为null，对null值的删除在这里执行
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        //效率比较低，需要从第一个元素遍历找到equals相等的元素后进行删除，删除同样需要移动元素
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

void clear()

移除list中的所有元素

public void clear() {
    modCount++;
    // 遍历集合数据全部设置为null
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    //集合中的元素数量设置为0
    size = 0;
}

E set(int index, E element)

用element替换集合中指定位置的元素

public E set(int index, E element) {
    //检查索引值是否合法
    rangeCheck(index);
    E oldValue = elementData(index);
    //替换指定位置的元素
    elementData[index] = element;
    return oldValue;
}

E get(int index)

获取集合中指定位置的元素

public E get(int index) {
    rangeCheck(index);
    //直接返回指定位置的元素
    return elementData(index);
}

boolean addAll(Collection<? extends E> c)

在集合尾部添加指定集合中的所有元素

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    //扩容检查
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //直接在数组后面添加指定数组中的所有元素
    System.arraycopy(a, 0, elementData, size, numNew);
    //更新数组中的元素长度
    size += numNew;
    return numNew != 0;
}

Object[] toArray()

根据elementData数组拷贝一个新的数组

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

ArrayList注意事项

1.ArrayList允许插入null元素

2.当数据量很大时，ArrayList中间添加或移除元素的时候，会拷贝元素到新的位置，所以效率较低。建议使用其他集合，如LinkedHashSet

3.ArrayList虽然可以自动扩容，但是数据量较大时，扩展的容量也较大，会造成空间浪费。建议如果预先知道要新增的容量大小，初始化ArrayList时就指定容量大小

三个有趣的示例

示例1

int[] a={1,2,3};
Integer[] b={1,2,3};
List A= Arrays.asList(a);
List B= Arrays.asList(1,2,3);
List C= Arrays.asList(b);
System.out.println(JSON.toJSONString(A)+",ListA的元素类型为："+A.get(0).getClass()+",长度为："+A.size());
System.out.println(B);
System.out.println(C);

output:
[[1,2,3]],ListA的元素类型为：class [I,长度为：1
[1, 2, 3]
[1, 2, 3]

问题：A的长度为什么是1呢？

我们看下asList的源码

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

发现asList接收一个泛型变长参数，而基本类型是不能被泛型化的，所以当传入int类型数组的时候，数组是一个对象，把int类型数组作为了T类型。则A长度为1。

示例2

List<String> pets= Arrays.asList("cat","dog");
pets.add("pig");

ouput:
Exception in thread "main" java.lang.UnsupportedOperationException
	at java.util.AbstractList.add(AbstractList.java:148)
	at java.util.AbstractList.add(AbstractList.java:108)

问题：为什么list不能使用add方法呢？

我们还是查看下源码：

public class Arrays {  
    .......  
  
    private static class ArrayList<E> extends AbstractList<E>  
        implements RandomAccess, java.io.Serializable  
        {  
        private static final long serialVersionUID = -2764017481108945198L;  
        private final E[] a;  
  
        ArrayList(E[] array) {  
            a = Objects.requireNonNull(array);
        }  
          
        ......  
    }  
}

发现静态内部类中，存储数组的a变量是final类型的，由此发现，这里是不能做任何内部元素的添加删除操作的。

内部类里面也没有add，remove方法，可以看下这个类继承的AbstractList类里面的这些方法实现：

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}
public E remove(int index) {
    throw new UnsupportedOperationException();
}

ok,我们使用asList得到的对象add，remove操作时就是直接抛出异常。

如果要对asList的对象使用add，remove方法可以使用如下的解决办法

List<String> pets= new ArrayList<String>(Arrays.asList("cat","dog"));

示例3

String[] test={"a","b","c","d"};
List<String> testList=Arrays.asList(test);
System.out.println("List的原始顺序："+testList);
Collections.shuffle(testList,new Random(10));
System.out.println("List打乱后的顺序："+testList);
System.out.println("List打乱顺序后数组的顺序："+ Arrays.toString(test));

output:
List的原始顺序：[a, b, c, d]
List打乱后的顺序：[b, d, a, c]
List打乱顺序后数组的顺序：[b, d, a, c]

我们发现改变了list的顺序，但是数组的顺序也发生了变化。

解决办法：

List<String> testList = new ArrayList<String>(Arrays.asList(test));

综上：

Arrays.asList()产生的List的对象会使用底层数组作为其物理实现，只要你执行操作就会修改这个List，并且你不想原来的数组被修改，那么你就应该在另一个容器中创建一个副本。