java集合类型源码解析之ArrayList

时间:2022-03-09 14:07:15

前言

作为一个老码农,不仅要谈架构、谈并发,也不能忘记最基础的语言和数据结构,因此特开辟这个系列的文章,争取每个月写1~2篇关于java基础知识的文章,以温故而知新。

如无特别之处,这个系列文章所使用的java版本都是1.8.0。

第一篇当然谈ArrayList了,因为这是java最常用的list集合类型,它内部使用数组作为存储空间,在增加元素时能够自动增长。总体来说,ArrayList的实现比较简单,这里不罗列它的全部代码,只看一些有意思的地方。

成员变量

    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;
  • DEFAULT_CAPACITY 常量,初始话的时候如果没有指定capacity,使用这个值;
  • EMPTY_ELEMENTDATA 空数组,所有空的ArrayList的elementData可以共享此值,避免使用null;
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是elementData的值,代表初始化容量为默认值(非0)的存储空间,但是暂时还没有实际元素,等到需要增长存储空间时,与EMPTY_ELEMENTDATA的策略不一样;
  • elementData 提供存储空间的数组;
  • size list长度,list的元素存储在elementData[0~size)。

PS:说实话,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);
    }
}

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

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
  • 第一种,指定初始容量;
  • 第二种,使用默认容量,此时DEFAULTCAPACITY_EMPTY_ELEMENTDATA派上用场;
  • 第三种,使用另一个集合来初始化,使用了集合的toArray方法,值得注意的是,集合的toArray返回的不一定是Object[]类型。

空间增长

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

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

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

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

这是三个私有方法

  • ensureCapacityInternal,在增长容量前加了一层检查,如果elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,确保容量不小于默认容量;
  • ensureExplicitCapacity,检查数组的容量是否确实需要扩充;
  • grow,执行数组扩容,先尝试扩容一半,看是否满足需求;也就是说空间的扩容,不是严格按照输入参数来的。

这里有一个疑问,ensureExplicitCapacity方法的那句modCount++为什么会在if语句外执行.

增删改查

基本操作方法有很多,这里只列几个有代表性的。

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

ArrayList查找元素的过程就是遍历数组,而且null也是可以查找的。

2、插入:

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

插入前做了范围检查,并确保容量,最后把插入位置之后的元素全部再往后挪一个位置;移动内存使用了System.arraycopy,这是一个native方法

值得注意的是,add方法并没有直接调用modCount++,因为ensureCapacityInternal里面调用了,所以我猜测modCount++放在ensureCapacityInternal里面纯碎就是为了更方便,即使有些没有修改数组的场景也会导致modCount被修改。

3、删除:

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

把删除位置之后的元素全部往前挪一个位置,注意的是,最后空出来的那个内存位置要置成null,否则会内存泄露

4、批量删除

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
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;
}

removeAll删除集合参数里的所有元素,反过来retainAll删除不在集合参数里面的所有元素,二者都通过batchRemove来实现。

batchRemove使用两个游标w,r来执行连续的元素移动,w代表写入位置,r代表读取位置,读取一个元素后判断是否应该删除,如果是那么继续读下一个,否则写入w位置。 这样,到了最后w位置就是list的末尾,w~r之间的位置需要置成null。

值得注意的是,最后的收尾逻辑放到finally里面,保证了一定程度的异常安全性。如果发生异常,那么剩余未扫描的元素(r位置之后的元素),要拷贝到w之后;这样一来,batchRemove可能执行了一半而失败,但ArrayList的状态并没有乱掉。

迭代器

ArrayList支持两种迭代器,Iterator和ListIterator,后者是前者的增强版本,可以向前移动、插入元素、返回元素索引。

这里就解读下Iterator实现,ListIterator是差不多的。

1、Iterator成员变量

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;

    public boolean hasNext() {
        return cursor != size;
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

Iterator实现为ArrayList的非静态内部内,因此可以直接访问ArrayList的成员字段,它只需要记住当前位置(cursor)即可。lastRet指向上一次next操作返回的元素位置,这个是非常有必要的,因为在迭代器上,如果要对元素做一些操作,都是针对这个位置的元素。

expectedModCount是ArrayListmodCount的快照,防止在迭代过程中,意外对list执行修改。

2、next操作

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

很简单,几乎没啥可解释的。

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

remove操作会更新expectedModCount,这是一个允许的、意料之中的修改操作。

4、modCount
modCount定义在基类AbstractList当中,使用来追踪list修改的,自身的值没有实际意义。

modCount主要最用,就是在发生意外的修改时,快速失败,而不是等到出现难以追踪的数据状态错误时才失败。思路是,如果在执行一个操作的过程中,如果不期望ArrayList被其他操作所修改,那么可以在开始时记录一下modCount快照,在执行操作的过程中,通过比较ArrayList的modCount和这个快照来判定ArrayList是否被修改了,然后抛出ConcurrentModificationException。

ConcurrentModificationException看起来像是多线程相关的,但实际上这里和多线程一点关系都没有,ArrayList不是线程安全的,modCount的设计也没有针对多线程的意思。

SubList

ArrayList的subList可以直接通过游标锁定原ArrayList的一个区段,从而避免了copy。
由于SubList要实现List的全部接口,全部源码比较多,这里讲解一下get方法的实现,其他的都是类似的。

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }
    
    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return ArrayList.this.elementData(offset + index);
    }
    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }
}

1、首先,构造函数可以看出来,SubList实际就是通过索引来操作原ArrayList的数据,只不过加一个偏移(offset)和长度限制(size)。

2、get方法检查modCount,说明在SubList的生命周期内,期望parent ArrayList不会被修改。这也说明SubList只适合做临时变量,不适合长期存活,除非原ArrayList是不变的。

AbstractList

AbstractList是ArrayList的基类,它也实现了Iterator,ListIterator,SubList的一个版本。不过AbstractList并不清楚存储的实现细节,因此只能基于list的公共接口来实现,因此效率肯定不佳。

比如AbstractList的Iterator的next方法是这样实现的:

public E next() {
    checkForComodification();
    try {
        int i = cursor;
        E next = get(i);
        lastRet = i;
        cursor = i + 1;
        return next;
    } catch (IndexOutOfBoundsException e) {
        checkForComodification();
        throw new NoSuchElementException();
    }
}

获取元素用的是list.get方法:E next = get(i)