More
More
文章目录
  1. DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA
  2. trimToSize()
  3. ensureCapacity() –> ensureExplicitCapacity() –> grow() –> hugeCapacity()
  4. toArray()
  5. add()
  6. retainAll()
  7. iterator()
  8. listIterator()
  9. 说点什么
  10. 知识点

【java源码一带一路系列】之ArrayList、Vector

  |  

一路至此,风景过半。
ArrayList与Vector虽然名字各异,源码实现基本相同,除了Vector增加了线程安全。所以作者建议我们在不需要线程安全的情况下尽量使用ArrayList。下面看看在ArrayList源码中遇到什么有趣的事情。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA

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
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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;
}
}

区别:DEFAULTCAPACITY_EMPTY_ELEMENTDATA用于无参初始化;EMPTY_ELEMENTDATA用于指定容量为0时的初始化。

trimToSize()

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

去除扩容后未存放元素的预留空间,以size为基准。

ensureCapacity() –> ensureExplicitCapacity() –> grow() –> hugeCapacity()

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
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

预设容量(提前扩容),可提高初始化效率。扩容后比扩容前多了“oldCapacity >> 1”(即多了原来的50%)。同时注意溢出情况处理。(overflow-conscious code)。即“a-b<0”而不是”a<b”:

1
2
3
4
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE + 1;
System.out.println(a < b); // false
System.out.println(a - b < 0); // true

toArray()

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
/**
* Returns an array containing all of the elements in this list in proper
* sequence (from first to last element); the runtime type of the returned
* array is that of the specified array. If the list fits in the
* specified array, it is returned therein. Otherwise, a new array is
* allocated with the runtime type of the specified array and the size of
* this list.
*
* <p>If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
* <tt>null</tt>. (This is useful in determining the length of the
* list <i>only</i> if the caller knows that the list does not contain
* any null elements.)
*
* @param a the array into which the elements of the list are to
* be stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose.
* @return an array containing the elements of the list
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this list
* @throws NullPointerException if the specified array is null
*/
@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的size时,将a[size]置空作为调用者判断标志。根据这段代码写了个demo帮助理解:(扩展知识见②)

1
2
3
4
5
6
ArrayList al = new ArrayList();
al.add("s");
String[] s = {"c","h","e"};
String[] sal = (String[]) al.toArray(s);
System.out.println(sal[0] + "," + sal[1] + "," + sal[2]); // s,null,e

add()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

新增、删除都用到了System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);下面举例加深理解。

1
2
3
4
5
String[] arr ={"r", "e", "b", "e", "y", "."};
System.arraycopy(arr, 0, arr, 2, 2);
for(String i : arr) {
System.out.println(i);
}

即将arr下标从0开始的2个元素拷贝到arr下标从2开始的位置。

retainAll()

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
/**
* Retains only the elements in this list that are contained in the
* specified collection. In other words, removes from this list all
* of its elements that are not contained in the specified collection.
*
* @param c collection containing elements to be retained in this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
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 {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// 保证异常时,未比较元素不丢失
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;
}

a.retainAll(c)可以看成取a与c交集,a非c子集时,返回true。a中只留在c中存在的元素,其余删除。否则,返回false。

“elementData[w++] = elementData[r];”w永远小于等于r,因此可以将找到的相等元素大胆的放在elementData[w++]中(elementData[w++]是先放后加)。

iterator()

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
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
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]; //第一次cursor=1,lastRet=0
}
// lastRet不等于-1时才能进行删除,即next()后才能使用remove()
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++]);
}
// update once at end of iteration to reduce heap write traffic !!!
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

Iterator()所指类似数据库的游标,不了解的同学可参看以下解释:

当使用语句Iterator it=List.Iterator()时,迭代器it指向的位置是Iterator1指向的位置,当执行语句it.next()之后,迭代器指向的位置后移到Iterator2指向的位置。[1]

iterator

由源码可见ArrayList的迭代器基于Itr子类实现。该类实现了Iterator接口,并重写了它的全部方法(4种)。同时增加了checkForComodification()考虑并发问题。

listIterator()

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
/**
* Returns a list iterator over the elements in this list (in proper
* sequence), starting at the specified position in the list.
* The specified index indicates the first element that would be
* returned by an initial call to {@link ListIterator#next next}.
* An initial call to {@link ListIterator#previous previous} would
* return the element with the specified index minus one.
*
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
* Returns a list iterator over the elements in this list (in proper
* sequence).
*
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @see #listIterator(int)
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* An optimized version of AbstractList.ListItr
*/
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();
}
}
}

listIterator有2中构造方法,即它多了指定游标的功能。它实现了ListIterator extends Iterator接口,比Iterator多了一些方法。Iterator只能从前往后删除,而listIterator可实现从后往前删除/替换。同时也提供了获取前后下标的方法。

说点什么

private class SubList extends AbstractList implements RandomAccess {…} 源码太长就不贴出来了。它是ArrayList的子类,表示ArrayList的子集,需要注意的是,对它的数据进行更改会影响原数据。

此外,源码中出现了大量泛型(如T、E…)。希望顺便巩固泛型知识。

ArrayList允许为null;非线程安全;有序。

更多有意思的内容,欢迎访问笔者小站: rebey.cn

知识点

1.ArrayList c.toArray might (incorrectly) not return Object[] (see 6260652);2016.09.23;

2.为什么 Java ArrayList.toArray(T[]) 方法的参数类型是 T 而不是 E ?;2016.04.07;

[1]JAVA中ListIterator和Iterator详解与辨析;2014.11.27;

打赏
手机扫一扫,支持CHE~