集合框架原理剖析（二）、ArrayList篇

前言

本篇正式开始进入集合框架

首先从最最常用的ArrayList开始，它是单列集合顶层接口Collection，的子接口List，的一个实现类

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

但他其实不光实现了List接口，还有一些其他的继承和实现关系，这些暂时先不去看

先来看一下类名吧，顾名思义，Array是数组的意思，List是集合

就是说ArrayList是一个用数组实现的集合

其实对于操作多个对象，大家首先应该想到的就是数组

但是数组有一个问题，就是他的长度需要在初始化的时候就确定好，因为需要给他分配连续的内存空间，它后面的空间可能会被其他数据占用，所以它不支持动态的扩容，初始化10个数据的内存空间就只能放10个数据

这显然是不行的，实际的使用场景中，我们往往是不知道集合中会有多少个数据，那应该怎么办呢？初始化设置的数组太大了，会浪费内存空间，太小了又可能不够用，定长的数组好像根本不适合用来做集合。

ArrayList解决了这个问题，将数组封装成了集合对象，话不多说，实现的原理直接来源码中找答案

根据上面这个，idea中的类图，我们可以看到ArrayList一共有三种构造器

分别是一个无参构造，一个int类型为参数构造，一个约束为Collection子类的泛型对象为参数的构造

先从无参构造器开始进入源码吧

无参构造

构造方法如下：

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

该方法只有一句代码，是一个赋值操作，将一个常量赋值给了一个属性变量，我们看一下这个变量和常量分别是什么

transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

这里先解释一下transient关键字，表示被它修饰的属性不会参与对象的序列化（对象序列化是用与数据的传输，这里不多做这个的解释了，不理解不会影响源码的阅读，感兴趣可以自己去看看）

可以看到elementData是一个Object类型的数组，Object是所有对象的父类，就意味着这是一个可以存放任意类型数据的数组

根据源码中的注释，他就是用来存放要管理的集合数据的

DEFAULTCAPACITY_EMPTY_ELEMENTDATA常量呢，是一个空的Object数组

那么这个构造器，就只做了一件事，就是把管理集合数据的数组，初始化为一个空数组，并没有给数组分配初始内存容量

那我们来看一下，他如何给空数组添加元素

add方法

一共有两个add方法，参数不同，是一种方法的重载，理解成两个完全不同的方法就好了

这里先看第一个,这个E表示泛型，了解泛型的人不需要我多说，不了解的这里就不讲了，先当做可以接收任意类型参数去看就好，泛型是只存在与编译器层面的一种约束，编译后的字节码文件中都是不存在的，并不会影响源码的阅读

这个add方法，接收一个e数据，返回一个boolean

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

首先方法的最开始执行了一个ensureCapacityInternal(size + 1)方法

传入的参数是size+1

private int size;

size是一个成员属性，表示实际存入集合中的元素数量，当前没有任何操作对它进行过修改，所以它就是int类型数据的默认值0

这里传入的参数size+1其实就是需要数组的最小容量minCapacity

看一下这个方法

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

又是两个方法的嵌套，先看内层calculateCapacity(elementData, minCapacity)方法

elementData就是数据数组，minCapacity就是需要数组的最小容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

方法中判断，如果当前数组就是空数组，他会返回DEFAULT_CAPACITY和需要的最小容量中更大的一个,DEFAULT_CAPACITY是一个常量10，表示默认的容量

private static final int DEFAULT_CAPACITY = 10;

如果当前数组不是空的，就返回需要的最小容量

再来看外层，得到这个容量后做了什么

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

modCount++，modCount是继承自AbstractList的一个属性，记录的是对集合的修改次数，他会被迭代器的实现类使用，如果正在遍历的集合被修改了，会抛出异常，所以一边遍历一边更改集合的操作是不被允许的

修改次数++后，判断了如果需要的最小容量，大于当前数组长度，就执行了一个grow(minCapacity)方法，下面我给这个方法加上注释

private void grow(int minCapacity) {
    //记录旧容量为当前数组长度
    int oldCapacity = elementData.length;
    //记录新容量为当前数组长度的1.5倍（这里是一个位运算，>>表示右移操作，右移一位相当于除以二）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //判断如果新容量小于最小需求容量，就让新容量等于最小需求容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //判断如果新容量大于MAX_ARRAY_SIZE（2147483639）
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //就设置为int的最大值
        newCapacity = hugeCapacity(minCapacity);
    //创建一个容量为新容量的数字
    elementData = Arrays.copyOf(elementData, newCapacity);
}

到这里ensureCapacityInternal(size + 1)方法就执行完了，原来是一个判断是否需要扩容，如果需要就扩容的方法

接下来elementData[size++] = e就很好理解了，因为size记录的是当前数组中实际存储的数据数量，就在以size为索引的位置添加了新元素e，然后让size=size+1（size++是先复制后++）

add方法看完了，这些彻底明白ArrayList实现动态扩容的原理了，它将所有的数据存在一个数组elementData中，并且记录了一个当前数组中有效数据数量size，每次添加时就判断当前数组容量够不够存放添加的数据，如果不够，就进行扩容，扩容方法判断如果当前数组为空，就用默认容量10进行初始化，如果不为空就扩容为当前容量的1.5倍

（这里可能会觉得有一些多余操作，比如扩容的容量，是在最小需求容量和扩容为1.5倍后的容量中，取了一个更大的，你的思考是有道理的，在当前我们使用无参构造初始化集合后只使用add方法的前提下，确实是多余的，但是还有有参构造和批量添加也会公用这个扩容方法）

有了上面的结论，我们再去看有参构造和另一个重载的添加方法就简单多了

我们接着来剖析一下ArrayList中其他的增删改查方法

先把构造器都看完

int有参构造

继续来看一个传入一个int类型参数的有参构造

我加上注释一起看一下

public ArrayList(int initialCapacity) {
    //判断传入参数是否大于0
    if (initialCapacity > 0) {
        //如果大于0，elementData初始化为一个容量为参数的Object数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //再判断如果等于0，elementData初始化为一个空Object数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //小于0，抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

代码非常简单易懂，很明显，这个构造器是可以设置初始数组容量的构造器，会按照传入的容量值，初始化数组

再看最后一个有参构造

Collection有参构造

这个构造器，可以传入一个Collection接口类型（根据Java的多态，这里可以传入任意Collection的子集类型）

也就是传入另外一个集合，我加上注释

public ArrayList(Collection<? extends E> c) {
    //首先调用集合的toArray()方法，给elementData赋值
    elementData = c.toArray();
    //判断传入的集合转化后的数组容量
    if ((size = elementData.length) != 0) {
        //如果容量不是空的，在判断是否是Object[]
        if (elementData.getClass() != Object[].class)
            //如果不是Object[]，转化为Object[]
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //如果容量是空的，直接设置为空Object[]{}数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

这里的toArray()方法是集合顶层接口Collection的接口方法，所有实现类都必须实现的方法，作用就是将集合转化成数组返回

可以看一下ArrayList对toArray()的实现

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

返回的是集合中存放实际数据的满容量数组

构造器就都看完了，再看一下add方法还有一个重载

add(int index, E element)方法

看一下参数，猜测就能想到，应该是向某个位置添加一个元素

看一下和普通添加有什么区别，首先没有返回值了

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++;
}

逐行看一下

rangeCheckForAdd(index);

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

是一个参数校验，先判断了要插入的位置index是否合法，如果大于size或者小于0说明不存在一个这样的位置，直接抛出异常

ensureCapacityInternal(size + 1);

这个就不用说了，和add中完全一样，是判断扩容的方法

System.arraycopy(elementData, index, elementData, index + 1, size - index);

这句点进去看一下

public static native void arraycopy
    (Object src,int srcPos,Object dest,int destPos,int length);

是一个native修饰的方法，表示是底层用非Java语言实现的方法

这里就说一下它的作用，就是把数组中index开始的元素，都后移了一位，给需要添加的元素空出了位置

elementData[index] = element;size++;

这两句放在一起，就是在index的位置插入了新的元素，然后维护实际存储数据数量++

至此构造器和单个元素添加的方法就都看完了

再看看其他增删改查，详细看过前面这些的源代码，后面的基本都大同小异，大家应该也都能看懂了，我就只列举出来，讲述一下功能，分析一下和源码中不同的地方，以及罗列一些注意点

批量添加

批量添加至数组尾部

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

看过之前的Collection有参构造和单个添加，批量添加非常好理解

首先从传入的集合获得数组

然后执行的是一样的判断扩容方法，只不过这里不再是size+1，因为要添加的数量是集合中获取的数组的长度（这里是不是就明白了，为什么扩容的代码中，要从最小需求容量和扩容1.5倍的容量中，选一个更大的作为实际要扩容到的容量，也就是如果批量添加的元素太多了，甚至会超过一次扩容后的容量，就直接扩容成增加后的容量，此时相当于最终会存了一个满数组）

扩容之后，还是用了底层的一个数组拷贝方法，将新数组追加到了最后一个元素的后面

批量添加至指定位置

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

结合单个元素添加到指定位置，和批量添加来看，也很好理解，就是从index开始所有元素后移一个要添加数组的长度，空出要添加数组的位置

然后再将要添加的数组复制进来到空出来的位置

然后让size加上新添加数组的长度

迭代器

Iterator

    /**
     * Returns an iterator over the elements in this list in proper sequence.
     *
     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.Itr
     */
    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;

        Itr() {}

        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() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

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

这个就不深入去看了，只需要知道ArrayList用一个静态内部类辅助继承了Iterator，实现里里边的四个方法，所以可以直接用公共方法public Iterator iterator()来获取它的迭代器，去进行集合的遍历

值得注意的是，之前说过修改集合的时候会改变一个modCount值，在这里实现迭代器中方法就用上了这个变量，会判断正在遍历的集合是否被修改了（这里说的修改其实只有新增和删除，只有这两种操作会改变modCount的值），如果修改了就会抛出异常，可以看到确实有下面这段代码

if (modCount != expectedModCount)
    throw new ConcurrentModificationException();

所以在遍历集合的时候，是不能新增和删除的

那如果非要在遍历集合的时候进行删除/新增操作怎么办？

首先我们看到迭代器中，有一个方法remove，可以删除当前正在遍历的元素，这个不会异常
如果我们遍历的时候就是遍历到某个元素之后要删除其他元素，用不了迭代器的remove，那就只能纪录一下要删除什么元素，待遍历结束后，再根记录删除
如果便利的时候要根据遍历的元素，进行新增，可以在外边创建一个新的集合，将遍历过程中要新增的元素顺序的存入新集合中，遍历结束后执行批量添加
...可能还有其他场景，但不论什么场景，只要是遍历中有对正在遍历的集合进行新增和删除的操作，都要想办法到遍历之后再执行

！注意！：foreach的底层就是这个迭代器

所以使用foreach和使用Iterator迭代器都需要注意上面的问题

listIterator

还有一个更厉害的迭代器listIterator，前面的那个Iterator迭代器不仅只能单向遍历，而且remove方法在调用一个next后只能执行一次，也不能在遍历的时候有其他删除和新增的操作

这个集合迭代器就不一样了，首先可以支持双向遍历，多了一个previous方法可以向前遍历，还多了set、add方法，支持在遍历中修改，还支持选择开始遍历的位置,listIterator(int index)；listIterator()，空参和有参两个重载方法来获取这个迭代器

不过也还是有局限性，只能用set和add在当前遍历到的索引位置添加或修改...

public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}
public ListIterator<E> listIterator() {
    return new ListItr(0);
}
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

查找

按索引查找

/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);

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

按对象查找

查找对象所在的索引位置（找到第一个返回）

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;
}

查找所在对象的索引位置（找到最后一个返回）

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

两个一个是从前往后遍历，一个是从后往前遍历

是否包含某个对象

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

综上，按对象查找其实可以这样

if(list.contains(o)){
    Object obj = list.get(list.indexOf(o));
}

值得注意的是，这里的查找对象，就只是使用了equals方法，所以如果存入的对象没有重写equals方法，相当于默认的equals方法是用==判断是否是同一个对象，那如果new一个对象去查找的话，就会可能虽然长得一摸一样，但是是找不到

常用删除

按索引删除

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);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

这里其实也都大同小异，就是删掉之后，再把后面的元素向前移动

按对象删除

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

这里是先遍历查找到对应元素然后删除，删除调用了一个私有方法fastRemove

其实就是在remove的基础上省略了判断索引是否越界和返回值

private void fastRemove(int index) {
    modCount++;
    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
}

按起止索引删除

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}

把两个索引之间的元素全部删除，然后后边的元素都向前移动补齐

交集删除

//在当前集合删除与c集合的交集
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
//只保留当前集合与c集合的交集
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

也是两种不同的批量删除方式

清空集合

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

将所有元素置为空，见size设置为0（但不会改变集合的容量）

李阿阿

游客

2022-09-14 21:32:29

coderZ

博主

@ 李阿阿

这位兄弟为什么要骂我

2022-09-15 01:11:38

嘻嘻嘻我在测试评论敏感字眼屏蔽，博主写了真厉害

2022-09-15 16:19:15

博主你视频功能可以完善下发我学习下嘛谢谢

2022-09-15 16:21:50

测试**

2022-09-21 17:26:36

gtrfe

😀re⁣赞一个

2022-10-08 17:27:49

rantrsim

⁣您好～我是腾讯云开发者社区运营，关注了您分享的技术文章，觉得内容很棒，我们诚挚邀请您加入腾讯云自媒体分享计划。完整福利和申请地址请见：https://cloud.tencent.com/developer/support-plan<br/><br/>作者申请此计划后将作者的文章进行搬迁同步到社区的专栏下，你只需要简单填写一下表单申请即可，我们会给作者提供包括流量、云服务器等，另外还有些周边礼物。

2022-10-21 10:48:10

腾讯云开发者社区

⁣您好～我是腾讯云开发者社区运营，关注了您分享的技术文章，觉得内容很棒，我们诚挚邀请您加入腾讯云自媒体分享计划。完整福利和申请地址请见：https://cloud.tencent.com/developer/support-plan<br/>作者申请此计划后将作者的文章进行搬迁同步到社区的专栏下，你只需要简单填写一下表单申请即可，我们会给作者提供包括流量、云服务器等，另外还有些周边礼物。😁🍉

2022-11-22 18:17:01