Java源码阅读之ArrayList - JDK1.8

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方，欢迎指正~
转载请注明出处https://blog.lzoro.com。

前言

当你对某件事情很感兴趣的时候，时间的流逝在感知中都模糊了（是不是很文艺，绕口得都快听不懂了），通俗来说，就是时间过得很快。

而且，只有感兴趣才能驱动你继续下去，不然读源码，写解析博客这么高(Ku)大(Zao)上的事，是很难坚持的。

详细地写一篇源码解析博客少则半天一天，比如本篇，多则几天，比如红黑树在Java - HashMap中的应用，又要画图又要注释，还要排版，时不时要加点表情，开个车什么的，你说要是没兴趣，怎么坚持呢，还不如吃个鸡实在(啊，暴露了我是吃鸡选手)。

闲话少说，打开你的IDE，挽起袖子，开撸代码，加上注释，总计1461行代码。

基本介绍

常量

相比HashMap来说，ArrayList的常量算是短小精悍了，只有几个。

其中包含一个默认容量和两个空数组等，如下。

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

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

/**
 * 缺省大小的空数组共享实例
 * 与 EMPTY_ELEMENTDATA 区分开来，以便知道第一个元素添加时如何扩容
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 最大可分配大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

成员变量

成员变量也是简单到令人发指，一个负责实际存储的缓冲数组和一个表示大小的变量。

/**
 * 实际负责存储的缓冲数组
 * ArrayList的容量就是缓冲数组的长度
 * 
 * 空的ArrayList(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)在第一个元素添加时将会以默认容量扩容
 */
transient Object[] elementData; // 非私有，以简化嵌套类的访问

/**
 * 大小
 */
private int size;

构造函数

三个构造函数，分别是利用默认初始容量/给定初始容量/给定特定集合来构造ArrayList。

/**
 * 根据给定初始容量构造一个空的list
 *
 * @param  initialCapacity  list的初始容量
 * @throws IllegalArgumentException 当给定的初始容量非负时抛异常
 */
public ArrayList(int initialCapacity) {
    //判断给定初始化容量是否合法
    if (initialCapacity > 0) {
        //创建数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * 按默认初始容量(10)构造一个空的list
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 根据给定集合构造一个list，将按集合迭代的顺序存储
 *
 * @param c 集合
 * @throws NullPointerException  集合为null时抛异常
 */
public ArrayList(Collection<? extends E> c) {
    //集合转数组后赋值给缓冲数组
    elementData = c.toArray();
    //判断大小
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //c.toArray方法可能不会返回Object[]形式的数组
        //下面做一层判断
        if (elementData.getClass() != Object[].class)
            //做拷贝操作
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //如果是空集合，则替换成共享空数组实例
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

功能

看完了基本介绍，应该会觉得Just so so。

接下来就要逐一介绍各个功能的具体实现了。

ArrayList中，我们常用的功能有add/remove/get等。

无外乎增删改查，下面一一介绍~

add

在ArrayList中，添加操作还分为几种

• 从尾部添加元素
• 指定位置添加元素
• 从尾部添加集合
• 从指定位置添加集合

/**
 * 从尾部添加指定元素
 *
 * @param e 元素
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    //确保内部容量，有一系统调用链但不复杂，下面分析
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //存储元素
    elementData[size++] = e;
    return true;
}

/**
 * 在指定位置插入元素
 *  移动当前位置的元素 (如果存在) 和后继元素到右边
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    //判断边界，可能会产生数组越界
    rangeCheckForAdd(index);
    //确保内部容量，同上
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //调用效率较高的System.arraycopy进行数组复制
    //目的是为了空出指定位置
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //指定位置上放入指定元素
    elementData[index] = element;
    //容量+1
    size++;
}

在添加的元素的时候，有一个关键方法ensureCapacityInternal是来确保内部缓存数组的容量，当容量不够时进行扩容，下面具体看下这个方法的调用链

/**
 * 私有方法
 */
private void ensureCapacityInternal(int minCapacity) {
    //判断是否是默认空实例，如果是的话，计算扩容容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //调用ensureExplicitCapacity
    ensureExplicitCapacity(minCapacity);
}

...

private void ensureExplicitCapacity(int minCapacity) {
    //操作计算+1
    modCount++;
    
    // overflow-conscious code
    //只有当容量不够时才扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 缓冲数组扩容以确保能够存储给定元素
 *
 * @param minCapacity 期望的最小容量
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    //现有元素长度
    int oldCapacity = elementData.length;
    //新容量为 旧容量 + 旧容量的一半
    //如 10 + 5 = 15
    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:
    //最小扩容容量通常是接近size的，所以这是一场胜利
    //这么臭美的吗
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * 取得最大容量
 */
private static int hugeCapacity(int minCapacity) {
    //溢出
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //取最大容量
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

set

这里的set其实可以理解为修改，将指定位置的元素替换为新元素。

/**
 * 修改指定位置的元素
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    //范围检查
    rangeCheck(index);
    //取出旧值用以返回
    E oldValue = elementData(index);
    //放入新的值
    elementData[index] = element;
    return oldValue;
}

remove

数组的移除和添加一样，也分为几种方式

• 根据下标移除
• 根据对象移除
• 根据集合移除
• 根据过滤器移除
• 根据范围移除(受保护的方法)

/**
 * 删除指定位置的元素，后继元素左移(前移)
 *
 * @param index 下标
 * @return the 被移除的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    //下标检查
    rangeCheck(index);
    //操作计数 + 1
    modCount++;
    //获取指定位置的元素(用以返回)
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    //用system.arraycopy的方式移动元素
    //相当于是index位置后的元素前移
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //最后一个数组元素引用置为null，方便GC
    elementData[--size] = null; // clear to let GC do its work
    //返回
    return oldValue;
}


/**
 * 当元素存在的时候，删除第一个找到的指定元素
 * 
 * 如果元素不存在，则list不会变动
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
public boolean remove(Object o) {
    //o是否是null元素(数组允许存储null)
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //调用内部的fastRemove方法，后面分析
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            //这里跟上面不一样的是，是用equals来比较，而不是比较地址
            if (o.equals(elementData[index])) {
                //同上
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/**
 * 根据给定的集合，将list中与集合相同的元素全部删除
 *
 * @param c collection containing elements to be removed from this list
 * @return {@code true} if this list changed as a result of the call
 * @throws ClassCastException if the class of an element of this list
 *         is incompatible with the specified collection
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 * (<a href="Collection.html#optional-restrictions">optional</a>),
 *         or if the specified collection is null
 * @see Collection#contains(Object)
 */
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    //调用批量删除，后续分析
    return batchRemove(c, false);
}


/**
 * 通过一个过滤器接口实现，来实现删除
 */
@Override
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    //用bitset来存储哪些下标对应的元素要删除，哪些下标对应的元素要保存
    //这里不清楚BitSet的用法的，可以先行了解一下
    final BitSet removeSet = new BitSet(size);
    //判断并发修改用
    final int expectedModCount = modCount;
    final int size = this.size;
    //按顺序遍历且没有并发修改
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        //利用过滤器匹配元素，如果匹配，则删除计数+1，并将下标进行存储
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    //判断是否存在并发修改
    if (modCount != expectedModCount) {
        //抛出并发修改异常
        throw new ConcurrentModificationException();
    }

    // shift surviving elements left over the spaces left by removed elements
    //判断是否有要删除的元素
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            //下一个要保存的元素
            i = removeSet.nextClearBit(i);
            //存放到新数组
            elementData[j] = elementData[i];
        }
        //把实际要保存的元素之后的全部置为null，用以GC
        //实际上，上面的操作已经将要保留的元素全部前移了，后面的元素都是不保留的，所以要置为null来帮助gc
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let gc do its work
        }
        //设置size
        this.size = newSize;
        //判断是否并发修改
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}


/**
 * 删除list中指定范围的元素
 * 
 * Shifts any succeeding elements to the left (reduces their index).
 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 * (If {@code toIndex==fromIndex}, this operation has no effect.)
 *
 * @throws IndexOutOfBoundsException if {@code fromIndex} or
 *         {@code toIndex} is out of range
 *         ({@code fromIndex < 0 ||
 *          fromIndex >= size() ||
 *          toIndex > size() ||
 *          toIndex < fromIndex})
 */
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    //范围删除时，其实数组被分成三个部分
    //分别为[保留区 - 删除区 - 保留区]
    //实际操作，则是计算出最后那部分保留区的长度
    //利用arraycopy拷贝到第一个保留区的后面
    //然后置空多余部分，帮助GC
    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;
}

//最后，来看一下批量删除这个私有方法

/**
 * 批量删除
 */
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++)
            //这里其实有可能抛异常的
            //complement
            //为false时，则证明下标r的元素不在删除集合c中，所以这个时候存储的是不删除的元素

            //为true时，则证明下标r的元素在删除集合c中，所以这个时候存储的是要删除的元素
            
            //这个布尔值的设计很巧妙。所以本方法可以供removeAll、retainAll两个方法来调用
            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;
        }
        //如果有需要删除的元素的话，则证明有一部分位置需要只为null，来帮助GC
        //并且设置是否有修改的标志为true
        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;
}

至此，删除相关的方法都已经分析完毕。

有几个比较有意思的应用

• BitSet 标志哪些下标要删除，哪些不删除
• batchRemove 方法中的布尔值很巧妙

get

作为数组型的list，获取方法时比较简单的，只需要根据给定下标，读取指定下标的数组元素即可。

public E get(int index) {
    //范围检查
    rangeCheck(index);

    return elementData(index);
}

contains

当前list是否包含指定元素

/**
 * 返回布尔值表示是否包含
 */
public boolean contains(Object o) {
    //实际上是判断下标是否存在
    return indexOf(o) >= 0;
}

/**
 * 指定元素在list中首次出现的下标，不存在则返回-1
 */
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;
}

clear

清空缓冲数组。

public void clear() {
    //修改计数 + 1
    modCount++;

    // clear to let GC do its work
    //全部置为null，帮助GC
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    //size设置为0
    size = 0;
}

以上相关方法基本都已经介绍完毕。

总结

Array相比其他集合框架，如Map、Set之类的，还是比较简单的。

只需要了解相关方法的应用和原理，注意下标越界问题，以及内部的缓冲数组是如何扩容的，基本上就OK了。

溜了溜了。有帮助的话给格子点个赞呗~_3Q

我的博客即将入驻“云栖社区”，诚邀技术同仁一同入驻。