Java 源码--ArrayList

ArrayList类继承了AbstractList抽象类,AbstractList抽象类对于一些通用的方法提供了默认实现。ArrayList类实现了接口List、RandomAccess、Cloneable和Serializable。后三者都是语义标志接口,不提供任何实现,标记这个类具有某种功能。RandomAccess标记类具有随机访问的功能,Cloneable标记类具有克隆功能,Serializable标记类具有序列化功能。

ArrayList类底层是由数组实现的,使用一个Object[]类型的变量来保存这个list的值。这个值不参与序列化,类中重写了writeObject()和readObject()方法来序列化该值。

1
transient Object[] elementData;

变量size记录值的大小。

1
private int size;

ArrayList有两个构造方法——有参构造方法和无参构造方法。

无参构造时,将数组列表的值赋为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

1
2
3
4
5
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

有参构造时,指定容量大于0,就构造一个指定容量大小的数组,如果指定容量为0,就将值赋为EMPTY_ELEMENTDATA。

1
2
3
4
5
6
7
8
9
10
11
12
private static final Object[] EMPTY_ELEMENTDATA = {};

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);
}
}

也可以根据一个集合构造一个数组集合,将集合转为数组直接赋值给elementData。当值大小为0时,就将值赋为EMPTY_ELEMENTDATA。

1
2
3
4
5
6
7
8
9
10
11
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;
}
}

那么,无参构造和有参构造产生的空值有什么区别呢?从表面上看来是一样的,在变量elementData上有这样一句注释,“ 添加第一个元素时,任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。”

DEFAULT_CAPACITY指定为10。

1
private static final int DEFAULT_CAPACITY = 10;

注释的意思是说,无参构造产生的空值在第一次添加元素时,将容量扩展至10。那么我们来看下add方法。

add方法首先将数组容量加1,这就涉及到了ArrayList的扩容机制,我们一步步来看。

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

首先,判断目前数组的值是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,即该数组是不是无参构造出的空数组。如果是,就取DEFAULT_CAPACITY和minCapacity的最大值,否则就扩展至指定的容量。第一次添加元素时,minCapacity为1,也就是说将数组扩展至10,如果是有参构造的空数组,就扩展至1。

1
2
3
4
5
6
7
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

接下来要判断扩展的容量是否足够存放数组的值,足够存放就开始扩容工作。第一次添加元素时,数组长度为0,可以进入扩容工作。

1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

grow方法是ArrayList扩容机制的核心,可以看出,扩容的机制是扩展原来容量的0.5倍。如果扩容至1.5倍之后依旧无法达到指定容量大小或者大小超出了int类型的大小,就使用指定容量进行扩容。如果扩容容量大于数组最大容量,就扩容至Integer类型的最大值。最后重新申请一个数组,并进行数组的复制完成扩容工作。当第一次添加元素时,就数组的容量为0,扩容至1或10。

这里有一个疑问,既然ArrayList是数组来保存值的,数组的容量最大是Integer.MAX_VALUE - 8(查资料说是需要空间来保存一些头部信息),那么为什么ArrayList的容量还可以扩大至Integer.MAX_VALUE呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

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

由此可以看出,EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是为了区分有参构造和无参构造的空数组,从而使用不同的扩容规则。

我们可以注意到,上面方法中有一个modCount变量加1的操作。这个变量是从父类AbstractList中继承来的,它标记一个list被修改的次数。它主要是为了在迭代器中判断list是否被其他操作改变,进入迭代器会保存一个modCount值的副本,如果modCount的值变了,就抛出异常。

1
protected transient int modCount = 0;

方法trimToSize将数组中多余容量释放。当使用容量小于数组容量时,如果使用容量为0,将数组设为空值,否则重新生成一个长度为size的数组。

1
2
3
4
5
6
7
8
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

size方法可以获取list的大小。

1
2
3
public int size() {
return size;
}

isEmpty方法判断list是否为空,即size是否为0.

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

contains方法判断数组是否包含参数。如果参数o在数组的位置不小于0,就说明数组中存在参数。

1
2
3
public boolean contains(Object o) {
return indexOf(o) >= 0;
}

indexOf方法判断参数在数组中的位置。如果参数o为null,那么在数组中找到一个null值的位置就好,不为空就是用equals方法找到数组中o的位置,找不到就返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

lastIndexOf方法从后往前遍历,判断参数在数组中的位置。

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

clone方法克隆一个list。注意,该克隆是浅克隆,数组元素并没有复制。

1
2
3
4
5
6
7
8
9
10
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);
}
}

toArray方法将list转为数组。如果参数a的长度不够容纳list元素,就重新生成一个数组,否则就直接复制元素。a中有空余位置的话将size位置置为null。

1
2
3
4
5
6
7
8
9
10
11
12
13
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

get方法返回指定位置的元素。首先检查index是否越界,然后返回数组index位置的元素。

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

return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}

private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

set方法设置指定位置的元素。首先检查index是否越界,然后拿到index位置的旧值,将index位置的值设为新值,最后返回旧值。

1
2
3
4
5
6
7
public E set(int index, E element) {
rangeCheck(index);

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

add方法向list中添加元素。不指定元素添加位置时默认添加到数组末尾,首先确保数组的容量,然后在数组后面添加一个元素,最后返回true。指定元素添加位置时,首先检查指定位置是否越界,然后确保数组的容量,然后将index以及之后的元素向后移动一位,将index位置设为指定元素,最后返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

remove方法移除指定位置的元素或移除指定元素。当指定的是元素位置时,先检查指定位置是否越界,然后获取指定位置的旧值,将指定位置之后的元素向前移动一个位置,然后将最后一位设为null,最后返回旧值。当指定的是元素时,就先判断元素的位置,移除那个位置元素,最后返回布尔值。

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
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;
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)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
}

clear方法清除list中的元素。将数组中的每个元素设为null,并将大小设为0。

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

for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

addAll方法向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
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);

int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);

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

removeAll方法移除指定集合中的所有元素,retainAll方法保留指定集合中的所有元素。这两个方法类似,只是逻辑是反的,Java设计者很巧妙的运用了一个boolean类型的参数来区分两种逻辑,以便使同一个方法。在try中的for循环就已经将需要留下的元素放到了数组的前一部分,即w位置之前。注释说contains方法可能会有异常,当异常发生,就将没有遍历到的元素全部留下,这个逻辑我也不太明白。最后将w位置之后的元素设为null,返回布尔值。

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

public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}

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 {
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}

forEach方法可以使用lambda表达对每一个元素进行相同的操作。在操作之前,会先拿到数组修改的次数,然后重新申请一个与list数组元素相同的数组进行操作。注意,此复制是浅复制,两个数组共用一套元素。最后判断list是否被其他操作改变了,如果被改变了就抛出异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

removeIf方法移除掉满足参数条件的元素。首先将满足参数条件的元素的位置放到一个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
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}

final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null;
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}

return anyToRemove;
}

replaceAll方法对数组的每个元素执行传入方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}

sort方法使用传入的比较方法对数组进行排序。

1
2
3
4
5
6
7
8
9
10
@Override
@SuppressWarnings("unchecked")
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++;
}

ArrayList拥有自己的两种迭代器,Itr和ListItr。

Itr实现了接口Iterator,定义了三个变量,cursor,代表下一个元素的位置,lastRet,代表上一个元素的位置,expectedModCount,数组之前的修改次数。

1
2
3
int cursor;       
int lastRet = -1;
int expectedModCount = modCount;

Itr迭代器有4个方法,hasNext(),next(),remove(),forEachRemaining()。

hasNext方法判断可以向后迭代。

1
2
3
public boolean hasNext() {
return cursor != size;
}

next方法返回下一个元素,并将cursor和lastRet向前移动一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
@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];
}

remove方法移除掉上一个遍历过的元素,并将cursor指向上一个元素的位置,将lastRet设为-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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();
}
}

forEachRemaining方法遍历所有剩下的元素。在使用Iterator迭代器使用next方法循环list,如果没有循环完整个list,可以使用该方法循环完整个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
@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();
}

ListItr继承了Itr类,实现了接口ListIterator。除了提供了一个构造方法之外,还添加了向前遍历的方法。

ListItr的构造方法可以为迭代器指定开始迭代的位置。

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

hasPrevious方法判断是否可以向前迭代。

1
2
3
public boolean hasPrevious() {
return cursor != 0;
}

nextIndex方法返回下一个迭代元素的位置。

1
2
3
public int nextIndex() {
return cursor;
}

previousIndex方法返回前一个迭代元素的位置。

1
2
3
public int previousIndex() {
return cursor - 1;
}

previous方法返回前一个迭代的元素。

1
2
3
4
5
6
7
8
9
10
11
12
@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];
}

set方法设置上一个遍历过的元素值为e。

1
2
3
4
5
6
7
8
9
10
11
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

add方法向cursor位置添加一个元素,并将cursor指向下一个位置,将lastRet设为-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
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();
}
}

接下来就是一个子列表SubList。

SubList继承AbstractList抽象类,实现RandomAccess接口,有四个属性,在构造方法中可以看出这四个属性的意义。

1
2
3
4
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;

parent就是母列表,parentOffset是母列表的偏移,offset是子列表相对于母列表的偏移,size是子列表的大小,同时记录了母列表被修改的次数。

1
2
3
4
5
6
7
8
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}

SubList提供了列表简单的操作 ,set,get,size,add,remove,removeRange,addAll,iterator,listIterator等方法。注意,这些方法虽然在子列表调用的,但是都是直接操作母列表对应位置的元素的。比如set方法,会去修改母列表元素offset+index位置的元素的值。

1
2
3
4
5
6
7
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}

ArrayList使用subList方法返回列表的子列表。注意,如果修改子列表的元素,母列表的元素也会被修改。

1
2
3
4
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}

最后,ArrayList还有一个内部类ArrayListSpliterator,这个以后再研究吧,目前有些看不懂。

-------------本文结束感谢您的阅读-------------

本文标题:Java 源码--ArrayList

文章作者:huihui

发布时间:2019年02月14日 - 19:02

最后更新:2019年02月14日 - 19:02

原始链接:http://101.200.47.120:8011/2019/02/14/Java 源码--ArrayList/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。