jdk源码追踪-ArrayList

红太狼 2022-02-26 10:52 258阅读 0赞

### List ###

List是有序列，所以定义的接口中都有基于index的各种方法。

public interface List<E> extends Collection<E> {
        E get(int index);
        E set(int index, E element);
        void add(int index, E element);
        E remove(int index);
        int indexOf(Object o);
    
        @Override
        default Spliterator<E> spliterator() {
            return Spliterators.spliterator(this, Spliterator.ORDERED);
        }
    }

#### AbstractList ####

AbstractList是List抽象基类，`ArrayList`，`LinkedList`都是它的子类或孙子类。它采用模版方法模式通过调用抽象方法`get(int index)`实现`iterator()`基本算法，它有`get(int index)`，`add(int index, E element)`，`remove(int index)`三个抽象方法需要自己去实现。

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

#### ArrayList ####

ArrayList是由数组实现，基本操作实现遵循数据结构中的线性表。实现`add(int index, E element)`，`remove(int index)`，`iterator()`方法。

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
    
        //默认容器大小，小于10时，第一次扩容
        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;
    
        //创建一个空数组
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    }

下面介绍Array对于add，remove，iterator方法的源码实现

`add(int index, E element)`方法通过两次数组copy实现的，具体实现是

1.  判断插入后`size+1`是否越界，越界新建长度为原长1.5倍的数组并copy；
2.  接着将`index`到`length-1`的元素复制到`index+1`到`length-1`；
3.  然后替换index的元素为插入元素；

如\[1,2,3\]在index为2的插入5，步骤2数组为\[1, 2, 2, 3\]，步骤3数组为\[1, 5, 2, 3\]。

> ArrayList初始化的长度为0，第一次加节点时，长度为10。`minCapacity = Math.max(10, length+1)`。

public void add(int index, E element) {
        rangeCheckForAdd(index);
        //验证大小，判断是否扩容
        ensureCapacityInternal(size + 1);
        //将index到size的节点，copy到index+1到size
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    //扩容
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // copy一个新数组对象
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

`remove(int index)`实现原理是将`index+1`到`length-1`的元素复制到`index`到`length-1`。

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

`ArrayList`实现了迭代器，是为了避免ArrayList在迭代过程中数组结构发生变化的问题，称为Fail-Fast机制。

Fail-Fast就是一个乐观锁，实现如下。

ArrayList有一个modCount属性，在`add()`，`remove()`执行开始，`modCount++`。`ArrayList`创建迭代器对象时，会复制当前`modCount`到`expectedModCount`，迭代器每次执行`next()`，`remove()`，`forEachRemaining()`时，都判断`modCount`是否与`expectedModCount`相同，若不相同，则抛出异常。

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 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];
        }
    
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }