JDK源码阅读--ArrayList

层次结构

字段及构造

// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;

//用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 用于默认大小的空实例的共享空数组实例。 
* 我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


//数组缓冲区,ArrayList 的元素存储在其中。 ArrayList 的容量就是这个数组缓冲区的长度.
//添加第一个元素时，任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 
//的空 ArrayList 都将扩展为 DEFAULT_CAPACITY
transient Object[] elementData;

//所包含元素的个数,不是数组的大小
private int size;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三个构造方法

ArrayList();
ArrayList(int cap);
ArrayList(Collection c);

源码流程分析

从list的创建, 添加, 查找, 删除, 扩容这几个方面分析

创建

ArrayList(); 默认初始化容量10,首次add时将创建长度为10的数组
ArrayList(int cap);
ArrayList(Collection c);

add添加

1. 每次add时,先调用ensureCapacityInternal()确保list容量可以进行add操作,如果不够,则会进行扩容
2. 确认容量后,新加入的元素放入数组缓冲区elementData 索引为size+1的位置

grow扩容

每次调用add()方法,都会调用ensureCapacityInternal()以确保内部容量,容量不够就扩容
以无参构造创建的list举例:

1. 首次添加元素时,计算容量calculateCapacity(),因为是无参构造,所以算出待创建数组的容量为10
2. 当前list所需的容量 大于 list数组缓冲区实际大小时,触发扩容grow()

if (minCapacity - elementData.length > 0)
   grow(minCapacity);


private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 10 >> 1  =>5
    // 5 >> 1  =>2
    // >>1,右移位1,可看成0.5倍扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 扩容后与缓冲区最小容量比较
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 扩容后容量是否大于容量上限
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // hugeCapacity() 返回 Integer.MAX_VALUE 或 MAX_ARRAY_SIZE
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 复制并生成指定长度的新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

查找get

在ArrayList中,get/set方法在访问底层数组之前,都会进行访问检查rangeCheck(index),来避免索引越界;
因为底层使用数组这种数据结构,所以get时直接通过数组下标获取,如下:

E elementData(int index) {
    return (E) elementData[index];
}
1
2
3

删除

提供多个API,通过对象删除,通过索引删除
通过索引删除:
情况1:如果删除元素是数组的最后一位,则将最后一位直接置为null;elementData[–size] = null
情况2:如果不是,则根据参数索引,计算出需要移动的元素个数numMoved,调用arrayCopy进行数组赋值

int numMoved = size - index - 1;
if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
elementData[--size] = null; // clear to let GC do its work
1
2
3
4
5

通过对象删除:
底层对数组进行for循环遍历,只会删除匹配到的第一个元素(索引最低位,第一次出现),删除过程与上述情况2相同.

总结

1. ArrayList底层是对象数组(elementData)
2. size是ArrayList中元素个数,不是底层数组对象的长度
3. 扩容时机:在add操作时,ArrayList会进行内部容量的确认,如果最小所需容量大于数组缓冲区的长度,则进行扩容
4. 扩容大小:old + old >>1,即0.5倍扩容