关于java:ArrayList源码分析

1. AzrrayList 简介

java.util.ArrayList 是一个 数组队列 ，相当于 动静数组 。与 Java 中的数组相比，它具备 容量能动静增长、元素增删慢、查找快 的特点。

ArrayList继承于 AbstractList，实现了 List、RandomAccess、Cloneable、java.io.Serializable 这些接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{--- omit ---}

• ArrayList 继承了 AbstractList 形象办法，实现了 List 接口，提供了相干的 增加、删除、批改、遍历 等性能。
• RandomAccess 是一个标记接口，表明实现这个这个接口的 List 汇合是反对 疾速随机拜访 的。在 ArrayList 中，咱们即能够通过元素的序号疾速获取元素对象，这就是疾速随机拜访。
• ArrayList 实现了 Cloneable 接口，即笼罩了函数clone()，能被克隆。
• ArrayList 实现了 java.io.Serializable 接口，这意味着 ArrayList 反对序列化，能通过序列化去传输。

Tips：ArrayList中的操作不是线程平安的！倡议在单线程中才应用ArrayList，多线程中抉择应用 Vector 或者CopyOnWriteArrayList。

2. ArrayList 源码简析（JDK 1.8）

2.1 成员属性

// 默认容量大小
private static final int DEFAULT_CAPACITY = 10;

// ArrayList 空实例共享的一个空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// ArrayList 空实例共享的一个空数组，用于默认大小的空实例。// 与 EMPTY_ELEMENTDATA 离开，这样就能够理解当增加第一个元素时须要创立多大的空间。private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 真正存储 ArrayList 中的元素的数组
transient Object[] elementData;

// ArrayList 所蕴含的元素个数，留神并不是 elementData 的长度
private int size;

// 数组的最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

AbstractList抽象类中惟一属性：

// 示意 elementData 被批改的次数，每次 add 或者 remove 它的值都会加 1
protected transient int modCount = 0;

为什么 size 不是用来标记 elementData 数组的长度呢？

在 Java 中，一般来说：

• length属性是针对数组而言的，比方上面源码中 elementData.length 示意 elementData 数组的长度。
• length() 办法是针对字符串而言的，能够调用 length() 获取字符串长度。
• size() 办法是针对泛型汇合而言的，能够调用 size() 来获取汇合中个数。

这样，就很好了解为什么 size 不是 ArrayList 的长度了，不易记混。

2.2 构造方法

ArrayList 有三种初始化形式：

    /**
     * 有参的构造函数
     */    
    public ArrayList(int initialCapacity) {if (initialCapacity > 0) {
            // 初始化容量大于 0，创立 initialCapacity 大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 初始化容量等于 0，创立空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity:"+
                                               initialCapacity);
        }
    }

    /**
     * 默认无参构造函数（未指定初始化容量大小），应用初始容量 10 结构一个空列表。*/
    public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

    /**
     * 应用 Collection 汇合来初始化 ArrayList
     */
    public ArrayList(Collection<? extends E> c) {
        // 将汇合转换为数组
        elementData = c.toArray();
        // 如果数组的长度 size 不等于 0
        if ((size = elementData.length) != 0) {
            // 如果返回的不是 Object 类型数据
            if (elementData.getClass() != Object[].class)
                // 从新创立一个 size 大小的数组。// 并将原来不是 Object[]数组的内容，Copy 给新的是 Object[]的数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 用空数组代替
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

从下面的剖析中看出EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别。

EMPTY_ELEMENTDATA 示意在咱们实例化对象时指定了容量就是 0，当增加 1 个元素后，那么 elementData.length=1。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 示意实例化时是无参结构，未指定容量，在调用 add 办法增加第 1 个元素后会默认扩容容量为 10，即 elementData.length=10。

2.3 增加元素

    /**
     * 间接将元素增加到数组开端。*/
    public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     * 将元素增加到指定 index 地位。*/
    public void add(int index, E element) {
        // 对 index 进行界线查看
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // native 静态方法，原 elementData 数组的 index（蕴含）之后的数据，复制到指标 elementData 数组的 index + 1 之后地位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将从 index 开始之后的所有成员后移一个位，将 element 插入到 index 地位。elementData[index] = element;
        // 最初 size+1
        size++;
    }

    /**
     * 将指定汇合中的所有元素追加到此列表的开端。*/
    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;
    }

    /**
     * 从指定的地位开始，将指定汇合中的所有元素插入到此列表中。*/
    public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

源码中大量调用了 arraycopy() 办法，其具体应用能够参考由 System.arraycopy 引发的坚固：对象援用 与 对象 的区别一文。

2.4 删除元素

    /**
     * 删除列表中指定地位的元素。将任何后续元素挪动到左侧（从其索引中减 1）。*/
    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;
          // 从列表中删除的元素
        return oldValue;
    }

    /**
     * 从列表中删除指定元素。*/
    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++)
                // 返回 true，此列表蕴含指定的元素
                if (o.equals(elementData[index])) {fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    // 它跳过边界查看而不返回移除的值。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;
    }

    /**
     * 从列表中删除所有元素。*/
    public void clear() {
        modCount++;

        // 把数组中所有的元素的值设为 null
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    /**
     * 从此列表中删除所有索引为 fromIndex（蕴含）和 toIndex 之间的元素。*/
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {elementData[i] = null;
        }
        size = newSize;
    }

    /**
     * 从此列表中删除指定汇合中蕴含的所有元素。*/
    public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);
        // 如果此列表被批改则返回 true
        return batchRemove(c, false);
    }

2.5 ArrayList 扩容机制

能够发现，ArrayList 增加元素时，都会调用 ensureCapacityInternal 办法。

以 add(E e)办法为例：

    /**
     * 间接将元素增加到数组开端。*/
    public boolean add(E e) {
        // 查看是否须要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

2.5.1 ensureCapacityInternal() 和 ensureExplicitCapacity()

查看 ensureCapacityInternal()办法：

    // 获取到满足需要的最小容量
    private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // elementData 是空列表
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 扩容数组到 DEFAULT_CAPACITY(10)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // return size+1
        return minCapacity;
    }

    // 判断是否须要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity - elementData.length > 0)
            // 调用 grow 办法进行真正地扩容
            grow(minCapacity);
    }

1. 当增加第 1 个元素到 ArrayList 中时，minCapacity 为 size+1=0，elementData 还是空的 list，elementData.length=0，所有会执行 return Math.max(DEFAULT_CAPACITY, minCapacity);，minCapacity 变为 10。此时，minCapacity - elementData.length > 0 成立，所以会进入 grow(minCapacity) 办法真正扩容。
2. 当增加第 2 个元素时，minCapacity 为 size+1 =2，因为 elementData.length 在增加第一个元素后曾经扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，不会执行grow(minCapacity) 办法，即不会扩容。
3. 增加第 3、4、5…… 到第 10 个元素时，仍然不会扩容，数组容量还是为 10。

直到增加第 11 个元素，minCapacity - elementData.length > 0 成立，执行 grow 办法进行扩容。

2.5.2 grow()

grow 办法是整个 ArrayList 扩容的外围：

    private void grow(int minCapacity) {//11
        // oldCapacity 为旧容量
        int oldCapacity = elementData.length;//10
        // 位移运算符比一般运算符的运算快很多。>> 示意将 oldCapacity 右移一位，(oldCapacity >> 1)相当于 oldCapacity /2
        // 将新容量更新为旧容量的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 若新容量还是小于最小需要容量
        if (newCapacity - minCapacity < 0)
            // 间接最小需要容量当作数组的新容量
            newCapacity = minCapacity;
       // 如果 minCapacity 大于最大容量，则新容量则为 `Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。// 新容量大于 MAX_ARRAY_SIZE,
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 执行 hugeCapacity()办法
            newCapacity = hugeCapacity(minCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    // 比拟 minCapacity 和 MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {if (minCapacity < 0)
            throw new OutOfMemoryError();

        // minCapacity > MAX_ARRAY_SIZE，新数组的大小为 Integer.MAX_VALUE
        // 否则，新数组的大小为 MAX_ARRAY_SIZE
        // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

由此可知，ArrayList 默认扩容大小是原大小的1.5 倍左右（oldCapacity 为偶数必定是 1.5 倍，为奇数必定就是等于 1.5 倍左右）。

• 如果扩容后的 newCapacity 仍小于 minCapacity，那么就将数组大小调整为 minCapacity 大小。
• 如果 minCapacity 的值在 MAX_ARRAY_SIZE 和 Integer.MAX_VALUE 之间，那么新数组调配 Integer.MAX_VALUE 大小，否则调配 MAX_ARRAY_SIZE。

“>>”（右移运算符）：”>>1“示意右移 1 位；右移 n 位相当于除以 2 的 n 次方。

2.6 ensureCapacity

从下面源码剖析，在应用 Arraylist 初始化容量时，就会通过一系列逻辑判断后再进行扩容。如果数据量很大，运行效率岂不是很低。

而 ensureCapacity() 办法，就是让咱们事后设置 Arraylist 的大小，这样就能够大大提高初始化速度了。

    public void ensureCapacity(int minCapacity) {
        // 以此来判断咱们实例化时是否调用无参构造函数。如果不是，minExpand=0；如果是，minExpand=10。int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        // 咱们设置的 minCapacity 大于 minExpand 才进行扩容
        if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);
        }
    }

最好在 add 大量元素之前用 ensureCapacity 办法，以缩小增量重新分配的次数。

上面就来测试一下应用 ensureCapacity 前后的区别：

public class EnsureCapacityTest {public static void main(String[] args) {ArrayList<Object> list = new ArrayList<Object>();
        final int minCapacity = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < minCapacity; i++) {list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("不应用 ensureCapacity 耗时：" + (endTime - startTime));

        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(minCapacity);
        for (int i = 0; i < minCapacity; i++) {list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("应用 ensureCapacity 耗时：" + (endTime1 - startTime1));
    }
}

运行后果：

不应用 ensureCapacity 耗时：2471
应用 ensureCapacity 耗时：289

3 遍历

ArrayList 次要反对三种遍历形式：

• foreach 循环遍历

Integer value = null;
for (Integer integ:list) {value = integ;}

• 迭代器遍历

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {value = (Integer)iter.next();}

• 随机拜访，通过索引值去遍历

因为 ArrayList 实现了 RandomAccess 接口，它反对通过索引值去随机拜访元素。

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {value = (Integer)list.get(i);        
}

4 fail-fast 机制

疾速失败 (fail-fast) 是 Java 汇合中的一种谬误检测机制。它的个性就是在遍历 Java 汇合时，不容许进行值的批改，否则会抛出ConcurrentModificationException 异样。

例如在 多线程 开发中，线程 A 正在通过 iterator 遍历某汇合，线程 B 凑巧对该汇合的内容进行了批改，那么线程 A 持续遍历汇合就会抛出 ConcurrentModificationException 异样，产生 fail-fast 事件。

查看 AbstractList 源码：

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    ... ...

    // 用来记录 List 批改的次数：每批改一次(增加 / 删除等操作)，将 modCount+1
    protected transient int modCount = 0;

    // 返回 List 对应迭代器。实际上，是返回 Itr 对象。public Iterator<E> iterator() {return new Itr();
    }

    // Itr 是 Iterator(迭代器)的实现类
    private class Itr implements Iterator<E> {
        int cursor = 0;

        int lastRet = -1;

        // 批改数的记录值。// 每次新建 Itr()对象时，都会保留新建该对象时对应的 modCount。int expectedModCount = modCount;

        public boolean hasNext() {return cursor != size();
        }

        public E next() {checkForComodification();
            --- omit ---
        }

        public void remove() {if (lastRet == -1)
                throw new IllegalStateException();
            checkForComodification();
            --- omit ---
        }

        final void checkForComodification() {
            // 每次遍历 List 中的元素的时候，都会比拟 expectedModCount 和 modCount 是否相等。// 若不相等，则抛出 ConcurrentModificationException 异样，产生 fail-fast 事件。if (modCount != expectedModCount)
                throw new ConcurrentModificationException();}
    }
     ... ...   
}

可见，ArrayList 在增加或者删除元素时，无论是调用 add()、remove()还是 clear()等其余办法，只有波及到批改汇合中的元素个数时，都会扭转 modCount 的值。

而每当迭代器遍历下一个元素之前，都会检测 modCount 变量是否为 expectedModCount 值。如果在汇合被遍历期间批改 modCount 的值，那么 modCount != expectedModCount，进而抛出 ConcurrentModificationException 异样。

因而，在多线程开发中，倡议应用 java.util.concurrent 包下的线程安全类去取代 java.util 包下的线程不安全类。比方 ArrayList 对应的线程安全类为CopyOnWriteArrayList。

特地留神的是，并不是只有在多线程中才会呈现 fail-fast 事件。在单线程下，如果遍历过程中对汇合对象的内容进行了批改的话也会触发 fail-fast 机制。

foreach 循环也是借助迭代器进行遍历的。

应该防止写出相似这样的代码：

        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        for (String str : list) {if("b".equals(str)){list.remove(str);
            }
        }

参考

• ArrayList 源码解析
• 由 System.arraycopy 引发的坚固：对象援用 与 对象 的区别
• Java 汇合系列 03 之 ArrayList 具体介绍 (源码解析) 和应用示例
• Java 汇合系列 04 之 fail-fast 总结(通过 ArrayList 来阐明 fail-fast 的原理、解决办法)