较真儿学源码系列-ArrayList(逐行源码带你分析作者思路)

时间:2020-9-9 作者:admin

Java版本:8u261。


1 简介

ArrayList作为最基础的集合类,其底层是使用一个动态数组来实现的,这里“动态”的意思是可以动态扩容(虽然ArrayList可以动态扩容,但是不会动态缩容)。但是与HashMap不同的是,ArrayList使用的是*1.5的扩容策略,而HashMap使用的是*2的方式。还有一点与HashMap不同:ArrayList的默认初始容量为10,而HashMap为16。

有意思的一点是:在Java 7之前的版本中,ArrayList的无参构造器是在构造器阶段完成的初始化;而从Java 7开始,改为了在add方法中完成初始化,也就是延迟初始化。在HashMap中也有同样的设计思路。

另外,同HashMap一样,如果要存入一个很大的数据量并且事先知道要存入的这个数据量的固定值时,就可以往构造器里传入这个初始容量,以此来避免以后的频繁扩容。


2 构造器

/**
 * ArrayList:
 * 无参构造器
 */
public ArrayList() {
    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空实现“{}”,这里也就是在做初始化
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 有参构造器
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //initialCapacity>0就按照这个容量来初始化数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //EMPTY_ELEMENTDATA也是一个空实现“{}”,这里也是在做初始化
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //如果initialCapacity为负数,则抛出异常
        throw new IllegalArgumentException("Illegal Capacity: " +
                initialCapacity);
    }
}

3 add方法

3.1 add(E e)

添加指定的元素:

/**
 * ArrayList:
 */
public boolean add(E e) {
    //查看是否需要扩容
    ensureCapacityInternal(size + 1);
    //size记录的是当前元素的个数,这里就直接往数组最后添加新的元素就行了,之后size再+1
    elementData[size++] = e;
    return true;
}

/**
 * 第6行代码处:
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    /*
    minCapacity = size + 1

    之前说过,DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空实现“{}”,这里也就是在判断是不是调用的无参构造器
    并第一次调用到此处
     */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        /*
        如果是的话就返回DEFAULT_CAPACITY(10)和size+1之间的较大者。也就是说,数组的最小容量是10

        这里有意思的一点是:调用new ArrayList<>()和new ArrayList<>(0)两个构造器会有不同的默认容量(在HashMap中
        也是如此)。也就是说无参构造器的初始容量为10,而传进容量为0的初始容量为1。同时这也就是为什么会有
        EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA这两个常量的存在,虽然它们的值都是“{}”
        原因就在于无参构造器和有参构造器完全就是两种不同的实现策略:如果你想要具体的初始容量,那么就调用有参构造器吧,
        即使传入的是0也是符合这种情况的;而如果你不在乎初始的容量是多少,那么就调用无参构造器就行了,这会给你默
        认为10的初始容量
         */
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //如果调用的是有参构造器,或者调用无参构造器但不是第一次进来,就直接返回size+1
    return minCapacity;
}

/**
 * 第16行代码处:
 */
private void ensureExplicitCapacity(int minCapacity) {
    //修改次数+1(快速失败机制)
    modCount++;

    /*
    如果+1后期望的容量比实际数组的容量还大,就需要扩容了(如果minCapacity也就是size + 1后发生了数据溢出,
    那么minCapacity就变为了一个负数,并且是一个接近int最小值的数。而此时的elementData.length也会是一个接近
    int最大值的数,那么该if条件也有可能满足,此时会进入到grow方法中的hugeCapacity方法中抛出溢出错误)
     */
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    //获取扩容前的旧数组容量
    int oldCapacity = elementData.length;
    //这里扩容后新数组的容量是采用旧数组容量*1.5的方式来实现的
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    /*
    如果新数组容量比+1后期望的容量还要小,此时把新数组容量修正为+1后期望的容量(对应于newCapacity为0或1的情况)

    这里以及后面的判断使用的都是“if (a - b < 0)”形式,而不是常规的“if (a < b)”形式是有原因的,
    原因就在于需要考虑数据溢出的情况:如果执行了*1.5的扩容策略后newCapacity发生了数据溢出,那么它就一样
    变为了一个负数,并且是一个接近int最小值的数。而minCapacity此时也必定会是一个接近int最大值的数,
    那么此时的“newCapacity - minCapacity”计算出来的结果就可能会是一个大于0的数。于是这个if条件
    就不会执行,而是会在下个条件中的hugeCapacity方法中处理这种溢出的问题。而如果这里用的是
    “if (newCapacity < minCapacity)”,数据溢出的时候该if条件会返回true,于是newCapacity会
    错误地赋值为minCapacity,而没有使用*1.5的扩容策略
     */
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    /*
    如果扩容后的新数组容量比设定好的容量最大值(Integer.MAX_VALUE - 8)还要大,就重新设置一下新数组容量的上限

    同上面的分析,如果发生数据溢出的话,这里的if条件可能也是满足的,那么也会走进hugeCapacity方法中去处理
     */
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    /*
    可以看到这里是通过Arrays.copyOf(System.arraycopy)的方式来进行数组的拷贝,
    容量是扩容后的新容量newCapacity,将拷贝后的新数组赋值给elementData即可
     */
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * 第83行代码处:
 */
private static int hugeCapacity(int minCapacity) {
    //minCapacity对应于size+1,所以如果minCapacity<0就说明发生了数据溢出,就抛出错误
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    /*
    如果minCapacity大于MAX_ARRAY_SIZE,就返回int的最大值,否则返回MAX_ARRAY_SIZE
    不管是哪个,这都会将newCapacity重新修正为一个大于0的数,也就是处理了数据溢出的情况
    其实从这里可以看出:本方法中并没有使用*1.5的扩容策略,只是设置了一个上限而已。但是在Java中
    真能申请得到Integer.MAX_VALUE这么大的数组空间吗?其实不见得,这只是一个理论值。实际上需要考虑
    -Xms和-Xmx等一系列JVM参数所设置的值。所以这也可能就是MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)
    其中-8的含义吧。不管如何,当数组容量达到这么大的量级时,乘不乘1.5其实已经不太重要了)
     */
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

3.2 add(int index, E element)

在指定的位置处添加指定的元素:

/**
 * ArrayList:
 */
public void add(int index, E element) {
    //index参数校验
    rangeCheckForAdd(index);

    //查看是否需要扩容
    ensureCapacityInternal(size + 1);
    /*
    这里数组拷贝的意义,就是将index位置处以及后面的数组元素往后移动一位,以此来挪出一个位置
    System.arraycopy是直接对内存进行复制,在大数据量下,比for循环更快
     */
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    //然后将需要插入的元素插入到上面挪出的index位置处就可以了
    elementData[index] = element;
    //最后size+1,代表添加了一个元素
    size++;
}

/**
 * 第6行代码处:
 * 检查传入的index索引位是否越界,如果越界就抛异常
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
    return "Index: " + index + ", Size: " + size;
}

4 get方法

/**
 * ArrayList:
 */
public E get(int index) {
    //index参数校验
    rangeCheck(index);

    return elementData(index);
}

/**
 * 第6行代码处:
 * 这里只检查了index大于等于size的情况,而index为负数的情况
 * 在elementData方法中会直接抛出ArrayIndexOutOfBoundsException
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 第8行代码处:
 * 可以看到,这里是直接从elementData数组中获取指定index位置的数据
 */
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

5 remove方法

5.1 remove(Object o)

删除指定的元素:

/**
 * ArrayList:
 */
public boolean remove(Object o) {
    if (o == null) {
        //如果要删除的元素为null
        for (int index = 0; index < size; index++)
            //遍历数组中的每一个元素,找到第一个为null的元素
            if (elementData[index] == null) {
                /*
                删除这个元素,并返回true。这里也就是在做清理的工作:遇到一个为null的元素就清除掉
                注意这里只会清除一次,并不会全部清除
                 */
                fastRemove(index);
                return true;
            }
    } else {
        //如果要删除的元素不为null
        for (int index = 0; index < size; index++)
            //找到和要删除的元素是一致的数组元素
            if (o.equals(elementData[index])) {
                /*
                找到了一个就进行删除,并返回true。注意这里只会找到并删除一个元素,
                如果要删除所有的元素就调用removeAll方法即可
                 */
                fastRemove(index);
                return true;
            }
    }
    /*
    如果要删除的元素为null并且找不到为null的元素,或者要删除的元素不为null并且找不到和要删除元素相等的数组元素,
    就说明此时不需要删除元素,直接返回false就行了
     */
    return false;
}

/**
 * 第14行和第26行代码处:
 */
private void fastRemove(int index) {
    //修改次数+1
    modCount++;
    //numMoved记录的是移动元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        /*
        这里数组拷贝的意义,就是将index+1位置处以及后面的数组元素往前移动一位,
        这会将index位置处的元素被覆盖,也就是做了删除
         */
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    /*
    因为上面是左移了一位,所以最后一个位置相当于腾空了,这里也就是将最后一个位置(--size)置为null
    当然如果上面计算出来的numMoved本身就小于等于0,也就是index大于等于size-1的时候(大于不太可能,
    是属于异常的情况),意味着不需要进行左移。此时也将最后一个位置置为null就行了。置为null之后,
    原有数据的引用就会被断开,GC就可以工作了
     */
    elementData[--size] = null;
}

5.2 remove(int index)

删除指定位置处的元素:

/**
 * ArrayList:
 */
public E remove(int index) {
    //index参数校验
    rangeCheck(index);

    //修改次数+1
    modCount++;
    //获取指定index位置处的元素
    E oldValue = elementData(index);

    //numMoved记录的是移动元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        /*
        同上面fastRemove方法中的解释,这里同样是将index+1位置处以及后面的数组元素往前移动一位,
        这会将index位置处的元素被覆盖,也就是做了删除(这里是否可以考虑封装?)
         */
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    //同上,将最后一个位置(--size)置为null
    elementData[--size] = null;

    //删除之后,将旧值返回就行了
    return oldValue;
}

6 不要在foreach循环里进行元素的remove/add操作

首先来看一下remove的情况。正例:

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if ("2".equals(item)) {
        iterator.remove();
    }
}

反例:

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");

for (String item : list) {
    if ("2".equals(item)) {
        list.remove(item);
    }
}

运行上面的代码可以看到,使用迭代器的删除操作是不会有问题、能成功删除的;而使用foreach循环进行删除则会抛出ConcurrentModificationException异常,但如果使用foreach循环删除第一个元素“1”的时候又会发现不会抛出异常。那么这到底是为什么呢?

首先来看一下ArrayList中的内部类Itr,每次foreach遍历都是通过它的hasNext和next方法来进行确定的(普通的for循环不是通过这种方式,也就是说普通的for循环不会有这种问题):

/**
 * 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];
    }

    //...
}

而抛出异常是在上面第17行代码处的checkForComodification方法里面抛出的,下面来看一下它的实现:

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

可以看到如果modCount和expectedModCount不等就会抛出ConcurrentModificationException异常。而上面说过,在add方法中的ensureExplicitCapacity方法中,会对modCount修改标志位做+1的操作。这里的modCount是为了做快速失败用的。快速失败指的是如果在遇到并发修改时,迭代器会快速地抛出异常,而不是在将来某个不确定的时间点冒着任意而又不确定行为的风险来进行操作,也就是将可能出现的bug点推前。在包括HashMap在内的很多集合类都是有快速失败机制的。注意:这里的并发修改指的并不都是发生在并发时的修改,也有可能是在单线程中所做的修改导致的,就如同上面的反例一样。

这里拿上面的反例来举例,ArrayList调用了两次add方法,也就是此时的modCount应该为2。而expectedModCount如上所示,一开始会初始化为modCount的值,也就是也为2。

第一次循环:

因为此时的modCount和expectedModCount都为2,所以第一次循环中不会抛出异常,抛出异常都是发生在不是第一次循环的情况中。而这也就是使用foreach循环删除第一个元素“1”的时候不会抛出异常的原因。在next方法走完后,foreach循环方法体中的remove方法的if条件判断不满足,就结束了本次循环。

第二次循环:

第二次循环的hasNext和next方法都是能成功走完的,在这之后会进入到foreach循环方法体中的remove方法中,进行删除元素。而此时的size-1变为了1。上面分析过,在remove方法中的fastRemove方法中,会对modCount+1,也就变为了3。

第三次循环:

然后会走入到第三次循环中的hasNext方法中。按照正常的情况下该方法是会返回false的,但因为此时的size已经变为了1,而此时的cursor为2(cursor代表下一次的索引位置),所以两者不等,错误地返回了true,所以会继续走入到next方法中的checkForComodification方法中,判断此时的modCount和expectedModCount是否相等。因为此时的modCount已经变为了3,和expectedModCount的值为2不等,所以在此抛出了ConcurrentModificationException异常。同时这也就意味着,在foreach循环中做add操作也是会抛出异常的,因为add操作中也会修改modCount和size(具体抛出异常的过程这里就不再分析了,都是类似的)其实只要在foreach循环方法体中有进行修改modCount和size的操作,就都有可能是会抛出异常的。

既然现在已经知道了foreach循环中使用remove/add操作抛出异常的原因,那么就可以分析一下为什么使用迭代器进行相关操作就不会有问题呢?下面来分析一下上面正例的代码,第5行代码处的iterator方法如下:

public Iterator<E> iterator() {
    return new Itr();
}

可以看到iterator方法也是返回了一个Itr内部类。而第6行和第7行代码处的hasNext和next方法也就是Itr内部类中的hasNext和next方法,同时也就是上面分析过的方法,而区别在于第9行代码处的remove操作。这里的remove不是ArrayList中的remove操作,而是Itr内部类中的remove操作:

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

可以看到第7行代码处是调用了ArrayList的remove操作进行删除的,但同时注意第10行代码处会将expectedModCount更新为此时modCount的最新值,这样在next方法中就不会抛出异常了;在第8行代码处会将cursor更新为lastRet(lastRet代表上一次的索引位置),即将cursor-1(因为此时要remove,所以cursor指针需要减一)。这样在hasNext方法中就会返回正确的值了。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。