ArrayList源码解析

作者: 大厂offer | 来源:发表于2018-07-09 13:45 被阅读4次

重点是理解ArrayList的扩容机制、底层数据结构、迭代器与快速失败（fast-fail）

1. ArrayList的成员变量

     /**
     * 默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 调用有参构造且传参为0时使用此对象数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 调用无参构造时使用此对象数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 实际存储元素的对象数组
     */
    transient Object[] elementData; // non-public to simplify nested class access

    /**
     * 数组的元素个数，另elementData.length才为容器的实际容量
     * @serial
     */
    public int size;

为什么要用transient修饰符来修饰elementData？

加上了transient修饰符的变量在序列化的时候会被忽略，由于elementData的长度并不等于实际元素的个数，所以如果按照elementData的长度来序列化，就会浪费内存空间；

2. ArrayList构造器

(1).ArrayList的无参构造方法并没有生成容量为10的数组；
(2).elementData对象是ArrayList集合底层保存元素的实现；
(3).size属性记录了ArrayList集合中实际元素的个数；
(4).ArrayList的扩容因子为1，扩容后容量=原容量+原容量>>1；

(1). 指定初始容量的构造方法

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];//赋值给elementData用于存储实际元素
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;//initialCapacity为0时
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }

(2). 无参构造

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//默认空数组，此时elementData.length依然为0
}

(3). 传入Collection的构造方法

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();//转为数组
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)//如果转换出错则，使用深层拷贝方式创建
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

3. ArrayList的扩容机制

在jdk1.7和1.8中，ArrayList的无参构造并没有生成容量为10的数组，而是在第一次添加元素的时候，会判断ArrayList中的ElementData对象是空数组还是含有元素，如果是空数组则调用ensureExplicitCapacity方法给list进行首次扩容为10，往后只要元素每超过上次设定的最小容量(elementData.length) ，就会扩容，扩容后的容量为：elementData.length + elementData.length>>1

//添加元素e
public boolean add(E e) {
    ensureCapacityInternal(size + 1);//见下详解
    //将对应角标下的元素赋值为e：
    elementData[size++] = e;
    return true;
}
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
    //如果此时ArrayList是空数组,则将最小扩容大小设置为10：
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //判断是否需要扩容，见下详解
    ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    //操作数+1
    modCount++;
    //判断最小扩容容量-数组大小是否大于0：
    if (minCapacity - elementData.length > 0)
        //扩容，见下详解
        grow(minCapacity);
}
//ArrayList动态扩容的核心方法:
private void grow(int minCapacity) {
    //获取现有数组大小：
    int oldCapacity = elementData.length;
    //位运算，得到新的数组容量大小，为原有的1.5倍：
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果新扩容的大小依旧小于传入的容量值，那么将传入的值设为新容器大小：
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    //如果新容器大小，大于ArrayList最大长度：
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //计算出最大容量值：
        newCapacity = hugeCapacity(minCapacity);
    //数组复制：
    elementData = Arrays.copyOf(elementData, newCapacity);
}
//计算ArrayList最大容量：
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    //如果新的容量大于MAX_ARRAY_SIZE。将会调用hugeCapacity将int的最大值赋给newCapacity:
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

Arrays.copy() 与 System.arraycopy

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;
    }

其中System.arraycopy：

public static native void arraycopy(Object src:源数组,  int  srcPos:源数组中的起始位置,
                                        Object dest:目标数组, int destPos:目标数据中的起始位置,
                                        int length:要复制的数组元素的数量);

Arrays.copy() 与 System.arraycopy的主要区别在于：Arrays.copy()不仅仅拷贝数组元素，还会新建一个新的数组，而System.arrayCopy方法是将元素拷贝到一个已存在的数组当中。

其中Arrays.copy()的Array.newInstance方法用于创建动态数组，如下示例：

package com.yiibai;
import java.lang.reflect.Array;

public class ArrayDemo {
   public static void main(String[] args) {
      String[] stringArray = (String[]) Array.newInstance(String.class, 3);

      Array.set(stringArray, 0, "Mahesh");
      Array.set(stringArray, 1, "Ramesh");
      Array.set(stringArray, 2, "Suresh");

      System.out.println("stringArray[0] = " + Array.get(stringArray, 0));
      System.out.println("stringArray[1] = " + Array.get(stringArray, 1));
      System.out.println("stringArray[2] = " + Array.get(stringArray, 2));
   }
}

编译并运行上面的程序，将产生以下结果 -

stringArray[0] = Mahesh
stringArray[1] = Ramesh
stringArray[2] = Suresh

4. 迭代器 Iterator

public Iterator<E> iterator() {
    return new Itr();
}
/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return //默认是0
    int lastRet = -1; // index of last element returned; -1 if no such  //上一次返回的元素 (删除的标志位)
    int expectedModCount = modCount; //用于判断集合是否修改过结构的 标志

    public boolean hasNext() {
        return cursor != size;//游标是否移动至尾部
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)//判断是否越界
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)//再次判断是否越界，在 我们这里的操作时，有异步线程修改了List
            throw new ConcurrentModificationException();
        cursor = i + 1;//游标+1
        return (E) elementData[lastRet = i];//返回元素 ，并设置上一次返回的元素的下标
    }

    public void remove() {//remove 掉 上一次next的元素
        if (lastRet < 0)//先判断是否next过
            throw new IllegalStateException();
        checkForComodification();//判断是否修改过

        try {
            ArrayList.this.remove(lastRet);//删除元素 remove方法内会修改 modCount 所以后面要更新Iterator里的这个标志值
            cursor = lastRet; //要删除的游标
            lastRet = -1; //不能重复删除 所以修改删除的标志位
            expectedModCount = modCount;//更新 判断集合是否修改的标志，
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    //判断是否修改过了List的结构，如果有修改，抛出异常
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

二、LinkedList

基础结构

在LinkedList中，内部类Node对象最为重要，它组成了LinkedList集合的整个链表，分别指向上一个点、下一个结点，存储着集合中的元素；每一个元素对应着一个Node对象，这个对象里面有三个成员变量，一个是item，用于存储当前元素；一个是prev用于指向上一个Node，还有一个是next用于指向它下一个Node

add()

LinkedList的添加方法，主要分为2种，一是直接添加一个元素，二是在指定角标下添加一个元素；

add(E e)底层调用linkLast(E e)方法，就是在链表的最后面插入一个元素；
add(int index, E element)，插入的角标如果==size，则插入到链表最后；否则，按照角标大小调用linkBefore(E e)方法插入到对应位置；

remove()

LinkedList的删除也提供了2种形式，其一是通过角标删除元素，其二就是通过对象删除元素；不过，无论哪种删除，最终调用的都是unlink来实现的，对node的指向进行修改；

set()

set(int index, E element)方法与add(int index,E element)的设计思路基本一致，都是创建新Node节点，插入到对应的角标下，修改前后节点的prev、next属性；在这个方法里面调用了一个node()方法，这个方法根据角标来判断是从前遍历还是从后开始遍历，而每次都至少要遍历半个集合，这也是LinkedList查询慢的原因。

get()

get方法里面也调用了node()方法，这个方法会返回对应节点的item