ArrayList源码分析

此源码分析JDK版本为1.7，只是简单分析，算是个人看源码的一点小总结，随意性比较强，专业的还需百度。
先简单介绍一下ArrayList，ArrayList为线性数据结构，时间复杂度为O(1)，内部存储为数组。以下所有表达ArrayList的内容统称为数组。
ps:ArrayList和Vector的区别就是ArrayList是线程不安全的，Vector是线程安全的。Vector底层核心方法都为synchronized。

简介

1
2
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

属性

1
2
3
4
5
6
7
8
9
10
11
12
//默认数组大小
private static final int DEFAULT_CAPACITY = 10;
//默认空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//数组(ArrayList中的数据就放在此数组中)
private transient Object[] elementData;
//数组真实数据的长度(与数组的长度不一样)
private int size;
//数组最大大小常量(Integer.MAX_VALUE - 8原因是尝试分配较大的数组可能会导致OutOfMemoryError)
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//修改次数(对于线程安全至关重要，在Iterator中会解释)
protected transient int modCount = 0;

#构造方法

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 ArrayList() {
    super();
    //将属性中的空数组赋给elementData
    this.elementData = EMPTY_ELEMENTDATA;
}
//初始化长度的构造方法
public ArrayList(int initialCapacity) {
    super();
    //当初始化长度小于0则抛出异常
    if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    //new该长度的Object数组给与elementData
    this.elementData = new Object[initialCapacity];
}
//根据父类Collection类型的对象进行构造的构造方法
public ArrayList(Collection<? extends E> c) {
    //不同的Collection的实现类会有不同的实现，但最终结果都是转为Object数组
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
    //目前未知(属性定义为Object，判断不等于因此觉得不太理解，而且debug各种类型都是直接跳过此方法，暂时觉得此判断不会进入)
    elementData = Arrays.copyOf(elementData, size, Object[].class);
}

方法

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
//返回数组大小
public int size() {
    return size;
}
//是否为空
public boolean isEmpty() {
    return size == 0;
}
//获取该值的下标(无返回-1)
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            //可能会有人说Object默认的equals()实现是==，觉得此方法块没意义，但实际调用的为真实类型的equals()方法
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
//获取最后该值的下标(无返回-1)
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
        	//同上
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
//是否包含
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
//返回数组(并不是返回Object数组，而是真实类型的数组)
public Object[] toArray() {
    //查看copyOf源码会发现返回的是真实类型数组
    return Arrays.copyOf(elementData, size);
}
//当调用get()时会通过此方法返回值 (default，外部无法调用)
E elementData(int index) {
    return (E) elementData[index];
}
//检查传入的下标参数是否越界
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//返回该下标所对应的值
public E get(int index) {
    //检查下标参数是否越界
    rangeCheck(index);

    //根据下标返回值
    return elementData(index);
}
//设置下标和值
public E set(int index, E element) {
    //检查下标参数是否越界
    rangeCheck(index);

    //获取该下标的值
    E oldValue = elementData(index);
    //为该下标赋新值
    elementData[index] = element;
    //返回旧值
    return oldValue;
}
//扩容：第一步将传入的值与默认最小值进行对比
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        //最小为默认最小值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    //扩容实现
    ensureExplicitCapacity(minCapacity);
}
//扩容：第二步将第一步的值与数组大小进行对比判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    //当传入的值大于数组长度时，进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//扩容：扩容真正实现(默认情况下扩容之后的大小为当前数组长度+数组对2取余)
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //定义变量为当前大小加一半取余
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果变量小于传的参数，则新的数组大小为传入的参数
    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:
    //调用Arrays.copyOf()扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}
tag:第一个判断:如果传入的值小于[数组大小加对二取余]则新的数组大小为传入的值，定义的新值为传入的值；如果不是则无操作。第二个判断:第一步运算厚的结果如果大于默认数组最大长度，则返回hugeCapacity()计算后的值；如果不是则无操作
//判断传的值是否大于默认数组最大长度，如果是则为Integer最大值；如果不是则为默认数组最大长度，返回可用大小
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
//在数组中增加值
public boolean add(E e) {
    //添加则会增加modCount
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
//为某个下标新增值
public void add(int index, E element) {
    //判断下标是否越界
    rangeCheckForAdd(index);

    //先扩容(防止index刚好为当前数组长度)
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //将源数组index位置开始的数组复制到目标数组index+1后，复制的数量为size-index个
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
//删除某下标对应的值
public E remove(int index) {
    //判断下标是否越界
    rangeCheck(index);

    //增加修改次数
    modCount++;
    //获取旧值
    E oldValue = elementData(index);

    //判断删除该下标元素需要向前移动多少个位置
    int numMoved = size - index - 1;
    //如果当前下标不是最后一个元素，则将源数组index+1位置开始的数组复制到目标数组index后，复制的数量为numMoved个
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work  //置空原尾部数据 不再强引用， 可以GC掉

    return oldValue;
}
//根据下标删除值(不检查下标是否越界)
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  //置空原尾部数据 不再强引用， 可以GC掉
}
//删除值(只删除第一个)
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;
}
//清空数组
public void clear() {
    //增加修改次数
    modCount++;

    // clear to let GC do its work  //置空原尾部数据 不再强引用， 可以GC掉
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    //数组真实长度归零
    size = 0;
}
//将Collection增加到当前数组之后
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;
}
//判断增加下标是否越界(与判断是否越界区别在于少了=size和增加了不小于0)
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//在下标后增加Collection
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)
        //将index之后的位移量numNoved空置出来
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    //将Collection的数组放置index之后index + numNew之前
    System.arraycopy(a, 0, elementData, index, numNew);
    //设置真实数组大小长度
    size += numNew;
    return numNew != 0;
}
//删除指定区间内的数组内容(protected修饰，subList方法会调用，外部不可访问)
protected void removeRange(int fromIndex, int toIndex) {
    //增加修改次数
    modCount++;
    //计算位移量
    int numMoved = size - toIndex;
    //将toIndex后的数组放置fromIndex之后
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    //计算应当删除的起始下标
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    //设置真实数组大小长度
    size = newSize;
}
//与Collection取交集
public boolean retainAll(Collection<?> c) {
    //实际调用，true表示取交集
    return batchRemove(c, true);
}
//根据complement决定取交集还是取非交集(注意this.elementDat和elementData )
private boolean batchRemove(Collection<?> c, boolean complement) {
    //定义变量
    final Object[] elementData = this.elementData;
    //为了方便理解可以理解为:r为this.elementData的下标，w为elementData 下标
    int r = 0, w = 0;
    //定义是否修改成功
    boolean modified = false;
    try {
        for (; r < size; r++)
            //根据complement决定是否将此值放入elementData中
            if (c.contains(elementData[r]) == complement)
                //w++是将值放入下标为w之后w再+1
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //如果c.contains()抛出异常是则r一定不等于size，则执行下方。将this.elementData下标r之后的复制到elementData下标w之后
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        //如果w!=size则需要将w之后的数组清楚
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
                modCount += size - w;
                size = w;
                //只有进入此代码块才表明修改成功
                modified = true;
        }
    }
    return modified;
}
//返回Itr迭代器
public Iterator<E> iterator() {
    return new Itr();
}
//返回ListItr迭代器
public ListIterator<E> listIterator() {
    return new ListItr(0);
}
//subList部分放置在ArrayList-SubList文章中
tag:在上段代码中，只有w!=size的情况下才会表明修改成功。我的理解：首先，contains()发生异常只会是空指针。如果相等则可能发生以下几种情况1.求交集但两个数组完全一样2.求非交集两个数组完全不一样3.从开始就出现异常

#总结

1
2
3
4
5
6
1.ArrayList增删实现基本靠System.arraycopy()实现，修改是通过数组下标(只能在下标范围内修改)
2.通过modCount解决线程安全问题(iterator遍历时如果修改则会直接抛出异常)
3.手动置null去除强引用使gc下次工作是回收此对象
4.增、删都会因为数组扩容二影响效率，修改和查询不会影响效率
5.增、删都会修改modCount，修改和查询不会修改modCount
6.手动置null只是将内存地址取消引用，因为gc是通过计数法来进行回收，当内存地址没有被引用就会被回收

ArrayList-Iterator源码分析

此源码分析JDK版本为1.7，只是简单分析，算是个人看源码的一点小总结，随意性比较强，专业的还需百度。
#private class Itr implements Iterator{}
##简介
私有内部类

1
private class Itr implements Iterator<E> {}

属性

1
2
3
4
5
6
//下一个元素返回的索引
int cursor;
//遍历上个元素的索引 如果没有则返回-1
int lastRet = -1;
//当前修改次数(参考ArrayList的modCount属性)
int expectedModCount = modCount;

构造方法

1
无

方法

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
//判断是否还有下一个
public boolean hasNext() {
    //通过判断下一个下标是否为数组大小即可得出结果
    return cursor != size;
}
//检查当前Itr修改次数和ArrayList是否一致，不一致则抛异常(并发异常) ps:final是防止子类覆盖此方法(ListItr)
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}
//获取下一个元素
public E next() {
    //检查修改次数是否一致
    checkForComodification();
    //定义i为下个元素的下标
    int i = cursor;
    //下标判断
    if (i >= size)
        throw new NoSuchElementException();
    //定义elementData为ArrayList的数组
    Object[] elementData = ArrayList.this.elementData;
    //再次下标判断，此次判断不一致则说明数组修改过，抛出异常(并发异常)
    //可能出现的场景1.ArrayList的remove()方法中中elementData[--size] = null，size--之前进入了此方法
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    //定义下个元素的下标
    cursor = i + 1;
    //将lastRet定义为下个元素的下标(返回的最后一个元素的下标)，返回该下标对应的值
    return (E) elementData[lastRet = i];
}
//移出当前元素
public void remove() {
    //如果无当前遍历元素则抛出异常
    if (lastRet < 0)
        throw new IllegalStateException();
    //检查修改次数是否一致
    checkForComodification();

    try {
        //调用ArrayList的remove方法(如果在遍历外remove会导致Itr中的expectedModCount没有修改抛异常)
        ArrayList.this.remove(lastRet);
        //定义下一个元素的下标为当前下标
        cursor = lastRet;
        //定义上个遍历下标为-1
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

#private class ListItr extends Itr implements ListIterator {}

简介

继承Itr的顺序遍历，自己封装的逆序遍历
逆序遍历是从构造方法传参的下标开始往上遍历(默认的构造方法传参为0，无法逆序遍历)
可以说ListItr存在的意义就是逆序遍历、set()和add()，如果不使用逆序遍历完全可以使用Itr

1
private class ListItr extends Itr implements ListIterator<E> {}

属性

1
继承Itr

##构造方法(参数一般为数组的长度)

1
2
3
4
ListItr(int index) {
        super();
        cursor = index;
}

方法

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
//是否拥有上一个元素
public boolean hasPrevious() {
    return cursor != 0;
}
//下一个元素下标
public int nextIndex() {
    return cursor;
}
//上一个元素下标
public int previousIndex() {
    return cursor - 1;
}
//获取上一个元素
public E previous() {
    //检查修改次数是否一致
    checkForComodification();
    //定义i为上个元素的下标
    int i = cursor - 1;
    //下标判断
    if (i < 0)
        throw new NoSuchElementException();
    //定义elementData为ArrayList的数组
    Object[] elementData = ArrayList.this.elementData;
    //可能出现的场景1.ArrayList的remove()方法中中elementData[--size] = null，size--之前进入了此方法
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    //定义上个元素的下标
    cursor = i;
    return (E) elementData[lastRet = i];
}
//为当前下标重新赋值
public void set(E e) {
    if (lastRet < 0)
        throw new IllegalStateException();
    //检查修改次数是否一致
    checkForComodification();

    try {
        //调用ArrayList的set方法(如果在遍历外set会导致Itr中的expectedModCount没有修改抛异常)
        ArrayList.this.set(lastRet, e);
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}
//为当前下标后增加值
public void add(E e) {
    //检查修改次数是否一致
    checkForComodification();

    try {
        int i = cursor;
        //调用ArrayList的add方法(如果在遍历外add会导致Itr中的expectedModCount没有修改抛异常)
        ArrayList.this.add(i, e);
        cursor = i + 1;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

总结

1
2
3
1.在Iterator遍历时，对list进行set操作并不会抛出异常，也就是说存在脏数据问题
2.ListItr在Itr的基础上增加了逆序遍历、set()和add()
3.在遍历时对ArrayList的add和remove操作应该使用Itr或者其子类完成，防止出现ConcurrentModificationException
源码 > jdk
#源码 #jdk
ArrayList源码分析
https://gallrax.github.io/2018/01/16/ArrayList源码分析/
作者
Gallrax
发布于
2018年1月16日
许可协议