JAVA常用集合源码解析系列-ArrayList源码解析（基于JDK8）

文章系作者原创，如有转载请注明出处，如有雷同，那就雷同吧~（who care！）

一、写在前面

这是源码分析计划的第一篇，博主准备把一些常用的集合源码过一遍，比如：ArrayList、HashMap及其对应的线程安全实现，此文章作为自己相关学习的一个小结，记录学习成果的同时，也希望对有缘的朋友提供些许帮助。

当然，能力所限，难免有纰漏，希望发现的朋友能够予以指出，不胜感激，以免误导了大家！

二、稳扎稳打过源码

首先，是源码内部的成员变量定义以及构造方法：

 /**
      * Default initial capacity.
     （默认初始化长度）ps：实际是“延时初始化”（lazy init），后文详解
      */
     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.
     （区别于EMPTY_ELEMENTDATA，使用默认构造方法时，默认使用此空数组，再配合DEFAULT_CAPACITY共同实现lazy init）
      */
     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.
     （集合数据真正存放的地方，所以对于ArrayList我们可以理解为提供了一组高效操作方法的数组。注意注释后半段：当集合的首个元素被添加时，把空集合DEFAULTCAPACITY_EMPTY_ELEMENTDATA扩展为DEFAULT_CAPACITY大小的集合，这就是lazy init，使用时才分配内存空间，目的是防止空间的浪费。）ps：transient 表示此变量不参与序列化
      */
     transient Object[] elementData; // non-private to simplify nested class access

     /**
      * The size of the ArrayList (the number of elements it contains).
      *
      * @serial
     （数组大小）
      */
     private int size;

参数项

 /**
      * Constructs an empty list with the specified initial capacity.
      *
      * @param  initialCapacity  the initial capacity of the list
      * @throws IllegalArgumentException if the specified initial capacity
      *         is negative
 （没什么可说，初始化参数>0创建该长度数组，=0使用共享空数组，<0报错）
      */
     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);
         }
     }

     /**
      * Constructs an empty list with an initial capacity of ten.
 （使用默认空数组，lazy init，添加元素时数组扩展至默认容量DEFAULT_CAPACITY）
      */
     public ArrayList() {
         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
     }

     /**
      * Constructs a list containing the elements of the specified
      * collection, in the order they are returned by the collection's
      * iterator.
      *
      * @param c the collection whose elements are to be placed into this list
      * @throws NullPointerException if the specified collection is null
      */
     public ArrayList(Collection<? extends E> c) {
         elementData = c.toArray();
         if ((size = elementData.length) != 0) {
             // c.toArray might (incorrectly) not return Object[] (see 6260652)
 （准确的说这是个bug，从下面链接可以看到会在jdk9修复，bu*生原因后面详解。附上链接http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652）
             if (elementData.getClass() != Object[].class)
                 elementData = Arrays.copyOf(elementData, size, Object[].class);
         } else {
             // replace with empty array.
             this.elementData = EMPTY_ELEMENTDATA;
         }
     }

构造方法

进阶分析，集合常用操作，先从简单入手：

 /**
 思路很简单：
 1.判断index是否越界，越界则异常
 2.直接取出数组elementData相应位置index的元素并强转为E
 **/
 public E get(int index) {
         rangeCheck(index);

         return elementData(index);
     }
 private void rangeCheck(int index) {
         if (index >= size)
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }
  E elementData(int index) {
         return (E) elementData[index];
     }

按位次获取单个集合元素

 /**
 同样很简单：
 1.判断index是否越界，越界则异常
 2.取到index位置的值作为原值
 3.设置该位置值为修改后的值
 4.return原值
 **/
 public E set(int index, E element) {
         rangeCheck(index);

         E oldValue = elementData(index);
         elementData[index] = element;
         return oldValue;
     }

按位次修改单个集合元素

　　如前所述，单个元素按位次获取操作很简单，只要你了解到arrayList内部是数组存放数据，那上述操作完全可以想得到。

　　下面继续，集合的添加和删除操作，没看过源码的朋友可以思考下，添加和删除操作同上述两个操作主要的区别在哪里？为什么会复杂些？

　　因为添加元素的时候可能位置不够嘛，那怎么办？位置不够就加位置，也就是所谓的“扩容”！我们自己思考下实现思路，然后同作者的思路对比下：

　　1.上面我们提到，默认构造方法使用的lazy_init模式，添加元素时才init。那第一步判断是否需要init，需要则init。

　　2.判断是否需要扩容（通俗点说就是当前数组有没有空位置？）需要就扩容（创建个容量更大的新数组），但是扩容也不是无限的，超过上限就报错（Integer.Max_Value），并把原数据copy到新数组，否则什么都不做

　　3.在指定位置添加元素，并size++

 /**
 看下作者是如何思考的，和自己的思考做下对比：
 1.判断是否需要lazy init，如果需要则init，然后执行步骤2
 2.判断是否需要扩容，如果需要则执行步骤3，否则执行步骤5
 3.扩容，新数组长度=当前数组长度*1.5,并判断扩容后长度是否满足目标容量，不满足，则新数组长度=目标容量。接着判断新数组长度是否超过阈值MAX_ARRAY_SIZE，超过则执行步骤4
 4.目标数组长度=如果目标数组长度>MAX_ARRAY_SIZE?Integer.MAX_VALUE:MAX_ARRAY_SIZE
 5.扩容结束后，执行数据copy，从原数组copy数据到新数组
 6.在指定的位置添加元素，并使长度增加
 **/
 public boolean add(E e) {
         ensureCapacityInternal(size + 1);  // Increments modCount!!
         elementData[size++] = e;
         return true;
     }
 private void ensureCapacityInternal(int minCapacity) {
         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
         }

         ensureExplicitCapacity(minCapacity);
     }
 private void ensureExplicitCapacity(int minCapacity) {
         modCount++;

         // overflow-conscious code
         if (minCapacity - elementData.length > 0)
             grow(minCapacity);
     }
 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);
     }
 private static int hugeCapacity(int minCapacity) {
         if (minCapacity < 0) // overflow
             throw new OutOfMemoryError();
         return (minCapacity > MAX_ARRAY_SIZE) ?
             Integer.MAX_VALUE :
             MAX_ARRAY_SIZE;
     }

单个添加集合元素

　　对比后发现，总体思路是没问题的，但是作者为什么要加入下面这样的容量上限处理逻辑？朋友们可以思考下，ArrayList的容量上限到底是Integer.MAX_VALUE还是MAX_ARRAY_SIZE?

　　答案是：Integer.MAX_VALUE，依然还是它，并不是源码中作者定义的MAX_ARRAY_SIZE，那就引申出一个问题了-MAX_ARRAY_SIZE存在的意义。

　　我的理解是，这个上限的存在，减小了内存溢出的概率。首先注释中也提到了“Some VMs reserve some header words in an array”，意思就是有些虚拟机把头信息保留在数组中，毫无疑问保存信息是要占空间的，也就是我实际数组空间可能是不足Integer.MAX_VALUE的，作者应该是这样的思路（我猜的~）“我可以基本确定实际空间不会小于MAX_ARRAY_SIZE（可能是分析了主流虚拟机的实现而得出的结论），因此设置个阈值，来确保不会内存溢出，但如果这个容量还是不够，那把剩下的风险很高的8也给你好了，至于是不是会溢出，天知道，反正我已经尽力了！”

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

 /**
 比较简单，一笔带过，按位置删除
 思路：
 1.越界检测
 2.取出当前位置的元素
 3.当前位置之后的所有元素整体前移一位置
 4.最后位置置空，size--，返回删除的元素值。
 **/
 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;
     }
 /**
 思路很简单，按元素删除（注意只删除从头开始第一个匹配值），遍历->匹配->删除
 值得注意的是，单独对null做特殊处理，按地址比较
 **/
 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;
     }

 单个删除集合元素

单个删除元素

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

     private boolean batchRemove(Collection<?> c, boolean complement) {
         final Object[] elementData = this.elementData;
         int r = 0, w = 0;
         boolean modified = false;
         try {
 //遍历当前集合所有元素
             for (; r < size; r++)
                 if (c.contains(elementData[r]) == complement)
 //如果指定集合不包含该元素（即不应删除的，需要保留的），把当前元素移动到头部w位置（原头部元素因不符合条件，直接删除掉，这里覆盖也即删除），并把w标记移到下一位
                     elementData[w++] = elementData[r];
         } finally {
             // Preserve behavioral compatibility with AbstractCollection,
             // even if c.contains() throws.
 //这儿两种情况：
 //无异常r==size 不会进入这个if
 //有异常，则把因异常而未来得及比较的所有元素整体copy到w位置，并把w标记移位size - r（可以理解为还未比较的数量）
             if (r != size) {
                 System.arraycopy(elementData, r,
                                  elementData, w,
                                  size - r);
                 w += size - r;
             }
 //这儿很好理解，w位置（该位置之前都是比较或者异常而需要保留的）之后的所有都是应该删除的。
             if (w != size) {
                 // clear to let GC do its work
                 for (int i = w; i < size; i++)
                     elementData[i] = null;
                 modCount += size - w;
                 size = w;
                 modified = true;
             }
         }
         return modified;
     }

批量删除

 /**
 看起来比较简单，但仔细分析就会发现还是有些深度的，有兴趣可以看下defaultReadObject的实现，这里就暂时忽略，以后有机会详细分析下java的序列化与反序列化。
 实现思路（以序列化为例，反序列化同理）
 1.调用默认序列化
 2.写入size
 3.遍历数组，写入所有集合元素
 **/
 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 size as capacity for behavioural compatibility with clone()
         s.writeInt(size);

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

     /**
      * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
      * deserialize it).
      */
     private void readObject(java.io.ObjectInputStream s)
         throws java.io.IOException, ClassNotFoundException {
         elementData = EMPTY_ELEMENTDATA;

         // Read in size, and any hidden stuff
         s.defaultReadObject();

         // Read in capacity
         s.readInt(); // ignored

         if (size > 0) {
             // be like clone(), allocate array based upon size not capacity
             ensureCapacityInternal(size);

             Object[] a = elementData;
             // Read in all elements in the proper order.
             for (int i=0; i<size; i++) {
                 a[i] = s.readObject();
             }
         }
     }

序列化与反序列化

/**
迭代器
1.了解快速失败机制即可
2.关注下forEachRemaining的实现，可扩展研究下lambda表达式
**/
public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.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;
            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();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

迭代器

三、 ArrayList使用建议

　　1.当你需要确定长度的ArrayList时，推荐使用该长度初始化，理由是防止频繁扩容，扩容相对而言是对性能影响相当大的操作（请注意是相对而言，相对于常规的增删改查等操作）。

　　2.谨慎使用clone、toArray，对于源对象和方法返回对象，数据修改操作会相互影响。他们最终都执行了System.arrayCopy()，都是“浅拷贝”：只copy了引用，所有对于其中一个引用的修改操作会传递到其他引用上。java的copy应该都是“浅拷贝”，测试如下：

/**
测试代码，随手为之，仅供参考。
**/
class TestObj {

            TestObj(Integer i, String s) {
                this.i = i;
                this.s = s;
            }

            Integer i;

            String s;

            public String toString() {

                return "i=" + i + "," + "s=" + s;
            }
        }
        ArrayList<TestObj> arrayList = new ArrayList<>();

        int size = 10;

        for (Integer i = 0; i < size; i++) {

            arrayList.add(new TestObj(i, "test" + i));

        }

        ArrayList<TestObj> cloneArrayList = (ArrayList<TestObj>) arrayList.clone();

        cloneArrayList.add(new TestObj(101, "test" + 101));

        System.out.println("arrayList size：" + arrayList.size());
        System.out.println("cloneArrayList size：" + cloneArrayList.size());

        System.out.println("arrayList index 0：" + arrayList.get(0).toString());
        System.out.println("cloneArrayList index 0：" + cloneArrayList.get(0).toString());

        //修改cloneArrayList index 0
        TestObj testInteger = cloneArrayList.get(0);
        testInteger.i = 1000111;

        System.out.println("修改cloneArrayList index=0对象后，ps：我没修改arrayList哦");

        System.out.println("arrayList index 0：" + arrayList.get(0).toString());
        System.out.println("cloneArrayList index 0：" + cloneArrayList.get(0).toString());
测试结果：
arrayList size：10
cloneArrayList size：11
arrayList index 0：i=0,s=test0
cloneArrayList index 0：i=0,s=test0
修改cloneArrayList index=0对象后，ps：我没修改arrayList哦
arrayList index 0：i=1000111,s=test0
cloneArrayList index 0：i=1000111,s=test0

测试clone

　　3.谨慎使用subList，深入分析后会发现，本质原因同上面类似，都是相同的引用，所以数据修改操作会相互影响，如下例子：

 public static void testSubList() {

         Integer index = 10;

         List<Integer> myList = new ArrayList<>(index);

         for (int i = 0; i < index; i++) {
             myList.add(i);
         }

         List<Integer> mySubList = myList.subList(3, 5);

         System.out.println("打印myList：");
         myList.forEach(System.out::println);

         System.out.println("对mySubList增加个元素，注意我没对myList做任何操作哦");
         mySubList.add(100);

         System.out.println("打印mySubList：");
         mySubList.forEach(System.out::println);

         System.out.println("再次打印myList：");
         myList.forEach(System.out::println);

     }
 运行结果：
 打印myList：
 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
 对mySubList增加个元素，注意我没对myList做任何操作哦
 打印mySubList：
 3
 4
 100
 再次打印myList：
 0
 1
 2
 3
 4
 100
 5
 6
 7
 8
 9

测试subList

　　4.细心的朋友可能发现了，arrayList没有提供对数组的构造方法，但是我们知道array->arrayList是比较常见的需求，那如何做呢？办法不止一种，选择你喜欢的即可，如下：

 int[] ints = {1, 2, 3, 4};
         List<Integer> myIntListByStream = Arrays.stream(ints).boxed().collect(Collectors.toList());

         Integer[] integers = {1, 2, 3, 4};
         List<Integer> myListByAsList = Arrays.asList(integers);   //ps：此方式得到的数组不可修改,这里的修改指的是所有更改List数据的行为
         List<Integer> myListByNewArrayListAsList = new ArrayList<>(Arrays.asList(integers));
         List<Integer> myListByStream = Arrays.stream(integers).collect(Collectors.toList());

arrayToList

四、源码相关扩展（我能想到的可以深入思考的一些地方）

　　1.快速失败（fail fast）机制：

　　我们知道，ArrayList不是线程安全的集合类。意味着在并发操作时，很容易发生错误。按照常规思路，发现结果出错，抛出异常即可。但在实际应用中，我们并不满足于此，有没有一种检测机制，在并发操作前进行校验，提前告诉我们可能发生的错误呢？如你所料，就是我们提到的快速失败机制。它是如何实现的呢？其实很简单，我们定义一个计数器modCount，这个计数器记录所有集合结构变动的次数，比如增加两个元素就modCount+=2，再比如删除3个元素就modCount+=3，这个计数器只能增加不能减少，然后我们在执行一些需要快速失败的操作时（比如：迭代器、序列化等等），执行之前记录下当前modCount为expectedModCount,在适当的时候判断expectedModCount、modCount是否相等就可以判断这期间是否有过集合结构的变动。

　　2.lambda表达式：读源码我们发现，ArrayList中加入了许多支持lambda的方法，作为JDK8的亮点之一，应该能够熟练使用，然后再详细分析lambda的实现机制我觉得也很有意思。

　　3.jdk中常用JNI方法的实现：上文我们在对clone方法做分析的时候，最终只分析到Object的native方法，我觉得有机会去看下常用的一些native方法的实现也是很有意思的，待研究。

五、总结一下

老实说，分析完ArrayList发现，所花的时间大出我预计，我一度认为我已经理解的很透彻了，但是在写这篇文章的途中我又把差不多一半的源码回顾了一遍（这真是个悲伤的故事），不过不管怎么说，这是个好的开始，后面一篇解析hashMap。