【Java源码分析】ArrayList源码分析

淡淡的烟草味﹌ 2022-09-23 08:47 51阅读 0赞

类的定义

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

1.  List接口的实现类，AbstractList 的子类，支持随机访问，因此底层实现的数据结构是数组
2.  实现了所有list的操作，允许所有类型的元素，包括NULL
3.  提供计算Array大小的接口，可以看做是一个Vector，区别在于Vector是线程安全的，ArrayList不是
4.  由于底层实现数据结构是数组，所以get set iterator遍历, 以及size判断等都是常数时间。其他操作是线性时间复杂度，而且常数因子比LinkedList要小，因此效率略高
5.  含有一个容量capacity实例，表示容量的大小，随着数据的加入，该实例会自增，自增
6.  非线程安全，因此如果在多线程环境下需要自行处理线程安全问题，也可以使用`Collections.synchronizedList`方法`List list = Collections.synchronizedList(new ArrayList(...));`进行包装，而且最好是在声明变量的时候就考虑是否需要做多线程的处理，避免出错
7.  `ConcurrentModificationException`异常，如果ArrayList的实例在使用迭代器Iterator遍历的时候，如果出现了不是使用这个迭代器所做的remove或者add操作，那么就会直接抛出并发修改的异常。这个异常即使是在单线程下也是会出现的，常见的场景是用迭代器一边遍历一边修改ArrayList对象的时候
8.  对于7中的现象也叫做是`fail-fast`，该行为只能尽量检测出并发异常，但是不能做到绝对的线程安全，所以编程的时候不要因为没有抛出该异常就觉得是线程安全的

构造函数  
三种类型，默认构造(默认构造的Listd的size 为10)，传递size的构造，传递一个Collection对象的构造。

public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    
    public ArrayList() {
        this(10);
    }
    
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

扩容方式

private transient Object[] elementData; // 对象数组，实际存放数据的一个数组容器，默认初始10个Object
    private int size; // 实际存放对象数目
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 最大容量；由于一些虚拟机会在Array首部存储一些信息，所以此处减去8字节 
    
    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.5倍，如果指定值minCapacity比原来容量的1.5倍大，那么按指定值扩容；如果指定值minCapacity比阈值MAX\_ARRAY\_SIZE大，那么按如下策略确定扩容最终大小`(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;`，这样会存在一定的OOM风险

减少容量，用于减少一个ArrayList实例所占存储空间

public void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

从如下的一个侧面说明ArrayList是允许空的对象存入的。

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

连接集合类Collection和线性表Array类的桥梁，该方法将集合中所存储的对象拷贝到一个对象数组中返回

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

该方法还有另外一个多态实现，根据运行时类型返回指定类型的数组

public <T> T[] toArray(T[] a) { ... }

添加一个元素到集合

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

这个是添加到指定位置的，所以比较麻烦，需要拷贝移动。还有一个添加操作是直接添加到尾部，`public boolean add(E e) { ... }`只需要做一次赋值即可

删除指定位置的元素

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; // Let gc do its work
    
        return oldValue;
    }

从代码来看也是比较好懂的，删除指定位置元素，然后指定位置之后的元素前移，这是一个数组拷贝过程。但是需要注意最后一点，就是**将最后一个空出的位置置空，这个问题在Effective Java中有提到过，就是及时的消除过期引用**。对于一些自定义的数组类如果对象被移走了，但是指针没有置为空，那么强引用还是会一直保持，就会导致内存泄露。

另一个删除操作是删除指定对象

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

其中用到了一个私有的删除操作`fastRemove(index)`，该操作的特点是不检查边界也不返回被删除值，毕竟是自己内部调用，已经可以保证边界是正确的。

清空操作

public void clear() {
        modCount++;
    
        // Let gc do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
    
        size = 0;
    }

比较直接，循环置空，然后将对象的清除工作交给GC，注意clear只是将内容清空，集合容器还是在的、

删除集合中某些元素

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

功能就是将所有位于c中的元素全部删除

保留集合中某些元素

public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true);
    }

功能就是将所有位于c中的元素全部保留，不在c中的元素全部删除  
对比这两个方法就可以看出，实际的工作都是由`private boolean batchRemove(Collection<?> c, boolean complement) {}`完成的，当第二个参数是true的时候代表保留元素，否则代表删除。

集合数据的状态保存和恢复

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();
    
        // Write out array length
        s.writeInt(elementData.length);
    
        // Write out all elements in the proper order.
        for (int i=0; i<size; i++)
            s.writeObject(elementData[i]);
    
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    
    }

恢复，将数据从流中取出

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in size, and any hidden stuff
        s.defaultReadObject();
    
        // Read in array length and allocate array
        int arrayLength = s.readInt();
        Object[] a = elementData = new Object[arrayLength];
    
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++)
            a[i] = s.readObject();
    }

类似于序列化和反序列化，这里状态保存和恢复也是成对出现的，保存和恢复的顺序都是一样的，否则不可能得到正确的对象或者集合。注意在**保存状态的时候同样是不能够修改集合的，否则也是抛出并发修改异常**

再来看看ArrayList的迭代器

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

前面说迭代器的时候提到过在使用同一个迭代器迭代访问元素的时候，是不能修改集合的结构的(也就是大小，但是内容变化大小不变还是可以的比如add(index, value)或者set(index, value)是可以的，但是add(value)不可以，该操作会modCount++)，愿意就在于每当初始化一个迭代器实例的时候，该迭代器都保存了当前集合的修改次数。迭代器的每一个操作结束之后都会检查保存的值是否和集合的modCount值相同，如果不同直接抛出异常并且结束，这就是所谓的`fail-fast`

获取子集合操作

public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }

返回从fromIndex到toIndex之间的元素构成的子集合，不包括toIndex。**当toIndex和fromIndex相等的时候返回的是空的子集合而不是空指针**。

注意SubList`private class SubList extends AbstractList<E> implements RandomAccess {}`是ArrayList的一个内部子类，该子类实现了和ArrayList一样的方法.

最后补充一下经常调用的连个拷贝函数`Arrays.copyOf(elementData, newCapacity)`和`System.arraycopy(elementData, index, elementData, index + 1, size - index);`

前者最终调用了Arrays的`copyOf()`方法

public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

该方法实现如下

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

实现的过程是先确定泛型类型，然后调用系统的copy函数，将指定集合中的元素拷贝到目标集合中，目标集合是一个新建的newLength大小的集合。在实际的拷贝过程中还是调用了`System.arraycopy()`函数

是一个Native方法

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

该方法将srcPos+length-1个元素拷贝到dest中从destPos到destPos+length-1。由于是Native方法，所以在JDK中是看不到的，但是可以在openJDK中查看源码。该函数实际上**最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组**。Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。