ArrayList源码分析

总结

总结放前面防止太长不看:

  1. ArrayList内部是用数组实现的。
  2. 如果使用无参构造函数建立ArrayList,在添加第一个元素的时候会分配10个元素的空间。
  3. ArrayList的扩容是以1.5倍为基准的。
  4. ArrayList是线程不安全的,有fail-fast机制作改动保障。

层次图

ArrayList的Hierarchy:

ArrayList层次结构

先来看看List接口:

List接口

List代表有序集合,元素可以重复。

List家族一览:

List层次

默认实现方法:

default void replaceAll(UnaryOperator operator);

以指定的方法替换List中的所有元素,UnaryOperator是一个函数式接口,输入一个类型对象,返回一个同类型对象。

default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        li.set(operator.apply(li.next()));
    }
}

示例:

List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(3);
list.add(5);
list.replaceAll(a->a+1); //list = [2,4,6]

default void sort(Comparator<? super E> c);

根据排序方法排序。还是先转为了Array再使用Arrays的sort方法进行排序。

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

AbstractList接口

AbstractList接口继承自AbstractCollection,为什么要提它呢,因为里面有个重要的字段modCount,用于迭代器遍历元素时检查列表中的元素是否发生结构性变化。

参考下面“重要的内部类”中迭代器里next方法的实现。

重要的字段

transient Object[] elementData;

ArrayList的元素存储在这个数组中。

private int size;

记录空间大小。

重要的内部类

Itr实现了迭代器Iterator,ListItr实现了集合迭代器ListIterator

两者的介绍: 谈谈java中的Iterator

next的实现:

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

其中的checkForComodification():

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

modCount在ArrayList每次add或者remove它的值都会加1。在初始化迭代器的时候,令expectedModCount = modCount,在迭代器迭代的过程中,如果modCount被改变了,就会造成expectedModCount不等于modCount,抛出ConcurrentModificationException警告。

比如下面这段程序就会抛出警告:

为什么在迭代器循环的时候不让使用list.remove修改元素呢?

有多线程下被影响的考虑,更重要的是,强制了在迭代器迭代的时候只能使用iterator.remove移除元素.

比如上面这段程序应该改成:

构造方法

已知ArrayList的元素是存放于一个数组中,那么在初始化一个ArrayList对象的时候会分配一个多大的数组?

先看两个构造方法:

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

其中常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
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);
    }
}

使用一个初始容量初始化ArrayList。
如果传入的参数大于0,则分配一个这么大的数组。
注意到如果这里的initialCapacity等于0,令其等于常量EMPTY_ELEMENTDATA也是一个空数组。

那为什么要区分EMPTY_ELEMENTDATADEFAULTCAPACITY_EMPTY_ELEMENTDATA呢

因为他们是两个不同对象的引用,ArrayList通过这个区分当前对象是用无参构造方法创建的还是由ArrayList(0)这样一个构造方法创建的

在后文“重要的内部方法”中的calculateCapacity方法,当第一个元素被加进来的时候就能知道应该扩容多少。

重要的内部方法

空间分配相关

private static int calculateCapacity(Object[] elementData, int minCapacity);

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

这个方法用于计算:

当原来数组为空,第一次插入元素的时候,数组应该分配多少空间,DEFAULTCAPACITY_EMPTY_ELEMENTDATA呼应了上面构造方法中的无参构造方法,常量DEFAULT_CAPACITY=10

这说明:如果ArrayList是以无参构造方法建立的,在添加第一个元素时会直接分配10个元素的空间。

private void grow(int minCapacity);

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //即newCapacity = 1.5*oldCapacity
    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.5倍为基准扩容的,如果1.5倍后大于MAX_ARRAY_SIZE (Integer.MAX_VALUE - 8),则使用hugeCapacity(minCapacity)确认(size是int类型,不能超过int范围的最大值)。

元素获取、增改相关

E elementData(int index);

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

取元素,就是从数组中获取元素,是get等方法的依赖。

private void rangeCheck(int index);

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

边界检查。

rangeCheck方法是提供给get,remove,set之类的方法检查的,是给已经存在元素的集合操作的,范围0至size-1,这个方法把检查负责的职责交给了数组的访问,像get(-1)时会报异常ArrayIndexOutOfBoundsException。

private void rangeCheckForAdd(int index);

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

这个方法是提供给add和addAll的,会检查负数。因为如果扩容了数组再抛出异常就白扩容了。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/arraylist%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90/