ArrayList source code learning

This paper is based on jdk1 Version 8, do some source code learning for the giant ArrayList in the collection, and will refer to a large number of materials. Links to reference articles will be given at the end of the article. This article is used to consolidate learning knowledge.

Inheritance system of ArrayList

ArrayList inherits the abstract class abstractlist and implements the list interface, providing functions such as adding, deleting, modifying and traversing. As for other interfaces, we will make a summary later.

ArrayList core source code

The underlying implementation is based on array. We can view the source code to understand some of its properties:

private static final long serialVersionUID = 8683452581122892189L;

//默认的初始容量为10
private static final int DEFAULT_CAPACITY = 10;

//如果指定数组容量为0，返回该数组，相当于new ArrayList<>(0);
private static final Object[] EMPTY_ELEMENTDATA = {};

//没有指定容量时，返回该数组，与上面不同的是：new ArrayList<>();
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//该数组保存着ArrayList存储的元素，任何没有指定容量的ArrayList在添加第一个元素后，将会扩容至初始容量10
transient Object[] elementData; // non-private to simplify nested class access

//代表了当前存储元素的数量
private int size;

Re emphasize that empty_ Elementdata and defaultprotocol_ EMPTY_ Elementdata is distinguished to specify the size that should be expanded when adding the first element, and the specific expansion mechanism will be analyzed later.

Let's take a look at its constructor:

    
    //该构造器用以创建一个可以指定容量的列表
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //创建一个指定容量大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //指定容量为0，对应EMPTY_ELEMENTDATA数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    //默认无参构造器，赋值空数组，但是在第一次添加之后，容量变为默认容量10
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    //传入一个集合，根据该集合迭代器返回顺序，构造一个指定集合里元素的列表
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        //传入集合不为空长
        if ((size = elementData.length) != 0) {
            //传入集合转化为的数组可能不是Object[]需要判断
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData,size,Object[].class);
        } else {
            //传入集合为元素数量为0，用空数组代替即可
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    //指定集合为null的话（并不是说集合为空长），调用ArrayList的toArray方法，可能会抛出空指针异常

ArrayList capacity expansion mechanism

After understanding the basic properties and constructors of ArrayList, we will learn the methods contained therein:

    //没有指定索引，默认在尾部添加元素
    public boolean add(E e) {
 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //扩容之后，下一位赋值为e，size加1
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));
    }

    //判断是否为默认构造器生成的数组，并将minCapacity置为0；如果不是，minCapacity还是传入的size+1
    private static int calculateCapacity(Object[] elementData,int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //使用默认构造器，那么才会返回所需要的最小容量为默认容量10
            return Math.max(DEFAULT_CAPACITY,minCapacity);
        }
        //minCapacity = size+1 
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
        //定义在AbstractList中，用于存储结构修改次数
        modCount++;

        //如果最小容量比数组总长度还大，就扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    //扩容操作
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //将旧容量右移一位在加上本身，像当于新容量为就容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //1.新数组的容量还是不能满足需要的最小容量，如初始指定容量为0时的情况
        //2.新数组越过了整数边界，newCapacity将会小于0
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新数组的容量比数组最大的容量Integer.MAX_VALUE - 8还大，
        //调用hugeCapacity方法
        if (newCapacity - MAX_ARRAY_SIZE > 0)

            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

    //比较最小容量和MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //三目表达式：如果真的需要扩这么大容量的情况下：
        //1.最小容量大于MAX_ARRAY_SIZE，新容量等于Integer.MAX_VALUE，否则新容量为Integer.MAX_VALUE-8
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

When the article is written here, I take a long breath, and the nested calls are finally over. I don't know whether your heart is the same as me. Let's strike while the iron is hot and take a look at another overloaded add method.

    //在索引为index处插入E
    public void add(int index,E element) {
        //索引越界判断
        rangeCheckForAdd(index);

        //同上，确保有足够容量添加元素
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //实际上Arrays.copyOf的底层调用的就是这个方法，意思是在原数组上从索引的位置到最后整体向后复制一位，相当于移动的长度为 (size-1) - index +1 = size -index
        Sy@R_301_2354@.arraycopy(elementData,index,elementData,index + 1,size - index);
        //在将index处填上元素E
        elementData[index] = element;
        //元素数量+1
        size++;
    }

With the cushion in front, it's relatively easy. We might as well take a look at the method to judge the array out of bounds. Mom, this is more clear, but it should be noted that index = = size is equivalent to inserting from the tail in the addition operation, which does not constitute out of bounds:

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

After reading the two methods of "increase", it's time for the "deletion" of the same quadruplets. Before we talk about "delete", we should make it clear that the underlying ArrayList is based on array implementation and can access and obtain data by relying on continuous index values, which becomes a matter of course:

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

The following is the "delete" operation. It should be noted that the remove operation can not reduce the capacity, but reduce the number of elements. From beginning to end, the size is changing. I don't believe you:

    //移除指定位置的元素，并将其返回 
    public E remove(int index) {
        //范围判断
        rangeCheck(index);
        //操作列表，计数加1
        modCount++;
        //取出旧值
        E oldValue = elementData(index);

        //相当于把index+1位置向后的所有元素集体向前复制一位，复制的长度就是
        //(size-1)-(index+1)+1 = numMoved
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //执行集体拷贝动作
            Sy@R_301_2354@.arraycopy(elementData,index+1,numMoved);
        //并让最后一个空出来的位置指向null，点名让GC清理
        elementData[--size] = null; 
        //返回旧值
        return oldValue;
    }

You can take a look at the code of rangecheck. It is slightly different from the judgment in the add operation. The judgment of index < 0 is omitted. At first, I was very confused. Later, I found that there is an index value value of the array, and an exception will still occur:

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

    //移除指定元素，找到并删除返回true，没找到返回false
    public boolean remove(Object o) {
        //判断指定的元素是否本身就是null值
        if (o == null) {
            for (int index = 0; index < size; index++)
                //找到同为null值的那个“它”
                if (elementData[index] == null) {
                    //快速删除，删除操作和之前类似，只是省略了范围判断，就不赘述了
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                //不是空值的话，就找值相等的，注意不要elementData[index].equals(o),时刻避免空指针
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

There is also a scope remoderange, which will not be repeated. To sum up, the remove operation in ArrayList is based on the copy of the array, and the length of the remove is set to null, and the number of elements is reduced accordingly (only the number of elements is reduced, and the array capacity will not change). By the way, the clear method will clean up relatively, but still only the size changes:

    public void clear() {
        modCount++;

        //将所有元素置空，等待GC宠幸
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

Of course, if you want the array capacity to change. You can try the following method:

    //将ArrayList容量调整为当前size的大小
    public void trimToSize() {
        modCount++;
        //基于三目运算
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData,size);
        }
    }

Next, let's talk about the quite simple set and get gay operations:

    //用指定值替换只当索引位置上的值
    public E set(int index,E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    //获取指定索引位置上的值
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

Then there are sister flower operations: indexof and lastIndexOf. (PS: the process of finding elements can refer to the process of removing specified elements). Take indexof as an example, lastIndexOf can traverse forward from the tail.

    //判断o在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;
    }

Through the return value of indexof method, we can also judge whether an element exists:

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

In addition to adding a single element, ArrayList also provides methods to add the entire collection to its tail:

    //把传入集合中的所有元素全部加到本身集合的后面，如果发生改变就返回true
    public boolean addAll(Collection<? extends E> c) {
        //将传入集合转化为列表，如果传入集合为null，会发生空指针异常
        Object[] a = c.toArray();
        int numNew = a.length;
        //确定新长度是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        Sy@R_301_2354@.arraycopy(a,numNew);
        size += numNew;
        //传入为空集合就为false，因为不会发生改变
        return numNew != 0;
    }

Its overload method is to insert all elements in another collection at the specified position and arrange them in iterative order:

    //在指定位置插入另一集合中的所有元素
    public boolean addAll(int index,Collection<? extends E> c) {
        rangeCheckForAdd(index);
        //还是会引发空指针
        Object[] a = c.toArray();
        //传入新集合c的元素个数
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //要移动的个数：(size-1)-index+1 = numMoved
        int numMoved = size - index;
        if (numMoved > 0)
            Sy@R_301_2354@.arraycopy(elementData,index + numNew,numMoved);
        //size<index的情况，前面就会抛异常，所以这里只能index==size，相当于从尾部添加
        Sy@R_301_2354@.arraycopy(a,numNew);
        size += numNew;
        return numNew != 0;
    }

Final summary

By the way, if there is no accident, it will bring the source code learning of LinkedList. If I think I have narrative errors, or I don't explain the white points, I hope the comment area can criticize and correct, learn and communicate together, come on! Reference link: talking about the dynamic expansion of ArrayList. The list set is so simple [source code analysis] https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList.md