Java 容器源码分析之 ArrayList（2）
|
- UID
- 1066743
|
Java 容器源码分析之 ArrayList（2）
扩容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
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
| /**
* 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.
*/
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 ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
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.
*/
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;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
|
这一段代码的注释很清楚了，大致解释一下：ensureCapacity方法可供外部调用，而ensureCapacityInternal则仅供内部调用，都是要确保当前容器能够容纳给定数量的元素，它们都会调用ensureExplicitCapacity方法；在每次调用ensureExplicitCapacity方法时，会将modCount 的值加1，表明 ArrayList 发生了结构化的修改，然后根据当前数组能容纳的元素数量来决定是否需要调用grow方法来调整数组的大小；grow方法负责调整数组的大小，注意每次调整时将容量扩大为当前容量的1.5倍（oldCapacity + (oldCapacity >> 1)），如果还是不能满足容量要求，就按照所需的最小容量来分配，然后将原数组中的元素复制到新数组中。ArrayList 能够支持的最大容量为 int 值的上限，超过会报OutOfMemoryError异常。
这里有一个奇怪的地方在于，modCount 的值会在 ensureExplicitCapacity 方法中加1。前面已经说过，modCount用来记录容器发生结构化修改的次数，按道理来说实在加入或移除元素是才会修改的，为什么会在这里调用呢。后面我们会看到，每次新加入元素时，ensureExplicitCapacity 都会被调用，因而可以将modCount的修改放在此方法中，就不必在 add 及 addAll 方法中进行修改了。 |
|
|
|
|
|
