ArrayList源码解读

发表于 | 分类于
字数统计: 1.6k字 | 阅读时长 ≈ 6分

ArrayList源码解读

1
2
3
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
        实现了List<E>接口 实现了RandomAccess接口代表支持随机访问

Alt text

构造方法

1
2
3
4
5
6
7
//初始化的时候只是初始化成一个空数组，在添加第一个元素的时候才会把数组大小变为10
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
     private static final int DEFAULT_CAPACITY = 10;//默认容量是10
    transient Object[] elementData;
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//添加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
//添加元素方法 每次添加元素都要确保内部容量足够 ensureCapacityInternal方法
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0) //如果比数组长度长 就扩容 
        grow(minCapacity);
}

private void grow(int minCapacity) {
        // overflow-conscious code
        //oldCapacity为旧容量
        int oldCapacity = elementData.length;
        //newCapacity为新容量，oldCapacity >> 1 是oldCapacity右移一位，相当于/2
        //为什么不用直接/2 因为位运算的速度快于整除运算 此处的newCapacity为1.5倍的oldCapacity
        int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5*oldCapacity
        //如果新容量小于最小需要容量，新容量就直接等于最小需要容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity; 
        //如果新容量大于最大容量，进入hugeCapacity方法
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity); //复制数组 最底层是System.arraycopy方法
}
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //比较minCapacity和MAX_ARRAY_SIZE，前者大，新容量就为 Integer.MAX_VALUE，后者大新容量就为MAX_ARRAY_SIZE即为Integer.MAX_VALUE - 8
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
//删除元素方法
    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;
    }
    //先判断这个要移除的元素是不是null 如果是 就遍历 找到元素为空的数组下标 
    // 找到了null就fastRemove
    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
        }
        //用System.arraycopy方法把index+1后的元素都往前移 时间复杂度为O(n) 所以删除元素代价非常高

fail-fast

  1. fail-fast 产生的原因就在于程序在对 collection 进行迭代时，某个线程对该 collection 在结构上对其做了修改，这时迭代器就会抛出 ConcurrentModificationException 异常信息，从而产生 fail-fast。
  2. 迭代器在调用 next()、remove() 方法时都是调用 checkForComodification() 方法，该方法主要就是检测 modCount == expectedModCount ? 若不等则抛出 ConcurrentModificationException 异常，从而产生 fail-fast 机制。所以要弄清楚为什么会产生 fail-fast 机制我们就必须要用弄明白为什么 modCount != expectedModCount ，他们的值在什么时候发生改变的。
    expectedModCount 是在 Itr 中定义的：int expectedModCount = ArrayList.this.modCount;所以他的值是不可能会修改的，所以会变的就是 modCount。modCount 是在 AbstractList 中定义的，为全局变量
  3. ArrayList 中无论 add、remove、clear 方法只要是涉及了改变 ArrayList 元素的个数的方法都会导致 modCount 的改变。所以我们这里可以初步判断由于 expectedModCount 得值与 modCount 的改变不同步，导致两者之间不等从而产生 fail-fast 机制。知道产生 fail-fast 产生的根本原因了，我们可以有如下场景：
    有两个线程（线程 A，线程 B），其中线程 A 负责遍历 list、线程B修改 list。线程 A 在遍历 list 过程的某个时候（此时 expectedModCount = modCount=N），线程启动，同时线程B增加一个元素，这是 modCount 的值发生改变（modCount + 1 = N + 1）。线程 A 继续遍历执行 next 方法时，通告 checkForComodification 方法发现 expectedModCount = N ，而 modCount = N + 1，两者不等，这时就抛出ConcurrentModificationException 异常，从而产生 fail-fast 机制。
  4. 解决方案：
    方案一：在遍历过程中所有涉及到改变 modCount 值得地方全部加上 synchronized 或者直接使用 Collections.synchronizedList，这样就可以解决。但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。
    方案二：使用 CopyOnWriteArrayList 来替换 ArrayList。推荐使用该方案。
    CopyOnWriteArrayList 为何物？ArrayList 的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。 该类产生的开销比较大，但是在两种情况下，它非常适合使用。1：在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时。2：当遍历操作的数量大大超过可变操作的数量时。遇到这两种情况使用 CopyOnWriteArrayList 来替代 ArrayList 再适合不过了。那么为什么 CopyOnWriterArrayList 可以替代 ArrayList 呢？
    第一、CopyOnWriterArrayList 的无论是从数据结构、定义都和 ArrayList 一样。它和 ArrayList 一样，同样是实现 List 接口，底层使用数组实现。在方法上也包含 add、remove、clear、iterator 等方法。
    第二、CopyOnWriterArrayList 根本就不会产生 ConcurrentModificationException 异常，也就是它使用迭代器完全不会产生 fail-fast 机制。
    CopyOnWriterArrayList 所代表的核心概念就是：任何对 array 在结构上有所改变的操作（add、remove、clear 等），CopyOnWriterArrayList 都会 copy 现有的数据，再在 copy 的数据上修改，这样就不会影响 COWIterator 中的数据了，修改完成之后改变原有数据的引用即可。同时这样造成的代价就是产生大量的对象，同时数组的 copy 也是相当有损耗的。

System.arraycopy() 和 Arrays.copyOf()方法

ArrayList源码中用到的这2个方法
Arrays.copyOf()实际上是调用了System.arraycopy()这个方法，区别就是System.arraycopy()可以指定是原数组和新数组，指定起始位置和长度以及新放入的位置，copyOf() 是系统自动在内部新建一个数组，并返回该数组。

参考:fail-fast 机制