ArrayList 源码理解（一）

List

是一个接口，它继承于Collection,是一个有序集合，我们可以精确控制每个元素的插入位置，和集合不同，列表支持重复的元素。

JDK版本11.04

ArrayList

ArrayList 是List的一个实现类，底层是基于动态数组的形式实现的ArrayList
[图片上传失败...(image-83d310-1569232991949)]

ArrayList的源码

常量
/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

构造函数
 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) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

常量介绍:
DEFAULT_CAPACITY 是一个被final修饰的int型的常量，代表ArrayList默认初始容量。
EMPTY_ELEMENTDATA 是一个空的列表，将会和上面的DEFAULT_CAPACITY联系起来，创造一个容量的10的列表
DEFAULTCAPACITY_EMPTY_ELEMENTDATA也是一个空列表，但它和上面的不同，第一次添加元素时知道该 elementData 
从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容。

从上面的代码可以看出，ArrayList有三个构造函数，第一个构造函数是指定容量的构造函数。有如下几点，第一：如果容量传入一个负数，将会抛出一个IllegalArgumentException异常，第二：如果容量>0,就创造一个容量大小的列表，如果容量为0，便指定这个列表是一个EMPTY_ELEMENTDATA空列表。

第二个无参构造函数，按照注释解释，构造一个容量大小为 10 的空的 list 集合，但构造函数了只是给 elementData 赋值了一个空的数组，其实是在第一次添加元素时容量扩大至 10 的。

第三个构造函数，将 Collection 转化为数组并赋值给 elementData，把 elementData 中元素的个数赋值给 size。如果 size 不为零，则判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换。如果 size 为零，则把 EMPTY_ELEMENTDATA 赋值给 elementData，相当于new ArrayList(0)。

重要函数

   /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }

首先我们观察 add 函数

看源码时你会发现，有一个modCount++的操作，这是为什么呢？通过查看，modCount是AbstractList中定义的一个保护变量，源码注释中给出了比较详细的解释，作用大概是用于记录list结构被修改的次数。

image

平常很少用到add(int index, E element)这个函数,这个函数有一个陷阱。在本文最下方讲解。

当我们执行 list.add（Element）时，会调用了add(E e, Object[] elementData, int s)这个函数，并进行了一次判断，如果当前元素的个数已经和list的长度相同，也就是俗话说装满了，便会执行grow（）函数,用来改变list空间的大小。elementData代表着list，grow（）函数调用了newCapacity(minCapacity) minCapacity的大小为size+1。

在newCapacity（）函数内部，使用了移位操作符将新容量扩容为老容量的1.5倍，然后判断新容量和所需容量，如果新容量小于所需容量，就把新容量大小改成所需容量


    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }


    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

在newCapacity函数的的下方，将新容量将MAX_ARRAY_SIZE进行了比较，其大小为Integer.MAX_VALUE-8，在注释中也给出了解释，虚拟机在数组中存在一些保留字。MAX_VALUE的值为0x7fffffff，这是int类型（有符号）的最大值，有21亿多个，准确数值为2147483648

image

陷阱

借鉴地址

结合我自己的理解，当我们执行
ArrayList<Integer> integers = new ArrayList<>(3);时并不是创造了一个长度为3的数组队列，结合构造函数的源码可知，在底层时创造了一个长度为3的空数组集合，当前list集合仍然是一个带有初始容量3的empty list。

例子

 ArrayList<Integer> integers = new ArrayList<>(3);
        integers.add(1);
        integers.add(2);
        System.out.println(integers);
//        integers.add(1,4);
        integers.set(2,4);
//        integers.add(2,3);
//        integers.set(2,3);
        System.out.println(integers);

在上面的代码中，我创造了一个大小为3的集合，并添加了第一个和第二个元素，在尝试使用
integers.set(2,4);来添加第三个元素时，运行出错。原因如下

image

在if判断中判断index >= length（length就是传过来的size值）index(2)=size(2)进而导致出错，只有这种index大于等于size的情况下set才会出现错误

image

add情况是在index大于size的情况下报错

闲扯一句

JAVA中初始化ArrayList的三种方式

一、最常用的初始化方式

     List<String> list1 = new ArrayList<String>();
     list1.add("apple");
     list1.add("banana");
     list1.add("orange");

二、使用一个List来初始化。

  List<String> list2 = new ArrayList<String>(Arrays.asList("apple", "banana", "orange"));

三、使用匿名内部类来初始化。

 List<String> list4 = new ArrayList<String>() {
         {
             add("apple");
             add("banana");
             add("orange");
         }
     };

未完待续