Java：ArrayList源码分析（JDK1.7）

短命女 2022-05-27 10:43 246阅读 0赞

## ArrayList源码分析 ##

注：JDK1.7  
首先先来个总体的认识，ArrayList底层是用数组实现的。在插入值时如果超过了当前数组的大小，则会进行扩容操作，每次增加的大小为原来大小的“一半”（偶数一半，奇数减一的一半），并且按照新的大小新建一个相同类型的数组，然后将原数组中的值copy进新的数组，并修改引用。  
默认创建ArrayList情况下：  
![这里写图片描述][70]  
然后了解下ArrayList继承和实现的类和接口

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

总体有一个认知后从新建一个ArrayList讲起吧。

--------------------

## 初始化 ##

首先新建一个ArrayList:`List<String> list = new ArrayList<String>();`  
相关源代码

private static final Object[] EMPTY_ELEMENTDATA = {};
    private transient Object[] elementData;
    1.
    //首先会调用构造函数ArrayList()
    public ArrayList() {
        //调用父类构造函数
        super();
        //初始化elementData，ArrayList实际用来存储信息的数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
    
    2.
    //父类构造函数就略过了，在调用父类构造函数时会初始化modCount 成员变量，
    //之后ArrayList就使用该变量来记录自身经历的修改次数。
    AbstractList.class
    protected transient int modCount = 0; //修改/操作次数

这样一个空的ArrayList就创建完毕了，当然，我们还可以自己定义初始数组的大小。之后都以默认新建方式说明。  
`List<String> list = new ArrayList<String>(20);`

public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

--------------------

## add()函数 ##

相关源代码

/** * The size of the ArrayList (the number of elements it contains). * * @serial */
    private int size;//记录当前ArrayList保存的数据量
    private static final int DEFAULT_CAPACITY = 10;//默认大小为10
    1.
    //list.add("1") 调用函数，添加成功时返回true
    public boolean add(E e) {
        //检查数组容量，并进行扩容操作，size此时为0
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    2.
    //检查数组容量，并在超过容量时扩容
    private void ensureCapacityInternal(int minCapacity) {
        //当前ArrayList（elementData 数组）为空，
        //当前minCapacity = 1 ，DEFAULT_CAPACITY = 10,所以minCapacity = 10
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //现在minCapacity = 10
        ensureExplicitCapacity(minCapacity);
    }
    //当超过容量时扩容数组
    private void ensureExplicitCapacity(int minCapacity) {
        //记录一次插入操作
        modCount++;
        // overflow-conscious code
        //超过数组容量，进行扩容，minCapacity = 10 > （elementData.length = 0）
        if (minCapacity - elementData.length > 0)
            //扩容操作
            grow(minCapacity);
    }
    //扩容
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //newSize = oldSize + oldSize >> 1 (等价于偶数/2,奇数-1/2)。
        //现在elementData = {}，newCapacity = 0
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //newCapacity = 0，minCapacity = 10
        if (newCapacity - minCapacity < 0)
            //newCapacity = 10
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //新建一个通类型数组，copy旧值并修改elementData引用
        //现在newCapacity = 10
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    3.
    Arrays.class
    //即Arrays.copyOf函数，现在elementData = {} 空数组，newLength = 10
    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) {
        //因为新建时时ArrayList<String>
        //(Object)newType = 'class [Ljava.lang.String;' String数组类
        //(Object)Object[].class = 'class [Ljava.lang.Object;' Object数组类
        //所以(Object)newType == (Object)Object[].class = false
        //执行(String[]) Array.newInstance('class java.lang.String'->String类, newLength)
        T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        //从original的0下标处开始复制Math.min(original.length, newLength)
        //个值拷贝给copy，并从copy的0下标处开始赋值
        System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
        return copy;
    }
    //即Array.newInstance
    //按照提供的类型和大小生成一个该类型的数组
    //返回Object类型，因为数组类是Object类的子类，所以之后强转成对应的数组类即可
    public static Object newInstance(Class<?> componentType, int length)
            throws NegativeArraySizeException {
            return newArray(componentType, length);
    }

让我们接着之前新建的ArrayList讲，运行`list.add("1")`，可以看上面给出的相关源代码中的注释，可以看到add如果不涉及扩容的话基本上只做了modCount++和把值存入elementData数组中，非常简洁明了，当存入的信息数大于当前数组容量时会重新计算一个扩容大小，即`newSize = oldSize + (oldSize >> 1)`，然后根据新的大小和类型创建一个新的数组，然后将旧信息copy到新的数组中，然后修改elementData引用。完成扩容操作后当前的值就能放的进数组了，然后将值存入即可。  
![这里写图片描述][70 1]  
这里会遇到一些有意思的东西，顺便回顾下

//泛型，这里有3个T
    //第一个T：申明T为一个泛型
    //第二个T：返回一个T类型数组
    //第三个T：一个形参为T类型数组
    public static <T> T[] copyOf(T[] original ...)
    //当然还可以写成这样,∠( ᐛ 」∠)_
    public static <ᐛ> ᐛ ᐛ(ᐛ ᐛ){
        return ᐛ;
    }

![这里写图片描述][70 2]

然后还有一个add函数允许我们在指定位置添加数据  
相关源代码

public void add(int index, E element) {
        //检测指定位置是否合法
        rangeCheckForAdd(index);
    
        //和上面讲的一样，判断是否扩容和增加modCount值
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //上面在copyOf函数中出现过，就是把指定位置处空出来，
        //指定位置后的值储存下标值都向后移动一位，可以看下图，比较直观一点
        System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
        elementData[index] = element;
        size++;
    }
    
    Arrays.class
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

![这里写图片描述][70 3]

--------------------

## get()函数 ##

相关源代码

//获取index下标处的值
    public E get(int index) {
        //index是否超过数组大小
        rangeCheck(index);
        return elementData(index);
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    //通知编译器对下面这段代码的警告保持沉默，即忽略该段代码的警告
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

总体很简单，也不多说什么了。

--------------------

## indexOf()函数 ##

相关源代码

//返回o在ArrayList中第一次出现时的下标值，不存在则返回-1
    public int indexOf(Object o) {
        //为null时
        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;
    }
    
    //最后出现的位置，和IndexOf原理一样
    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;
    }

--------------------

## isEmpty()函数 ##

相关源代码，因为ArrayList类中有一个size变量用来记录当前ArrayList包含的记录数量，所以直接去检查size是否为0即可

public boolean isEmpty() {
        return size == 0;
    }

--------------------

## remove()函数 ##

相关源代码

//根据下标值删除
    public E remove(int index) {
        //判定下标值是否大于数组容量
        rangeCheck(index);
        //添加修改记录
        modCount++;
        //获取该下标处的值
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        //如果index不是数组的最后一个下标值
        if (numMoved > 0)
            //进行拷贝操作，将从index+1下标开始到最后一个的值都往前移动一位
            System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
        //将数组大小相应的减小一位，并将减小后的数组的最后一位置为空，、
        //以覆盖掉原来在这里的旧值
        elementData[--size] = null; // clear to let GC do its work
        //删除成功，返回该处的值
        return oldValue;
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

//根据值删除
    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;
    }
    //和上面按下标删值的过程一样
    private void fastRemove(int index) {
        //修改次数+1
        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
    }

--------------------

## set()函数 ##

相关源代码

public E set(int index, E element) {
        //前面出现过很多次了，判断index是否超过数组容量
        rangeCheck(index);
        //elementData()也出现过很多次了，返回index下标处的值
        E oldValue = elementData(index);
        //设置新值
        elementData[index] = element;
        return oldValue;
    }

--------------------

## subList(start,end)函数 ##

相关源代码

//返回从fromIndex到toIndex之间的数组
    public List<E> subList(int fromIndex, int toIndex) {
        //判断fromIndex，toIndex是否数组越界
        subListRangeCheck(fromIndex, toIndex, size);
        //返回fromIndex到toIndex之间的值
        return new SubList(this, 0, fromIndex, toIndex);
    }
    //判断fromIndex，toIndex是否数组越界
    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                                   ") > toIndex(" + toIndex + ")");
    }
    //因为整个SubList类太长，放上来比较占地方所以就截取了一段，基本和ArrayList相同
    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;
        }
        ......
    }

--------------------

## Iterator迭代器 ##

//常见用法，遍历
    List<String> list = new ArrayList<String>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    Iterator iterator = list.iterator();
    while(iterator.hasNext()){
        String s = (String)iterator.next();
    }

相关源代码

//创建迭代器
    public Iterator<E> iterator() {
        return new Itr();
    }
    //截取了用到的一段
    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;
            //返回i处的值
            return (E) elementData[lastRet = i];
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

以上，基本包含了常用的ArrayList相关函数。

[70]: /images/20220527/abc7d779b182443bba87ad4579164e95.png
[70 1]: /images/20220527/9ad1bad73bcf4594b14d879488588b82.png
[70 2]: /images/20220527/4bd2de0eae9a4b65b0ae38faf2aa7d3c.png
[70 3]: /images/20220527/18397ae3376d40d59671b3fefe97b40b.png