JDK容器学习之ArrayList：底层存储和动态扩容

一灰灰blog

发布于 2018-02-06 16:12:31

8640

发布于 2018-02-06 16:12:31

文章被收录于专栏：小灰灰

ArrayList 底层存储和动态扩容逻辑

ArrayList 作为最常用的容器之一，通常用来存储一系列的数据对象，O(1)级别的数据读写

I. 底层数据模型

查看源码，其内部定义的成员变量

// 默认数组容量
private static final int DEFAULT_CAPACITY = 10;

// 静态成员，创建一个空的ArrayList时，内部数组实际使用这个
// 避免每次创建一个ArrayList对象，都要新创建一个对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 实际保存数据的数组
transient Object[] elementData; // non-private to simplify nested class access

private int size;

因此ArrayList的底层数据模型比较清晰，就是一个数组，默认初始容量为10

II. 新增，删除，读取逻辑

因为底层的数据结构为数组，所以根据index查询元素是常量级别开销，等同于获取数组中所索引为index处的元素因此需要关注的就是新增一个元素，若数组容量不够，如何进行扩容删除一个元素，数组的连续性又是如何保障

1. 获取接口

获取List中某索引处的值，实现逻辑比较简单，如下

public E get(int index) {
    // 判断是否数组越界
    rangeCheck(index);
    // 获取数组中的元素
    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

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

另一个比较常见的读取接口就是contain和indexOf两个接口，用于判断列表中是否包含某个元素or某个元素在数组中的索引

若让我们自己来设计上面两个接口，多半是遍历数组，依次判断每个元素，是否满足要求

JDK实际实现代码如下

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

从具体实现，可以注意一下几点

size表示列表中元素的实际个数
列表中允许保存NULL
列表中允许多次加入统一个对象，但indexOf返回的是第一个匹配的位置
方法indexOf返回-1表示不存在

2. 删除元素

在添加元素之前，先看删除元素的接口实现，因为不涉及到动态扩容问题, 在分析中考虑下面几点

删除中间的元素，是否会造成后续的数组迁移
删除最后一个元素，是否会造成重排（还是直接size-1即可）

首先看删除指定索引处的值

public E remove(int index) {
    // 数组越界判断
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0) { // 如果移动不是最后一个则需要数组拷贝
        // native 方法实现数组拷贝
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    }
    // 消灭最后一个元素
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

从源码解决上面两个问题

删除中间元素，会导致数组拷贝
删除最后一个元素，不用数组拷贝，直接将最后一个元素设置为null
删除不会导致数组容量缩水，也就是List只有扩容的逻辑，没有缩小容量的逻辑

3. 新增元素

结合删除的逻辑，新增元素逻辑应该比较清晰，将添加索引处及之后的元素，整体后移一位，然后赋值新的值；需要注意扩容的机制

添加一个元素的实现

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
public void add(int index, E element) {
    // 判断索引是否越界
    rangeCheckForAdd(index);

    // 扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 数组拷贝
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 设置值
    elementData[index] = element;
    size++;
}

扩容的逻辑如下

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0) {
    // 当前的数组容量，已经超过数组长度
        grow(minCapacity);
    }
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩容原则： 
    // 新增原来容量的一半，即变为之前容量的 1.5倍
    // 如果上面容量依然不够，则选择扩容到恰好容下所有元素的容量
    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);
}

针对上面的逻辑进行小结：

先扩容，后数组迁移，最后进行赋值
扩容逻辑：
- 优先扩容原来容量的1.5倍
- 若依旧不够，则扩容到恰好能容纳所有元素
在列表的最后添加元素，不要使用add(index,object)方法，会造成没必要的数组迁移调用

插入删除示意图

III. 遍历逻辑

容器基本上都是实现了 Iterable 接口，所以遍历则主要是依据迭代器的next()方法来实现

List的遍历，说白了就是数组的遍历，实现逻辑比较简单，唯一有意思的就是并发修改抛异常的问题

先看下迭代器类

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        // 下面方法确保在遍历过程中，若有其他线程修改了列表的内容，则抛异常
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        
        // 遍历的实际逻辑，就是索引的递增
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
       // ...
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        //
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}