Java8集合系列之ArrayList（一）

Posted on   |   In   |     |   visitors

阅读Java SDK的几个核心包源码计划的flag已经立下很久了，一直没有行动。一个是因为集合框架是Java中比较常用的数据结构，从List、Set、Map到Queue等等，另外这部分会涉及到线程并发安全性的问题，所以想进一步学习弄清楚实现原理。于是，决定从List开始梳理java集合包中这部分源码的实现，方便自己日后回顾。

ArrayList

ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable，实现了list、RandomAccess（随机访问）。

construct

1
2
3
4
5
6
7
8
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;//关于transient关键字见下面注解;
public ArrayList() {
    super();
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。

add

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
private static final int DEFAULT_CAPACITY = 10;//默认数组大小10
private int size;//ArrayList中包含元素的数量
public boolean add(E e) {
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    //第一次初始化，minCapacity=10；
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //保证minCapacity大小的容量
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    //The number of times this list has been structurally modified.
    modCount++;
    //要保证的数组长度大于目前数组长度时，就要扩充数组了，否则，不用扩充。
    //比如：当第一次添加元素时候，因为还是空数组elementData.length=0，minCapacity = Math.max(DEFAULT_CAPACITY, 1)=10，就需要第一次扩充了。
    //当元素数量<=10的时候，minCapacity=10，elementData.length=10，这个时候就跳过了。
    //当元素数量等于11的时候，超过了elementData.length=10，这个时候就开始第二次扩充了。
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
   
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //第一次扩充的时候，oldCapacity=newCapacity=0，minCapacity=10；
    //第二次扩充的时候，oldCapacity=10，newCapacity=15，minCapacity=11；
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //将原来的数组内容复制到新的大小为newCapacity的数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 移除list中指定位置的元素，并且将后续元素向左移动
 */
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);//这是一个native方法（JNI），实现数组复制。
    elementData[--size] = null; //末尾值设置为null，便于GC
    return oldValue;
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

get

1
2
3
4
public E get(int index) {
    rangeCheck(index);//范围检查
    return elementData(index);
}

小结

1、默认容量10.
2、每次增加元素，需要保证足够大小容量，因此在不确定元素数量的情况下，会出现频繁的扩容（1.5倍），影响插入效率。
3、频繁删除元素效率较低，因为需要每次都移动大量数组元素。
4、能实现随机读取，查找效率较高。

参考

关于Java集合的小抄
Java transient关键字使用小记

-EOF-