ArrayList源码解析

总览

首先搜索ArrayListAbstractList类,复制代码并新建同名class,方便后面Debug及打印控制台信息。

准备工作

复制ArrayList类及AbstractList类源码到你的包目录下,并修改相关信息以便进行断点及打印log,在阅读本文过程中,建议使用Junit进行测试并使用Debug来观察数据变化。

内部参数

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
  1. DEFAULT_CAPACITY:默认初始容量
  2. EMPTY_ELEMENTDATA:空实例对象的默认数组
  3. DEFAULTCAPACITY_EMPTY_ELEMENTDATA:与EMPTY_ELEMENTDATA类似,主要用于区分在首次添加元素时判断如何进行扩容
  4. elementData:ArrayList中实际存储元素的Object数组
  5. size:ArrayList中实际包含的元素数量

构造方法

要new 一个对象,那么就需要有一个构造方法,ArrayList包含了如下几种构造方式。

public ArrayList()
public ArrayList(int initialCapacity)
public ArrayList(Collection<? extends E> c)

我们创建一个测试类来尝试使用如上几个方法进行创建ArrayList对象。

首先我们在这些构造方法上进行断点,然后Debug执行下面的测试代码,看看他们是如何执行的。

        ArrayList list = new ArrayList();
        ArrayList list2 = new ArrayList(100);
        ArrayList list3 = new ArrayList(Arrays.asList("a","b","c"));

ArrayList()

在执行第一行代码时,构造函数有了如下的操作

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

此处可以理解为,将ArrayList的elementData引用指向内置的默认对象数组。

ArrayList(int initialCapacity)

在执行第二行代码时,构造函数是具有以下的实现

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

首先,检查了构造函数传入的参数大小

  1. 如果大于0,则将内置的elementData指向一个新的Object数组(数组大小为initialCapacity)
  2. 如果initialCapacity值为0,则将elementData引用指向EMPTY_ELEMENTDATA这个内部Object数组。
  3. 如果以上两者均不满足的话,则会抛出IllegalArgumentException并附带initialCapacity参数

ArrayList(Collection c)

在第三行代码中,使用了Arrays.asList来获取一个容器对象,并使用该对象作为参数传递到ArrayList的构造方法中,让我们来看看这个构造方法执行了哪些操作。

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
  1. 使用c.toArray()方法将容器中的对象引用传递给elementData
  2. 接着将elementData.length参数赋给size,然后判断是否与0相等,这里由于我们传递的是3个参数,因此值均为3,所以该条件成立,继续执行第五行的判断
  3. 第五行这个判断比较有意思,请注意第四行的注释,这里不再过多叙述,在JDK9中已经修复,有关更多信息请参阅JDK-6260652
  4. 在第六行代码中,elementData获得了一个新的数组拷贝对象。
  5. 在最后一个else分支中,如果你传递的容器类中对象数量为0,则将elementData指向内部的空Object数组

常用方法解析

add(E e)

首先我们来看一下这个方法

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

我们先来看第三行,它执行的是将elementData数组中size++位置的元素指定为传入的参数,在最开始我们就知道,size是数组的实际大小,这就非常好理解了,它执行了size++后,那elementData[size]++这个位置就是数组中的最后一个位置了,因此也就有了添加在最末尾的效果。

第四行,没什么好说的,返回了一个true,代表成功。

重点是第二行

ensureCapacityInternal(size + 1);

它执行了ensureCapacityInternal方法,并传递了一个size+1的参数。

ensureCapacityInternal

ensureCapacityInternal这个方法,执行了如下操作。

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
calculateCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
  1. 判断了elementData与DEFAULTCAPACITY_EMPTY_ELEMENTDATA是否为同一个对象,如果满足该条件,则计算默认构造大小(10)与传入的minCapacity(最小数组大小要求)谁大,然后返回两者间的最大值。
  2. 如果不是同一个对象,那么就返回minCapacity(最小elementData数组大小要求)
ensureExplicitCapacity
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
  1. 执行了modCount++操作(注:此列表结构已被修改次数,来源于AbstractList)
  2. 判断传入的最小数组大小要求值是否大于现有数组大小,如果大于,则执行grow(minCapacity);操作
grow
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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. oldCapacity代表数组原有容量大小
  2. newCapacity代表原有容量扩大1.5倍后大小
  3. 5-6 如果原有容量扩大1.5倍后小于最小扩充要求,那么将newCapacity指定为最小扩充要求值
  4. 7-8 如果newCapacity比ArrayList最大容量大,那么执行hugeCapacity方法,hugeCapacity方法判断如果最小扩展要求值小于0则抛出异常,否则进行判断最小扩展要求值是否大于MAX_ARRAY_SIZE,如果大于则返回最大Int值,如果不大于则返回MAX_ARRAY_SIZE值。
  5. 10 将elementData指向到新拷贝的数组,该数组大小为newCapacity

由此我们可以得知,ArrayList扩容通常为原数组大小的1.5倍,并且ArrayList最大容量为int最大值。

MAX_ARRAY_SIZE的值为int最大值-8,-8是因为有些VM会在数组中保留一些词

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

addAll(Collection c)

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

首先执行toArray操作转为一个Object数组,然后拿到该数组的长度。

接着对当前ArrayList执行检查扩容操作,然后System.arraycopy方法将a数组附加到elementData数组的size下标后,然后设置size的大小,最后根据传入的容器长度来返回添加状态

addAll(int index, Collection c)

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这个下标值是否合法,然后将传入的容器对象转为数组并拿到该数组的长度,然后执行ensureCapacityInternal方法进行扩容检查操作

接着拿到原数据位移量numMoved,size – index就是判断该位移量是否是数组的最后一个下标值,如果不是将c附加到数组末尾的话,就先执行一次System.arraycopy操作,将index下标之后的所有元素,复制一份到index +numNew下标之后,然后再执行一次System.arraycopy操作,将a数组中的值放到elementData中index下标之后,最后将size大小设置为新的数组元素数量,然后返回操作状态,具体的内存图如下。

elementData:{1,2,3,4,5,6,7,8,9,10}

c:{1,2,3}

index:5

第10行代码前:elementData-》{1,2,3,4,5,6,7,8,9,10}

第10行代码后:elementData-》{1,2,3,4,5,6,7,8,6,7,8,9,10}

第13行代码后:elementData-》{1,2,3,4,5,1,2,3,6,7,8,9,10}

get(int index)

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

其中index为传入的下标值,rangeCheck(index);执行的是检查该下标值是否合法,若不合法则抛出IndexOutOfBoundsException异常。

elementData(index)方法就更简单了,先看看它的实现

E elementData(int index)

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

返回数组中指定下标,并转成类型。

remove()

remove方法有两种方式,一种是直接根据下标值删除,一种是根据具体的对象来删除。

我们先来看看第一种。

remove(int index)

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

还是熟悉的rangeCheck方法,检查该下标是否不正确。

接着执行modCount++操作。

然后获取要需要删除的这个元素

接着获取到numMoved这个值,该值代表了需要移动的元素数量

然后判断需要移动的元素数量是否大于0,如果大于0则执行System.arraycopy操作,该操作会将需要删除的该元素后面的元素向前移动一位,此时末尾会出现两个相同的元素。

然后执行elementData[–size] = null;操作,将最末尾元素替空,完成删除操作,由于指定为null,因此下次GC时可以明确GC掉该元素对象

最后返回这个已被删除的元素

简单总结以下,就是先检查参数是否合法,然后判断要移动多少元素,接着移动元素,然后置空,最后返回被删除的元素。

remove(Object o)

还是先看源码

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

逻辑很简单,如果传入对象为空,那么执行for循环判断是否为空然后执行fastRemove(index)操作删除,如果不为空则执行else中for循环判断是否equals然后执行fastRemove(index)操作删除然后返回true,如果传入的参数既不为空,也在列表中找不到,就返回false,即删除失败。

fastRemove(int index)

可以看到,在上面的remove(Object o)方法中,唯一比较需要关注的就是这个方法了,在执行完这个方法之后就返回了true,那么这个方法又执行了哪些操作呢?

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
}

modCount++;就不说了,下面的代码是不是有一些熟悉的味道呢?是的,在remove(int index)方法中,也有着相同的代码出现,那么fastRemove和remove方法到底有什么区别呢?

  1. fastRemove为私有方法,remove方法公有
  2. fastRemove方法不执行下标检查操作,remove方法检查下标合法性

removeAll(Collection c)

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

第二行判断传入对象是否为NULL,为NULL抛出空指针异常。

还是先看batchRemove()方法

batchRemove(Collection c, boolean complement)
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;
}

其中r变量作为循环的遍历下标使用,w变量作为替换数组中的值下标使用。modified则是代表此次batchRemove()方法执行成功或失败。

先看try部分,执行了一个for循环,在for循环中拿出当前List中的各个对象和传入的容器对象中进行对比,若在c中没有找到elementData[r]这个对象,那么就将elementData[r]的值赋给elementData[w++],也就是执行了将数组中的值向前移动的操作。

再看finally部分,其中的注释表面了,如果在try部分出现了异常,那么finally部分会处理剩下的操作。

其中第一个if,判断了try中的for循环是否走完,如果没有走完,则使用System.arraycopy()方法,将剩下没有遍历到的元素复制到w下标后,再对w进行赋值告诉下个if需要处理具体范围的元素。

第二个if则是用于清除List末尾的元素,在try中的for循环只是将值重新赋值,因此在循环过后还有一些元素可能存在数组的末尾处,因此在该if中有一个for循环,处理在w后面的元素,将其置为NULL,modCount += size – w;则表示了这次操作执行了多少次的变更次数,并将size的大小设置为w的值,以及将返回值设置为true代表成功。

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

这段代码很简单,执行indexOf方法并判断返回值是否大于0来决定返回true还是false

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

是不是还是熟悉的味道呢?在上面的remove(Object o)方法中,也就是多了一行fastRemove(index);,以及返回值略有不同而已。

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

与indexOf(Object o)类似,不过它是从最末尾开始查找,查找到合适的元素则返回。

trimToSize()

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
    }
}

该方法是将当前ArrayList对象的容量修改为list的实际拥有元素个数大小,可以用此方法来进行最小化操作。

在第3行判断了size是否小于数组容量的长度,以避免不必要的复制操作。

然后进行 size是否 = 0判断,如果当前size的大小为0,则将默认的EMPTY_ELEMENTDATA对象的引用赋给elementData,否则就进行Arrays.copyOf操作然后指向给elementData。

for循环迭代删除所有元素问题

通常面试中会问到这么一道题,为什么在批量删除ArrayList元素时,是使用迭代器而非for循环或foreach来进行迭代删除,很多人都会回答说,因为使用for循环或foreach迭代删除,有可能出现线程安全问题,那么到底是不是这样呢?

先看代码

public class ListTest {

    private static ArrayList<Integer> list;

//    Arrays.asList(1,2,3,4,5,6,7,8,9,10
    @Test
    public void test() throws InterruptedException {
        list = new ArrayList(10);
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        Thread t1 = new Thread(new ThreadRemove(),"T1");
        Thread t2 = new Thread(new ThreadRemove(),"T2");
        t1.start();
        t2.start();
        Thread.sleep(1000);
        for (Integer i:list) {
            System.out.println(i);
        }
    }

    class ThreadRemove implements Runnable{

        @Override
        public void run() {
            for (int i = 0; i < list.size(); i++) {
                System.out.println(Thread.currentThread().getName() + ": i:" + i +" " + "remove:" + list.remove(i));
            }
        }
    }
}

首先我们定义了一个静态ArrayList,然后在test方法中进行初始化并添加了0-9总计十个数字,接下来我们创建了两个线程,并执行了start方法,这两个线程对象都执行了同一件事情,就是使用for循环删除list中的元素。

运行结果如下:

T2: i:0 remove:0
T2: i:1 remove:3
T2: i:2 remove:5
T2: i:3 remove:7
T2: i:4 remove:9
T1: i:0 remove:0
T1: i:1 remove:4
T1: i:2 remove:8
2
6

可以看到,在执行完毕后,还剩下元素2和6没有被成功删除,接下来我们测试使用foreach来删除元素

修改run方法中代码变成如下内容

for (Integer i:list) {
   System.out.println(Thread.currentThread().getName() + ": i:" + i +" " + "remove:" + list.remove(i));
}

运行程序,得到如下控制台输出:

Exception in thread "T1" java.util.ConcurrentModificationException
    at com.noesblog.List.ArrayList$Itr.checkForComodification(ArrayList.java:885)
    at com.noesblog.List.ArrayList$Itr.next(ArrayList.java:835)
    at com.noesblog.List.ListTest$ThreadRemove.run(ListTest.java:36)
    at java.lang.Thread.run(Thread.java:748)
T1: i:0 remove:true
Exception in thread "T2" java.util.ConcurrentModificationException
    at com.noesblog.List.ArrayList$Itr.checkForComodification(ArrayList.java:885)
    at com.noesblog.List.ArrayList$Itr.next(ArrayList.java:835)
    at com.noesblog.List.ListTest$ThreadRemove.run(ListTest.java:36)
    at java.lang.Thread.run(Thread.java:748)
T2: i:1 remove:true
2
3
4
5
6
7
8
9

可以看到抛出了ConcurrentModificationException异常,并且元素中仅删除掉了0,1两个元素,因此使用foreach无法迭代删除掉list中的所有元素。

那么应该如何解决呢?很多人想到了加锁,在每次访问list对象时使用,但是很明显,这是无效的。

所以?如何使用for循环来安全删除ArrayList中的所有元素呢?

修改代码如下:

@Override
public void run() {
    for (int i = 0; i < list.size();) {
        System.out.println(Thread.currentThread().getName() + ": i:" + i +" " + "remove:" + list.remove(i));
    }
}

或修改成如下:

public void run() {
    for (int i = list.size() - 1; i >= 0;i--) {
        System.out.println(Thread.currentThread().getName() + ": i:" + i +" " + "remove:" + list.remove(i));
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

均可删除掉list中所有元素,但需要注意的是,仍有可能出现IndexOutOfBoundsException异常

总结

在本文中,你可以理解到ArrayList通常所拥有的元素不超过Integer.MAX_VALUE - 8个,也知道了ArrayList是如何进行扩容与删除对象,对于ArrayList使用中一些可能的错误,你也有了更清楚的认识。

发表评论

电子邮件地址不会被公开。 必填项已用*标注