java.util.ArrayList类解析

ArrayList 是一个用数组实现的集合,支持随机访问,元素有序且可以重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 实现 List 接口
* 这个接口是 List 类集合的上层接口,定义了实现该接口的类都必须要实现的一组方法
* 实现 RandomAccess 接口
* 这是一个标记接口,一般此标记接口用于 List 实现,
* 以表明它们支持快速(通常是恒定时间)的随机访问。
* 该接口的主要目的是允许通用算法改变其行为,
* 以便在应用于随机或顺序访问列表时提供良好的性能
* 实现 Cloneable 接口
* 这个类是 java.lang.Cloneable,前面我们讲解深拷贝和浅拷贝的原理时,
* 我们介绍了浅拷贝可以通过调用 Object.clone() 方法来实现,
* 但是调用该方法的对象必须要实现 Cloneable 接口,
* 否则会抛出 CloneNoSupportException异常。
* 实现 Serializable 接口
* 序列化
*/
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
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* 默认初始大小.
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 用于空实例的共享空数组实例。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 共享空数组实例,用于默认大小的空实例。我们将其与空元素数据区分开来,
* 以了解添加第一个元素时要加多少量。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 存储集合元素的数组缓冲区。集合的容量是这个数组缓冲区的长度。
* 任何带有elementdata==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空集合
* 将在添加第一个元素时扩展为默认容量。
*/
transient Object[] elementData;

/**
* 集合大小
*/
private int size;

构造函数

1
2
3
4
5
6
7
/**
* Constructs an empty list with an initial capacity of ten.(构造初始容量为10的空列表。)
* 明明说是10,其实看代码只是创建了一个空数组,应该是版本更新忘了改注释了。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
* 构造具有指定初始容量的空列表
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 按照集合迭代器返回元素的顺序构造包含指定集合的元素的列表。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

方法

add

1
2
3
4
5
6

public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

看看ensureCapacityInternal方法

1
2
3
 private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

再看看calculateCapacity,可以看到当elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA时,也就是这是new ArrayList后第一次加进元素的话,就会返回初始容量10,后面根据这个新建一个10容量的数组

1
2
3
4
5
6
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

ensureExplicitCapacity是干嘛的呢,是确保数组可用,如果容量不够,就要进行扩容了,也就是grow方法

1
2
3
4
5
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

看看grow方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 /**
* 增加容量以确保它至少能容纳最小容量参数指定的元素数。一般是扩容1.5倍
*/
private void grow(int minCapacity) {
// 现在数组的容量
int oldCapacity = elementData.length;
// 扩容1.5倍的容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果1.5倍容量小于minCapacity,那把minC赋值给newC
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果1.5倍容量大于MAX_ARRAY_SIZE(int最大值 - 8)
if (newCapacity - MAX_ARRAY_SIZE(0x7fffffff - 8) > 0)
// hugeCapacity是这样的,minC > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE : MAX_ARRAY_SIZE;
newCapacity = hugeCapacity(minCapacity);
// 这里用到数组复制的方法,扩容到指定大小
elementData = Arrays.copyOf(elementData, newCapacity);
}

clear

1
2
3
4
5
6
7
8
9
10
 // 就是清空数组,也就是清空集合
public void clear() {
modCount++;

// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

clone

1
2
3
4
5
6
7
8
9
10
11
12
13
 // 克隆集合。。
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}

}

contains

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// // 从前面开始遍历,返回第一个与o相等的下标,不存在返回-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++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

get

1
2
3
4
5
6
7
// 根据下标值获取对应元素
public E get(int index) {
// 检查是否超过最大下标值
rangeCheck(index);
// 就是 elementData[index]
return elementData(index);
}

iterator

1
2
3
4
// 返回的是一个内部类 Itr,Itr这里就不做多解释了,有兴趣可以自己去看。
public Iterator<E> iterator() {
return new Itr();
}

lastIndexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
// 从后面开始遍历,返回第一个与o相等的下标,不存在返回-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;
}

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 移除指定下标的元素,可以看到是用System.arraycopy来实现对移除元素后数组进行重新组合,让其他元素位置不变
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; // clear to let GC do its work

return oldValue;
}

还有一个根据元素值来移除的,就是遍历数组,找到下标,移除,也是用System.arraycopy来实现

removeAll

1
2
3
4
5
// 从此列表中删除指定集合中包含的所有元素。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
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
// 核心还是用到了System.arraycopy
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++)
// complement等于false,也就是c不包含的元素,重新从下标0赋值到elementData
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
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;
}

set

1
2
3
4
5
6
7
8
// 设值。。
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

sort

1
2
3
4
5
6
7
8
9
// 对elementData进行排序,用Arrays.sort实现
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}

subList

1
2
3
4
5
// 截取指定访问的元素到SubList.,也就是生成新的集合吧
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}

toArray

1
2
3
4
// 转换成size大小的数组。。。
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
1
2
3
4
5
6
7
8
9
10
// 还可以指定转换的类型
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

trimToSize

1
2
3
4
5
6
7
8
9
// 把数组转换成size大小的数组
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}