当前位置：首页 > article >正文

从零到Offer -- List的那些事

article 2025/1/7 7:05:16

ArrayList

作为日常最常见的collection对象，相信大家对于ArrayList都不陌生。但是ArrayList的实现你是否又了解呢？开门见山，ArrayList的最底层实现其实就是一个数组：

transient Object[] elementData;

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

然而我们都知道，java下，一个数组的长度是固定的，是无法变化的。但是实际我们应用ArrayList的时候不难发现，无论你怎么往这个集合中添加元素，他都不会显示越界。相反，数组就像有了魔法一样，会随着你的添加而不断变长。要了解这个原因，就不得不提到add方法。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

乍一看，add方法本身平平无奇。但是实际上在ensureCapacityInternal方法中，它悄悄为你做了好多事。

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//计算长度
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //如果数组为空的，那么此时返回默认最小长度间 - 10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    //记录修改的次数
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

越界处理

首先看到modCount++这个代码，相信我们在使用中不免有过这样的操作，在for循环中尝试删除/移除一个元素对象：

for (String s : arrayList) {
    arrayList.remove(s);
}

然后此时可能就会抛出这样的报错：

在这里插入图片描述

其实本质原因是，for循环的代码依赖每个对象的iterator实现的。而iterator又依赖是数组的长度和下标。其是否可以往下循环会通过hasNext进行判断。如果我们随意删除元素，那么此时就可能出现越界。

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

为了尽早的避免这种情况发生（FailFast原则），ArrayList在设计上就采用一个modCount的变量来记录数组变更的次数，并通过判断迭代器生成时的modCount同循环进行时的modCount进行比较，从而达到目的。

容量变化

除了modCount以外，我们还关注到ArrayList里有grow(minCapacity);这样一句代码，这个其实就是ArrayList能够不断添加元素的关键：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 设置最小长度
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 计算溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

grow中主要做了以下三件事：数组扩容、设置最小长度、判断溢出

数组扩容

在数组扩容上，新的容量长度是通过旧容量*1.5倍（左右）得到的，这里为什么要采用1.5倍而不是2倍也不是1.2倍呢？原因个人理解有两个：

1、添加引发的扩充是很频繁的，因此需要更快的运算速度。而我们都知道位运算运算速度是最快的，自然就不优先考虑1.2、1.4这些用运算较难得到的数字。那么只剩下1.5、2（只需要一次移位）、1.25、4（需要两次移位）的选择了。

2、从上述描述中，我们优先会考虑1.5和2，采用2倍空间进行扩容自然也是可以的，但是实际中2倍扩充会浪费比较多的空间，且数组的空间是无法被GC回收的。因此，为了更少的浪费空间，于是采用了1.5倍这个关键值。

设置最小长度

在设置最小长度的点上，这个相对简单，需要注意的是，虽然初始ArrayList创建时是一个空数组，但是实际ArrayList会保存一个

默认长度，其值为10.

private static final int DEFAULT_CAPACITY = 10;

判断溢出

ArrayList能扩容不假，但也不能无限创建空间。因此ArraysList为数组的长度划定了一个上限：Integer.MAX_VALUE-8。这里之所以要减8，是为了适配不同VM虚拟机，因为不同的VM虚拟机会保存一部分header头信息。

如果当前长度超过了Integer的最大值，毫无疑问会变成负数。此时系统就会判定为超出了ArraysList的存储大小了。若是当前最小长度介于Integer.MAX_VALUE和Integer.MAX_VALUE-8之间，会默认转换成最大值。

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

//判断是否溢出
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

LinkedList

介绍完了ArrayList，我们自然还需要介绍他的亲戚LinkedList。与ArrayList明显不同的是，LinkedList底层的实现是基于链表实现的。其中有first、last两个节点，用于保存链表的首节点和尾节点。对于每个node来说，其都会保存其前一个节点的指针及后一个节点的指针。

transient Node<E> first; // 首节点

transient Node<E> last; // 尾节点

private static class Node<E> {
    E item;
    Node<E> next; // 前一个对象
    Node<E> prev; // 后一个对象
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

同arrayList类似，要介绍LinkedList就也得介绍他的add方法：

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

从上可以看到，linkLast()方法其实组成了add方法的全部。相信如果各位学过数据结构与算法的话，一定会对上述代码不陌生。就是一个简单的带尾部节点的链表尾插算法。（不了解的同学就百度一下吧，限于篇幅这里就不展开了。）

同时可以看到LinkedList也会保存一个size变量用于保存数组的长度，避免链表在获取长度时所需要消耗的耗时。与ArrayList类似的是，linkedList也会保存一个modCount变量用于保存数据变更的次数，作用是类似的，这里就不再赘述了。

Vector

上文介绍到的ArrayList和linkedList是我们日常最常使用到的数组结构。但是他们都存在一个缺陷，就是没法应对多并发。LinkedList在多并发下指针可能会紊乱，而ArrayList则可能出现数组越界、数据污染等问题。

为此，Collection包下还有一个数组结构，那就是Vector。那么vector又是如何支持多并发的呢？其实很简单粗暴，vector本身也是采用数组实现的，与ArrayList不同的是，其所有数据变更的方法都采用同步关键字synchronized进行修饰。从而达到同步互斥的逻辑。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}