Lebear
If you don't like the world, create one instead of complaining.

浅谈ArrayList源码实现

2020-10-20
Word count: 2k | Reading time: 9min

本文记录笔者对JDK1.8下ArrayList源码的解读

ArrayList中属性解读

  • transient Object[] elementData; //顾名思义，属性为数据空间，有容量大小限制，其中存放add进的数据
  • private static final Object[] EMPTY_ELEMENTDATA = {};//如果在调用构造方法传入初始容量为0时候，会创建一个空elementData
  • private int size;//该属性为List中拥有的元素个数

add：添加元素

boolean add(E e)

此方法为单独插入元素到List中

1
2
3
4
5
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保新元素可添加的条件为容量大于等于size+1
    elementData[size++] = e;//在数组尾部添加元素，顺便size+1
    return true;
}

void add(int index, E element)

此方法为在index处插入元素element

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
        rangeCheckForAdd(index);//数组越界Check，条件：index > size  index < 0

        ensureCapacityInternal(size + 1);  //这句为了确保要插入数据容量至少大于size+1，内部实现中如果minCapacity - elementData.length > 0会调用grow方法扩容。
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//arraycopy是一个native方法，作用是将要插入位置后的所有元素后移一位，在index处预留出空间以供新元素插入
        elementData[index] = element;//把预插入元素放置到index位置
        size++;//list大小增加
}

grow：扩容

此方法在add前会进行容量检测，可能调用扩容方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    private void grow(int minCapacity) {//传参为最小需要扩容的大小
        // overflow-conscious code
        int oldCapacity = elementData.length;//原有容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量为原容量的1.5倍
        if (newCapacity - minCapacity < 0)//如果新容量（1.5倍）小于最小需要容量（原因：int取值范围越界）
            newCapacity = minCapacity;//赋值为最小所需容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)//如果新容量大于int最大值-8
            newCapacity = hugeCapacity(minCapacity);//则利用hugeCapacity进行计算复制大小（后面有写）
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//分配好新空间，可以对旧数组进行扩容
    }


    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow 溢出
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE ://最小分配大小大于Integer_Max-8则复制为int最大值
            MAX_ARRAY_SIZE;
    }

//此外，如ensureCapacity等方法，内部都是调用grow来进行扩容，没什么其他内容，这里就不谈了

remove：移除元素

public E remove(int index)：按index移除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public E remove(int index) {
    rangeCheck(index);//检查index越界

    modCount++;//标记修改次数，类似版本号
    E oldValue = elementData(index);//取出index位置的元素

    int numMoved = size - index - 1;//需要移动元素的个数，也就是如果从index位置删除元素，那么后续所有其他元素需要前移一位来补空缺
    if (numMoved > 0)//如果移动的元素不是最后一个元素，则都需要前移后面所有元素，由此可见，如果移除index=0的元素的效率最差，需要数组整体前移
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);//移动操作
    elementData[--size] = null; // clear to let GC do its work，将最后一个元素位置置为null，原注释解释方便GC回收垃圾

    return oldValue;//返回删除的元素
}

public boolean remove(Object o)：按元素移除

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
public boolean remove(Object o) {
        if (o == null) {//如果要移除元素为null
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {遍历查找数值=null的元素
                    fastRemove(index);//实际就是封装了之前移除过程
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {//使用equals来进行比较，如果相等，则移除
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

//此方法基本上就是对于之前移除过程进行封装，可参考public E remove(int index)中的移除注释
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
    }

Iterator：内部实现迭代器

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
public Iterator<E> iterator() {//默认调用此方法
            return listIterator();//其中会调用listIterator(0)，也就是从0位置开始迭代
}        

public ListIterator<E> listIterator(final int index) {
            checkForComodification();//检测修改版本号，for concurrent
            rangeCheckForAdd(index);//检测越界
            final int offset = this.offset;

            return new ListIterator<E>() {
                int cursor = index;//内部维护索引，默认为0开始
                int lastRet = -1;//记录上一次返回的索引，初始化为-1
                int expectedModCount = ArrayList.this.modCount;

                public boolean hasNext() {//是否有下一个元素
//这里使用sublist，实际上内部有属性指向parent(当前list)，可理解为就是当前list
                    return cursor != SubList.this.size;//判断游标是否到达list的size

                }

                @SuppressWarnings("unchecked")
                public E next() {
                    checkForComodification();//检查修改次数版本号
                    int i = cursor;
                    if (i >= SubList.this.size)//如果越界，抛出无元素异常
                        throw new NoSuchElementException();
                    Object[] elementData = ArrayList.this.elementData;//创建对list的引用
                    if (offset + i >= elementData.length)//越界
                        throw new ConcurrentModificationException();
                    cursor = i + 1;//此时游标自动后移，为了迭代继续进行
                    return (E) elementData[offset + (lastRet = i)];//返回通过游标取出的元素，更新lastRet为当前返回的索引
                }

                public boolean hasPrevious() {//如果游标不等于0，则有前置元素
                    return cursor != 0;
                }

                @SuppressWarnings("unchecked")
                public E previous() {//返回前置元素，与next方法大同小异
                    checkForComodification();
                    int i = cursor - 1;
                    if (i < 0)
                        throw new NoSuchElementException();
                    Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length)
                        throw new ConcurrentModificationException();
                    cursor = i;
                    return (E) elementData[offset + (lastRet = i)];
                }

                @SuppressWarnings("unchecked")//支持lambda表达式特性的方法
                public void forEachRemaining(Consumer<? super E> consumer) {
                    Objects.requireNonNull(consumer);
                    final int size = SubList.this.size;
                    int i = cursor;
                    if (i >= size) {
                        return;
                    }
                    final Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    while (i != size && modCount == expectedModCount) {
                        consumer.accept((E) elementData[offset + (i++)]);
                    }
                    // update once at end of iteration to reduce heap write traffic
                    lastRet = cursor = i;
                    checkForComodification();
                }

                public int nextIndex() {//返回游标下一次访问的元素位置
                    return cursor;
                }

                public int previousIndex() {//返回上一个访问的位置
                    return cursor - 1;
                }

                public void remove() {//移除元素
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();//同上

                    try {
                        SubList.this.remove(lastRet);//内部调用此list的remove方法去移除刚访问过的元素
                        cursor = lastRet;//移除后，内部游标则跳到上一次访问元素位置
                        lastRet = -1;//上一次访问元素因为被删除，所以lastret又置为-1
                        expectedModCount = ArrayList.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void set(E e) {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();//修改版本检测

                    try {
                        ArrayList.this.set(offset + lastRet, e);//调用set方法设置当前元素为新值
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void add(E e) {
                    checkForComodification();

                    try {
                        int i = cursor;
                        SubList.this.add(i, e);//在当前游标位置添加元素
                        cursor = i + 1;//游标后移一位
                        lastRet = -1;
                        expectedModCount = ArrayList.this.modCount;//设置期望的修改版本号，此处运用了类似CAS的控制机制，在许多方法调用前会有checkForComodification()方法来进行修改版本号检测
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }


                final void checkForComodification() {//修改版本号检测
                    if (expectedModCount != ArrayList.this.modCount)
//这里使用了期望修改版本号与当前修改版本号对比，来判断是否期间有其他线程修改了这个值，利用CAS机制，以支持并发操作；如果不一致抛出并发修改异常
                        throw new ConcurrentModificationException();
                }
            };
        }

get and set：简单的获取元素和设置元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 public E get(int index) {
    rangeCheck(index);//检查越界

    return elementData(index);//直接返回元素
}


public E set(int index, E element) {
    rangeCheck(index);//检查越界

    E oldValue = elementData(index);//记录index位置的旧元素
    elementData[index] = element;//将index位置设置为新元素
    return oldValue;//返回旧元素
}

思考：

1、由上面源代码，可以总结，许多地方都用到了ensureCapacity与modcount版本号检测方法，如果我们学过设计模式后，考虑是否可以使用一个代理类，来完成一些鲁棒性等内容的前置代理？

2、对于remove的两个方法，可以明显发现，数组前移一个是写在方法内，另一个则是调用封装方法，所以这一点可以统一使用封装方法，重用代码。

3、本文未讲解到支持lambda部分的源码，之后笔者会补充。

Author: Leisurelybear

Link: https://blog.lebear.top/2020/10/20/296/

Copyright: Copyright © 2019-2022 LeisurelyBear All rights reserved.

< PreviousPost
OBS录制全屏黑屏解决方法NextPost >
从Android Studio中导出签名APK
CATALOG
  1. 1. ArrayList中属性解读
  2. 2. add：添加元素
    1. 2.1. boolean add(E e)
    2. 2.2. void add(int index, E element)
  3. 3. grow：扩容
  4. 4. remove：移除元素
    1. 4.1. public E remove(int index)：按index移除
    2. 4.2. public boolean remove(Object o)：按元素移除
  5. 5. Iterator：内部实现迭代器
  6. 6. get and set：简单的获取元素和设置元素
  7. 7. 思考：