Java8 ArrayList<E>源码解读

ArrayList<E>是能够自动扩容版本的数组实现,它继承了​AbstractList<E>​抽象类,实现了​List<E>, RandomAccess, Cloneable, Serializable​等几个接口:

1
2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList<E>初探


ArrayList<E>​内部以一个​Object​数组存储元素,以一个整型​size​成员记录元素的个数:

1
2
3
4
5
6
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; //transient表名了elementData不参与序列化
private int size;
protected transient int modCount = 0; // 从AbstractList<E>继承

其有三个构造函数:

  1. 无参构造函数:

    1
    2
    3
    public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    • 初始化的是一个空对象数组,其实际数组长度此时为0
  2. 指定初始容量的构造函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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);
    }
    }
    • initialCapacity​大于0时,初始化的是一个参数指定容量长度的对象数组
  3. 从另一个集合对象构造ArrayList<E>​

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
    // defend against c.toArray (incorrectly) not returning Object[]
    // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
    if (elementData.getClass() != Object[].class)
    elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
    // replace with empty array.
    this.elementData = EMPTY_ELEMENTDATA;
    }
    }
    • 从参数集合对象拷贝成对象数组,其长度是原集合对象的长度

modCount​从​AbstractList<E>继承而来,用来标记​ArrayList<E>​实例被结构性改变(如元素删除等)的次数,其被用来在迭代器中判断迭代过程中数组是否被做了修改,如果被修改则抛出​ConcurrentModificationException​。

延迟初始化与扩容


可以看到对于ArrayList<E>​的默认构造函数,并没有在对象构造的时候就初始化一定的空间容量,而是延迟到了往里面添加元素或者调用​ensureCapacity(int)​的时候才去分配容量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}

public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}

public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index, elementData, index + 1, s - index);
elementData[index] = element;
size = s + 1;
}

其中的grow()​方法即是做自动扩容的:

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
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 Object[] grow() {
return grow(size + 1);
}

public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}

//-------------------------- 以下来自ArraysSupport --------------------------

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// assert oldLength >= 0
// assert minGrowth > 0

int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) {
return newLength;
}
return hugeLength(oldLength, minGrowth);
}

private static int hugeLength(int oldLength, int minGrowth) {
int minLength = oldLength + minGrowth;
if (minLength < 0) { // overflow
throw new OutOfMemoryError("Required array length too large");
}
if (minLength <= MAX_ARRAY_LENGTH) {
return MAX_ARRAY_LENGTH;
}
return Integer.MAX_VALUE;
}
  • 首次调用add方法添加元素或初始化后调用ensureCapacity​扩容时,走以上代码第9行的逻辑,扩容至少​DEFAULT_CAPACITY​即10个元素的空间长度;

  • 当原来的数组有值但空间不足或手动调用ensureCapacity​扩容时,计算扩容空间的逻辑:

    最少扩容空间(minGrowth)为传入参数与已有容量之差(大于0),建议容量(prefGrowth)为已用用量的一半,MAX_ARRAY_LENGTH为整型最大值减8(减8的原因是某些VM在数组中保留一些头部信息)

    • 在扩容后的长度小于MAX_ARRAY_LENGTH的情况下,取最小扩容容量和建议容量值之间的最大者;也就是说单次扩容容量起码是已分配空间的一半
    • 当扩容后的长度大于MAX_ARRAY_LENGTH时,可能是由于增长了prefGrowth​导致的,则改为按​minGrowth​重新计算扩容后的长度:
      • 如果扩容后的长度已经整型溢出,则抛异常
      • 如果扩容后的长度小于等于MAX_ARRAY_LENGTH,则返回MAX_ARRAY_LENGTH
      • 否则返回Integer.MAX_VALUE​

batchRemove分析


removeAll​和​retainAll都使用了​batchRemove​方法来处理,其代码如下:

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

public boolean retainAll(Collection<?> c) {
return batchRemove(c, true, 0, size);
}

boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}

private void shiftTailOverGap(Object[] es, int lo, int hi) {
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}

complement​是​补数、补充、辅助的意思,其为true时计算的是与集合c的并集,其为false时计算的是与集合c的差集,这里使用了双指针的技巧来计算差集并集:

  • 第13行定义一个下标指针r(可理解为read),接下来初始化为参数的from即数组第一个元素下标,它将负责从头到尾遍历对象数组;
  • 第15~20行,找到第一个不在c(求并集)或第一个在c(求差集)中出现的元素记录其下标到w,如果指针r最终指向了数组末尾,则说明c是数组的子集(求并集)或c与数组不存在交集,直接返回false;
  • 第21~25行,继续指针r遍历对象数组的剩余部分,对于不在c(求并集)或在c(求差集)中出现的元素将其拷贝到w指向的位置然后将w往右移动一个元素,直到剩余元素遍历完成;
  • 第26~31行,兼容处理c.contains​可能抛出异常的情况;
  • 第33~34行,修改本ArrayList实例的modCount,并且置空w往后的元素空间为null

简单总结


  1. ArrayList<E>​没有加锁同步,它不是线程安全的;
  2. 使用默认构造函数新建一个ArrayList<E>​对象在未使用之前它是空的,直到调用​ensureCapacity​或者​add方法时才去扩容数组空间,至少为10个元素容量大小;
  3. 已分配过空间再进行扩容的机制:尝试扩容为已有容量的1.5倍,如果扩容超出整型最大值的情况下(可能是按已有容量一半进行扩容的)重新判断,尝试按最小扩容量进行扩容,如果还是超出整型最大值则抛异常,否则如果没超出MAX_ARRAY_LENGTH则返回MAX_ARRAY_LENGTH,否则返回整型最大值;
  4. 如果可预见后续会使用比较大的空间,则可以先调用ensureCapacity​做一次分配,以减少自动频繁扩容带来的开销;
  5. 求与另一个集合的差集、并集时采用了双指针的技巧。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×