Java) ArrayList Capacity
This post was migrated from Tistory. You can find the original here.
ArrayList
1
2
3
4
5
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_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
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
private static final int DEFAULT_CAPACITY = 10;
Let’s call ArrayList “Vector” and LinkedList “list.”
When you create a vector with new ArrayList<>();, an empty object array is assigned to elementData.
When the first add comes in, it hits the if (s == elementData.length) branch and grow() runs.
Inside grow(int minCapacity), the else branch runs, and elementData becomes an array with the size of DEFAULT_CAPACITY, which is 10.
Now let’s look at what happens on an add after the size-10 array is completely filled.
In grow, the if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) branch is taken, and a new array of size newCapacity is created and the old data copied into it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(ArraysSupport.newLength)
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// preconditions not checked because of inlining
// assert oldLength >= 0
// assert minGrowth > 0
int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
// put code cold in a separate method
return hugeLength(oldLength, minGrowth);
}
}
public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
SOFT_MAX... is close to the upper bound of an int. If prefLength gets close to or exceeds that bound, the else branch runs.
Let’s first look at the if branch case. If an add comes in right after the array has been filled to size 10, it looks like this: ArraysSupport.newLength(10, 1, 10 >> 1)
10»1 = 5
15»1 = 7
22»1 = 11
You can see that a right shift by one bit gives roughly half of the original value.
So the return value of the if branch can roughly be thought of as oldLength + Math.max(1, oldLength/2);. In other words, the new capacity ends up being about 1.5 times the original array size.
1
2
3
4
5
6
7
8
9
10
11
private static int hugeLength(int oldLength, int minGrowth) {
int minLength = oldLength + minGrowth;
if (minLength < 0) { // overflow
throw new OutOfMemoryError(
"Required array length " + oldLength + " + " + minGrowth + " is too large");
} else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
return SOFT_MAX_ARRAY_LENGTH;
} else {
return minLength;
}
}
Since oldLength + prefGrowth overflows, it starts instead from oldLength + minGrowth (== 1). If even adding minGrowth overflows, it throws an OutOfMemoryError.
If it doesn’t overflow and is less than or equal to Integer.MAX_VALUE - 8, it allocates the maximum capacity; if it’s larger than that, it allocates minLength, which is incremented by just 1.
Let’s also compare the timing and think about the characteristics of each data structure.
2023.07.13 - [java] - Java) Comparing ArrayList and LinkedList Timing (23-07-06)