简介

ArrayList可以说是我们最常用的一种集合了。

他的本质是一个数组,一个可以自动扩容的动态数组线程不安全允许元素为null

由于数组的内存连续,可以根据下标以O(1)的时间读写元素,因此时间效率很高。

内部属性

我们先来看下ArrayList里面有哪几个属性:

  • private static final long serialVersionUID = 8683452581122892189L;
    序列话UID。由于ArrayList实现了Serializable接口,为了序列化和反序列化的方便,我们就手动为他添加一个序列化UID。

  • private static final int DEFAULT_CAPACITY = 10;
    默认的容量。

  • private static final Object[] EMPTY_ELEMENTDATA = {};
    空数组。

  • private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    默认的空数组。

  • transient Object[] elementData;
    真正存放元素的数组。

  • private int size;
    当前元素个数。

构造方法

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
// 传入参数为初始化容量时的构造方法
public ArrayList(int initialCapacity) {

if (initialCapacity > 0) {
// 如果传入参数大于零,那就创建一个对应大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果传入参数等于0,那就直接把属性中创建好的空数组复制
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 如果传入参数小于0,那就抛异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

// 传入参数为空时的构造方法
public ArrayList() {
// 将属性中创建好的空数组复制过来
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 传入参数为数组时的构造方法
public ArrayList(Collection<? extends E> c) {
// 先转换为数组
elementData = c.toArray();
// 因为size代表ArrayList中元素个数,所以要把数组的长度赋过来
// 如果个数不为0进入此if
if ((size = elementData.length) != 0) {
//这里是当c.toArray出错,没有返回Object[]时,利用Arrays.copyOf 来复制集合c中的元素到elementData数组中
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果个数为0,那就把属性中的空数组复制过来
this.elementData = EMPTY_ELEMENTDATA;
}
}

常用API

ArrayList # add(E e)

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
public boolean add(E e) {
// ->> 分析4.1.1
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将需要加入的元素加到最后面
elementData[size++] = e;
return true;
}

/**
* 分析4.1.1 ensureCapacityInternal()
*/
private void ensureCapacityInternal(int minCapacity) {
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个变量只有在通过无参构造的时候用到过
// 也就是说,他判断创建出来的这个数组,到底是不是无参构造方法创建出来的,如果是就找出DEFAULT_CAPACITY和minCapacity中较大的那个
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 但是按道理来说,add一个元素minCapacity肯定为1,肯定小于DEFAULT_CAPACITY,为什么还要做一个判断呢?
// 但是你得注意,还有AddAll这个方法
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

// ->> 分析4.1.2
ensureExplicitCapacity(minCapacity);
}

/**
* 分析4.1.2 ensureExplicitCapacity()
*/
private void ensureExplicitCapacity(int minCapacity) {
// modCount是AbstractList中的属性,如果需要扩容,则会修改modCount
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
// ->> 分析4.1.3
grow(minCapacity);
}

/**
* 分析4.1.3 grow()
* 作用:扩容
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容为原数组的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果还不够,就直接用能容纳的最小大小
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
// 如果新数组比MAX_ARRAY_SIZE还要大的话
if (newCapacity - MAX_ARRAY_SIZE > 0)
// ->> 分析4.1.4
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually clos2019e to size, so this is a win:
// 生成新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
* 分析4.1.4
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

ArrayList # add(E e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 按给定的位置添加指定元素
public void add(int index, E element) {
// 如果给的位置超过了集合已存放的元素的个数或者小于0,就抛异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

// ->> 分析4.1.1
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将elementData从index处分开,给index空出位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 放入数据
elementData[index] = element;
size++;
}

ArrayList # addAll(Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
public boolean addAll(Collection<? extends E> c) {
// 转为数组
Object[] a = c.toArray();
int numNew = a.length;
// 扩容数组 ->> 分析4.1.1
ensureCapacityInternal(size + numNew); // Increments modCount
// 将a数组的全部内容添加到elementData数组从size开始之后
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

ArrayList # addAll(int index, Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

// 转为数组
Object[] a = c.toArray();
int numNew = a.length;
// 扩容 ->> 分析4.1.1
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
// 如果index小于size,也就是说需要在原数组的中间插入的haul,就需要先把原数组index之后的数据往后移动
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);

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

总结

  • 无论是add还是addAll,都是先判断是否越界,如果越界就扩容,然后再移动数组
  • 如果需要扩容,默认扩容原来的一般大小;如果还不够,那就直接将目标的size作为扩容后的大小
  • 在扩容成功后,会修改modCount

ArrayList # remove(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 修改modCount
modCount++;
// 将要删除的内容先保存下来
E oldValue = (E) elementData[index];

int numMoved = size - index - 1;
// 判断要删除的数据是不是最后一位
// 如果不是最后一位,还得先把后面的数据往前移动
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 清除数据,更改引用,让GC去清理
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

ArrayList # 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
27
28
29
30
31
32
33
34
35
36
37
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// ->> 分析4.2.1
fastRemove(index);
return true;
}
} else {
// 如果参数不为空,那就遍历整个数组集合
for (int index = 0; index < size; index++)
// 找到和参数相等的那一位,然后将该位移除
if (o.equals(elementData[index])) {
// ->> 分析4.2.1
fastRemove(index);
return true;
}
}
return false;
}

/**
* 分析4.2.1:fastRemove()
* 作用:基本上和remove(int index)一样
*/
private void fastRemove(int index) {
// 修改modCount
modCount++;
int numMoved = size - index - 1;
// 判断要删除的数据是不是最后一位
// 如果不是最后一位,还得先把后面的数据往前移动
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 清除数据,更改引用,让GC去清理
elementData[--size] = null; // clear to let GC do its work
}

ArrayList # removeAll(Collection<?> c)

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
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
// ->> 分析4.2.2
return batchRemove(c, false);
}

/**
* 分析4.2.2 batchRemove()
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
// 先赋值
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
// 快速保存两个集合共有元素
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
// 如果出现异常会导致r!=size,就把异常之后的数据全部覆盖到数组里面
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
// 将后面的元素全部置空,让GC来回收
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}

这块我看的时候有点绕,但是一想通就好了。

其实这个地方是要把C集合中和原集合中共有的元素删除,那我就只需要遍历原数组,然后碰到和C集合相同的元素就直接放到前面去,然后等遍历完成后,一次性把后面的全部置空。

ArrayList # retainAll(Collection<?> c)

1
2
3
4
5
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
// ->> 分析4.2.2
return batchRemove(c, true);
}

ArrayList # clear()

1
2
3
4
5
6
7
8
9
10
public void clear() {
modCount++;

// clear to let GC do its work
// 直接遍历每一位,然后把每一位都置空,让GC去清理
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

总结

  • 所有的删除操作都会修改modCount

1
2
3
4
5
6
7
8
9
10
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

// 取出原来的元素
E oldValue = (E) elementData[index];
// 把需要更改的数据放进去
elementData[index] = element;
return oldValue;
}

没啥好分析的

不需要修改modCount,相对高效

1
2
3
4
5
6
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

return (E) elementData[index];
}

没啥好分析的

不需要修改modCount,相对高效

包括 contains() & indexOf()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean contains(Object o) {
// ->> 分析4.5.1
return indexOf(o) >= 0;
}

/**
* 分析4.5.1:indexOf()
*/
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++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

没啥好分析的

判空 isEmpty()

1
2
3
public boolean isEmpty() {
return size == 0;
}

没啥好分析的

迭代器 Iterator

创建迭代器

1
2
3
4
public Iterator<E> iterator() {
// 构造Itr对象并返回
return new Itr();
}

Itr属性

1
2
3
4
5
6
7
8
9
// 限制,也就是数组的元素个数
protected int limit = ArrayList.this.size;

// 下一个元素的下标
int cursor; // index of next element to return
// 上一次返回元素的下标
int lastRet = -1; // index of last element returned; -1 if no such
// 用于判断集合是否修改过结构的标志
int expectedModCount = modCount;

Itr # hasNext()

1
2
3
public boolean hasNext() {
return cursor < limit;
}

不用多说

Itr # next()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public E next() {
// 判断是否修改过List的结构,如果修改了就抛异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
int i = cursor;
// 如果越界了就抛异常
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
// 再次判断是否越界,在 我们这里的操作时,有异步线程修改了List
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 标记加1
cursor = i + 1;
// 返回数据,并设置上一次的下标
return (E) elementData[lastRet = i];
}

Itr # remove()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();

try {
// 调用ArrayList的remove方法移除数据
ArrayList.this.remove(lastRet);
// 更新一系列数据
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
limit--;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

总结

modCount到底是个什么东西?

如果你看过很多集合源码的话,你就会发现你会在很多地方都会碰到这个modCount,例如ArrayList、LinkedList、HashMap等等。modCount字面意思就是修改次数,那么为什么需要纪录这个修改次数呢?

你回想下,似乎用到modCount的地方,如ArrayList、LinkedList等等,他们都用一个共性——线程不安全。

而在你看了这几个类的迭代器后就会发现,他们迭代器中一定有一个属性(如我们上面的expectedModCount)初始化时的值就是modCount的值。

然后在迭代器的方法中,只要是遍历这个集合的时候,都需要将两个值进行对比,然后再移除元素的时候,都需要更新迭代器里面的modCount变量。

这时,你需要了解下Fail-Fast机制

我们都知道这些集合是线程不安全的,如果在使用迭代器的过程中,有其他线程对集合进行了修改,那么就会抛出ConcurrentModificationException异常,这就是Fail-Fast策略。而这个时候源码中就通过modCount进行了操作。迭代器在创建时,会创建一个变量等于当时的modCount,如果在迭代过程中,集合发生了变化,modCount就是++。这时迭代器中的变量的值和modCount不相等了,那就抛异常。

所以,遍历线程不安全的集合时,尽量使用迭代器

解决办法:

  • 在遍历过程中所有涉及到改变 modCount 值得地方全部加上 synchronized 或者直接使用 Collections.synchronizedList,这样就可以解决。但是不推荐,因为增删造成的同步锁可能会阻塞遍历操作。
  • 使用 CopyOnWriteArrayList 来替换 ArrayList。推荐使用该方案。关于CopyOnWriteArrayList的内容此处不再过多的去将,想了解的同学可以百度或者谷歌。

ArrayList和Vector的区别

  • ArrayList线程不安全,Vector线程安全
  • 扩容的时候ArrayList默认扩容1.5倍,Vector默认扩容1倍