ArrayList是List接口的 可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。ArrayList继承自 AbstractList,这是一个抽象类对一些基础的list操作做了一些封装.实现了RandomAccess 标记接口,表明可以实现快速随机访问.实现了Cloneable接口的实现表示该容器具有Clone函数操作,Serializable是序列化。

每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的大小,就可在构造ArrayList实例时指定其容量。

在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。

注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。

ArrayList这个数据结构比较简单,总体来说,ArrayList底层结构是数组,他的很多方法都是从数组上面演变而来的。

下面我们先来看一下ArrayList中的一些初始值

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
//通过ArrayList实现的接口可知,其支持随机访问,能被克隆,支持序列化
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//序列版本号
private static final long serialVersionUID = 8683452581122892189L;
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//被用于默认大小的空实例的共享数组实例。
//与EMPTY_ELEMENTDATA的区别是:当我们向数组中添加第一个元素时,知道数组该扩充多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Object[]类型的数组,保存了添加到ArrayList中的元素。ArrayList的容量是该Object[]类型数组的长度
* 当第一个元素被添加时,任何空ArrayList中的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA将会被
* 扩充到DEFAULT_CAPACITY(默认容量)。
*/
transient Object[] elementData; //没有被私有化是为了简化内部类访问
// ArrayList的大小(指其所含的元素个数)
private int size;

// 记录被修改的次数
protected transient int modCount = 0;

// 数组的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
}

elementData 是”Object[] 类型的数组”,它保存了添加到ArrayList中的元素。实际上,elementData是个动态数组,我们能通过构造函数 ArrayList(intinitialCapacity)来执行它的初始容量为initialCapacity;如果通过不含参数的构造函数ArrayList()来创建ArrayList,则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长。

构造函数

ArrayList提供了三种方式的构造器。可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表。

这些元素按照该collection的迭代器返回的顺序排列的。

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(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);
}
}
// 构造一个默认初始容量为10的空列表
public ArrayList() { //这里并没有初始化,jdk 1.8之后是在进行add操作后初始化
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回的顺序排列的
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray()可能不会正确地返回一个 Object[]数组,那么使用Arrays.copyOf()方法
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else { // 如果指定的collection为空
this.elementData = EMPTY_ELEMENTDATA;
}
}

使用无参构造器,默认初始容量为什么是10?

  1. 初始时:this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; size = 0;
  2. 向数组中添加第一个元素时,add(E e)方法中调用了ensureCapacityInternal(size + 1)方法,即ensureCapacityInternal(1);
  3. 在ensureCapacityInternal(int minCapacity)方法中,minCapacity=DEFAULT_CAPACITY=10,然后再调用ensureExplicitCapacity(minCapacity)方法,即ensureExplicitCapacity(10);
  4. 在ensureExplicitCapacity(minCapacity)方法中调用grow(minCapacity)方法,即grow(10),此处为真正具体的数组扩容的算法,在此方法中,通过elementData = Arrays.copyOf(elementData, 10)具体实现了elementData数组初始容量为10的构造。

添加元素

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
// 在数组末尾加上一个元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 进行扩容检查
elementData[size++] = e;
return true;
}

// 在数组的指定位置添加元素
public void add(int index, E element) {
rangeCheckForAdd(index); // 检查index是否越界
ensureCapacityInternal(size + 1); // 进行扩容检查

// 对数据进行复制操作,空出index位置,并插入element,将源数组中从index位置开始后的size-index个元素统一后移一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++; // 元素个数加1
}

// 按照指定collection集合的迭代器所返回的元素顺序,将该collection中的所有元素添加到列表的尾部
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); // 将collection转换为数组类型
int numNew = a.length; // collection中的元素个数
ensureCapacityInternal(size + numNew); // 进行扩容检查
System.arraycopy(a, 0, elementData, size, numNew); // 将数组a[0,...,numNew-1]复制到数组elementData[size,...,size+numNew-1]
size += numNew;
return numNew != 0;
}

// 按照指定collection集合的迭代器所返回的元素顺序,将该collection中的所有元素添加到列表的指定位置
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index); // 检查index是否越界
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 进行扩容检查
// 将数组elementData[index,...,index+numMoved-1]复制到elementData[index+numMoved,...,index+2*numMoved-1]
//将源数组中从index位置开始的后numMoved个元素统一后移numNew位
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 将数组a[0,...,numNew-1]复制到数组elementData[index,...,index+numNew-1]完成数据的插入
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 用于自定义设置ArrayList的容量
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
// 进行扩容检查
private void ensureCapacityInternal(int minCapacity) {
//第一次add操作初始化,如果为空ArrayList,那么初始化容量为10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//判断是否需要扩容
ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
//modCount这个参数运用到了 fail-fast 机制
modCount++;

if (minCapacity - elementData.length > 0)
grow(minCapacity); // 扩容
}
// 扩容
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//newCapacity为以前的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断容量是否到达long int 最大临界值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 对数组进行复制处理
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 检查是否超过最大容量 0x7fffffff ,是否抛出异常
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_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
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
// 删除指定位置的元素
public E remove(int index) {
rangeCheck(index); //数组越界检查
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1; //计算数组需要复制的数量
if (numMoved > 0) //将index后的数据都向前移一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //help GC
return oldValue;
}
// 删除指定内容的元素(只删除第一个匹配成功的)
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;
}
//找到对应的元素后,删除。删除元素后的元素都向前移动一位
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0) // 将index后面的元素整体向前移动一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // help GC
}
//清空ArrayList,将全部的元素设为null
public void clear() {
modCount++;
for (int i = 0; i < size; i++) // help GC
elementData[i] = null;
size = 0;
}
//删除ArrayList中从fromIndex到toIndex(区间--左闭右开)之间所有的元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex; //需向前移动的元素的个数
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// help GC
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
//删除ArrayList中包含在指定容器c中的所有元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c); //检查指定的对象c是否为空
return batchRemove(c, false);
}
//移除ArrayList中不包含在指定容器c中的所有元素,与removeAll(Collection<?> c)正好相反
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c); //检查指定的对象c是否为空
return batchRemove(c, true);
}
// 根据complement的值删除元素
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0; //读写双指针 w是重新存元素时的索引,r是原来的索引
boolean modified = false;
try {
//遍历数组,并检查这个集合是否包含对应的值,移动要保留的值到数组前面,w最后值为要保留的元素的数量
//简单点:若保留,就将相同元素移动到前段;若删除,就将不同元素移动到前段
for (; r < size; r++)
if (c.contains(elementData[r]) == complement) //判断指定容器c中是否含有elementData[r]元素
elementData[w++] = elementData[r];
}finally {//确保异常抛出前的部分可以完成期望的操作,而未被遍历的部分会被接到后面
//r!=size表示可能出错了:c.contains(elementData[r])抛出异常
if (r != size) {
System.arraycopy(elementData, r,elementData, w,size - r);
w += size - r;
}
//如果w==size:表示全部元素都保留了,所以也就没有删除操作发生,所以会返回false;反之,返回true,并更改数组
//而w!=size的时候,即使try块抛出异常,也能正确处理异常抛出前的操作,因为w始终为要保留的前段部分的长度,数组也不会因此乱序
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;//改变的次数
size = w; //新的大小为保留的元素的个数
modified = true;
}
}
return modified;
}

removeAll和retainAll方法:实现删除或保留ArrayList中包含Collection c中的的元素。

这两个方法都用到batchRemove方法(boolean complement使得batchRemove方法得到了重用)

下面以removeAll为例,分析batchRemove(c, false)
a. 遍历elementData
b. 如果集合c中包含elementData的元素e,即c.contains(elementData[r])为true,if不成立,if结束;如果c不包含elementData的元素e,则if成立,将此元素e赋值给elementData[w++] (即elementData保留了c中没有的元素,也就是删除了c中存在的所有元素。)
c. 执行finally
d. finally是不管try中结果如何都会执行的。if(r!=size),则将elementData未参加比较的元素arraycopy到elementData后面;新索引w加上刚arraycopy的数目;if (w != size),此时w还不等于size,则将w后的元素移除.只有执行了if (w != size)(事实上只要c中含有elementData的元素,w肯定不等于size),才令modified = true,才说明remove成功,返回true,否则返回false。

ArrayList中还有一个用于节约数组内存空间,缩小容量的方法

1
2
3
4
5
6
7
8
9
10
// 因为容量常常会大于实际元素的数量。内存紧张时,可以调用该方法删除预留的位置,调整容量为元素实际数量。
// 如果确定不会再有元素添加进来时也可以调用该方法来节约空间
public void trimToSize() {
modCount++;
// length是数组长度,size表示数组内元素个数
// size<length那么就说明数组内有空元素,进行缩小容量操作
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}

去掉预留元素的位置。返回一个新数组,新数组不含null,数组的size和elementData.length相等,以节省空间。此函数可避免size很小但elementData.length很大的情况。

ArrayList会每次增长会预申请多一点空间,1.5倍,这样就会出现当size() = 10的时候,ArrayList已经申请了15空间, trimToSize就是删除多余的5,只留10。

或许有人会有疑问:调用Arrays.copyOf复制size长度的元素到elementData,而且由源码看应该是从0复制到size处,那么如果我之前调用过add(int index, E element)呢?比如,list={1,2,3,null,null,4,null,null},如果调用trimToSize返回的应该是list={1,2,3,null}(因为size=4)。其实上面这种情况不会发生的,因为调用add(int index, E element)时,会检查index的合法性,所以list的元素肯定是相邻的,而不会出现上述这种中间出现null的情况。

修改元素

1
2
3
4
5
6
7
// 将指定位置的元素改为指定的值 
public E set(int index, E element) {
rangeCheck(index); // 检查index是否越界
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

查找元素

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
//判断ArrayList中是否包含Object(o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//返回一个值在数组首次出现的位置,会根据是否为null使用不同方式判断。不存在就返回-1。时间复杂度为O(N)
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;
}
//返回一个值在数组最后一次出现的位置,不存在就返回-1。时间复杂度为O(N)
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;
}
//返回指定位置的值,因为是数组,所以速度特别快
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
//返回指定位置的值,但是会检查这个位置数否超出数组长度
public E get(int index) {
rangeCheck(index);
return elementData(index); //实质上return (E) elementData[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
//保存数组实例的状态到一个流(即它序列化)。写入过程数组被更改会抛出异常
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
int expectedModCount = modCount;
s.defaultWriteObject(); //执行默认的反序列化/序列化过程。将当前类的非静态和非瞬态字段写入此流
// 写入大小
s.writeInt(size);
// 按顺序写入所有元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
//上面是写,这个就是读了。
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// 执行默认的序列化/反序列化过程
s.defaultReadObject();
// 读入数组长度
s.readInt();
if (size > 0) {
ensureCapacityInternal(size);
Object[] a = elementData;
//读入所有元素
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}

为什么要自定义序列化、反序列化机制呢?

保存元素的数组 elementData 使用 transient 修饰,该关键字声明数组默认不会被序列化。

1
transient Object[] elementData; // non-private to simplify nested class access

由于ArrayList实质上是一个动态数组,往往数组中会有空余的空间,如果采用默认的序列化机制,那些空余的空间会作为null写入本地文件或者在网络中传输,耗费了不必要的资源。所以,ArrayList使用自定义序列化机制,仅写入索引为【0,size)的有效元素以节省资源

序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法,原理类似。

1
2
3
ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);

迭代器

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
//返回ListIterator,开始位置为指定参数
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
//返回ListIterator,开始位置为0
public ListIterator<E> listIterator() {
return new ListItr(0);
}
//返回普通迭代器
public Iterator<E> iterator() {
return new Itr();
}
//通用的迭代器实现
private class Itr implements Iterator<E> {
int cursor; //游标,下一个元素的索引,默认初始化为0
int lastRet = -1; //上次访问的元素的位置
int expectedModCount = modCount;//迭代过程不允许修改数组,否则就抛出异常
//是否还有下一个
public boolean hasNext() {
return cursor != size;
}
//下一个元素
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//检查数组是否被修改
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1; //向后移动游标
return (E) elementData[lastRet = i]; //设置访问的位置并返回这个值
}
//删除元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();//检查数组是否被修改
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
cursor = i;
lastRet = i - 1;
checkForComodification();
}
//检查数组是否被修改
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
//ListIterator迭代器实现
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
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.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}

Iterator与ListIterator的区别:

  1. Iterator可以应用于所有的集合,Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型;
  2. Iterator只能实现顺序向后遍历,ListIterator可实现顺序向后遍历和逆向(顺序向前)遍历;
  3. Iterator只能实现remove操作,ListIterator可以实现remove操作,add操作,set操作。

其他方法

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
//返回ArrayList的大小(元素个数)
public int size() {
return size;
}
//判断ArrayList是否为空
public boolean isEmpty() {
return size == 0;
}
//返回此 ArrayList实例的浅拷贝(元素本身没有被复制,复制过程数组发生改变会抛出异常)
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
/*
浅克隆就是我们所看到的Arrays.copyOf, System.arraycopy,数组是新的,但是里面N个元素全是引用的旧的。
浅拷贝(影子克隆):只复制基本类型。
深拷贝(深度克隆):基本类+对象。
*/
//返回一个包含ArrayList中所有元素的数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// 返回一个数组,使用运行时确定类型,该数组包含在这个列表中的所有元素(从第一到最后一个元素)
// 返回的数组容量由参数和本数组中较大值确定
@SuppressWarnings("unchecked")
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;
}

ArrayList相关问题

Integer.MAX_VALUE - 8 这里为什么要减去8?

主要是考虑到不同的JVM,有的VM会在加入一些数据头,当扩容后的容量大于MAX_ARRAY_SIZE,我们会将最小需要容量和MAX_ARRAY_SIZE做比较,如果比它大, 只能取Integer.MAX_VALUE,否则是Integer.MAX_VALUE -8。这个是从jdk1.7开始才有的

jdk1.8的无参构造函数和之前版本的构造函数有什么区别?

1
2
3
4
5
6
7
8
9
10
11
12
13
jdk1.6
public ArrayList() {
this(10);
}
jdk1.7
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
jdk1.8
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

对比下可以看出:jdk1.6的无参构造方法(默认构造方法)构造的ArrayList的底层数组elementData大小(容量)默认为10;从1.7开始,无参构造方法构造的ArrayList的底层数组elementData大小默认为0。

java集合类在jdk1.7版本基本上都有一种改动:懒初始化。懒初始化指的是默认构造方法构造的集合类,占据尽可能少的内存空间(对于ArrayList来说,使用空数组来占据尽量少的空间,不使用null是为了避免null判断),在第一次进行包含有添加语义的操作时,才进行真正的初始化工作。

1.7开始的ArrayList,默认构造方法构造的实例,底层数组是空数组,容量为0,在进行第一次add/addAll等操作时才会真正给底层数组赋非empty的值。如果add/addAll添加的元素小于10,则把elementData数组扩容为10个元素大小,否则使用刚好合适的大小(例如,第一次addAll添加6个,那么扩容为10个,第一次添加大于10个的,比如24个,扩容为24个,刚好合适)

1.8版本,默认构造的实例这个行为没有改变,只是用的数组名字变了。

jdk1.6中扩容算法的缺陷

(由于jdk1.7和jdk1.8在扩容算法方面差别不大,所以下面没有严格区分)

1
2
3
4
5
6
7
8
9
10
11
12
13
jdk1.6
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}

从上面的代码可以看出jdk1.6的ensureCapacity方法只是简单进行了逻辑上的操作,没有过多考虑int型溢出的问题,从1.7开始对这个进行了完善。

而且没考虑入参minCapacity可能因为int溢出变为负数。这个方法可以外部手动调用,手动扩容传入负数这个肯定是应该拦截掉的。但是自动扩容会因为int溢出产生负数,碰到这种情况时应该特殊处理,而不是什么都不做,等着后面抛出一个ArrayIndexOutOfBoundsException。

还有就是下面这句代码会造成过早溢出

1
int newCapacity = (oldCapacity * 3)/2 + 1;

虽然上面这行代码和1.7开始的oldCapacity + (oldCapacity >> 1) 差不多,都是相当于1.5倍,但实际上是有区别的。

这里主要有两个区别

第一个区别是jdk1.6的乘除运算的数学结果比后面一个大1比如oldCapacity=10,1.6的算法得到16,1.7开始的算法得到15,这个影响不大;

第二个区别就是两者在数字比较大时运算结果不一样,比如oldCapacity=10^9,这个数和Integer.MAX_VALUE位数一样,用1.6的算法得到的会是错误的-647483647,用1.7的则是正确的1500000000,这时候明明可以1.5倍扩容,但是jdk1.6却用的是按需扩容。

ensureCapacity(称之为手动,是因为此方法是public的,可以外部手动调用)。在1.6版本是只有这个手动的方法,内部自动操作也是调用这个方法,1.7开始进行了区分,并且进一步改进了扩容操作。

  • 从1.7开始将内部扩容和外部可以调用的扩容方法分开了,通过源码可以看出:外部调用的手动扩容方法ensureCapacity要多一个判断条件 minCapacity > minExpand,这个判断条件拦截掉负数的minCapacity,这样调用内部扩容ensureCapacityInternal方法时,minCapacity一定是正数;内部扩容方法直接就用minCapacity - elementData.length > 0判断,此条件可以检测出int型溢出,碰到溢出最后会抛出一个OOM错误。jdk1.7用OOM,这比jdk1.6用ArrayIndexOutOfBoundsException更好,因为此时数组大小超出了虚拟机对数组的限制,虚拟机无法处理这种情况了,抛出一个ERROR是合理的。

  • 使用这行代码

1
newCapacity = oldCapacity + (oldCapacity >> 1);

这行代码不仅仅是使用位运算加快执行速度,上面说了,这种做法才是对的,是真正的1.5倍。不仅仅因为那一个大小的差别,更重要的是避免过早出现int溢出的情况,保证了内部自动扩容会尽量按规定的策略执行。同时整个扩容处理流程中多增加了几处if判断,对各种情况处理更加完善。

为什么ArrayList自动容量扩充选择扩充1.5倍?

这种算法构造出来的新的数组长度的增量都会比上一次大( 而且是越来越大) ,避免频繁newInstance 的情况。

为什么ArrayList 不适合频繁插入和删除操作?

由上面分析的增加删除方法可以看出在ArrayList中经常会调用 System.arraycopy 这个效率很低的操作来复制数组,所以导致ArrayList在插入和删除操作中效率不高。

RandomAccess接口

1
2
public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以,在我看来 RandomAccess 接口不过是一个标识罢了。标识什么? 标识实现这个接口的类具有随机访问功能。

binarySearch() 方法中,它要判断传入的 list 是否 RamdomAccess 的实例,如果是,调用indexedBinarySearch()方法,如果不是,那么调用iteratorBinarySearch()方法

1
2
3
4
5
6
7
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}

ArrayList 实现了 RandomAccess 接口, 而 LinkedList 没有实现。为什么呢?我觉得还是和底层数据结构有关!ArrayList 底层是数组,而 LinkedList 底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。,ArrayList 实现了 RandomAccess 接口,就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识,并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的!

评论