JDK1.7与1.8中ArrayList源码分析

JDK1.7与1.8中ArrayList源码分析 JDK1.7与1.8中ArrayList源码分析

我们知道在Java中集合分为两大部分，分别是Collection和Map；

Collection接口有两个子接口，分别的List和Set。今天我来大家看一下List的实现类ArrayList的源码，如有解释不恰当的地方欢迎大神帮忙指出，先在这里拜谢！！！

JDK1.7的ArrayList源码分析

首先我们创建一个ArrayList集合：

    public static void main(String[] args) {
        List list = new ArrayList();
    }

接下来我们就开始我们的源码之旅~~

我们刚进入ArrayList的实现类中发现，ArrayList是继承自AbstractList这个实现类，点开AbstractList后我们发现他们同时实现了List这个接口，不知道你们会不会有这个疑问。我在看这段源码的时候想着为什么会这样写呢？

在查阅了一些资料之后，原来是集合的创始人当时出现的一个失误，当然不会影响整个JDK的功能和性能，所以在后续版本中就没有删除。

看来大佬也是会出现失误的，是不是对于开始源码之旅不是那么紧张了呢？废话说这一点就够了，我们开始上硬菜。

首先我们看一下ArrayList中定义的两个重要属性：

    
    // 底层的数组，Object类型的数组，方便存储不同类型的数据
    private transient Object[] elementData;
    
    
	// 数组中的有效数据的个数（有效数据俗称成功存入集合中的元素）
    private int size;

下面我们看一下ArrayList中的无参构造方法：

// 无参构造
public ArrayList () {    
    // 调用本身的构造器，默认传10    
    this(10);
}
// 有参构造
public ArrayList (int initialCapacity) {    
    // 给底层数组进行初始化 *** 作，初始化长度为10    
    this.elementData = new Object[initialCapacity];
}

我们从这里可以看出，我们在没有new ArrayList的时候采用无参构造的方式创建的，这边无参构造方法调用了一下ArrayList中的有参构造方法，并且传参10。紧接着在无参构造中创建了一个长度为10的数组。

这样我们就知道为什么ArrayList的默认长度为10的，但是我们又有一个疑问，ArrayList的默认长度是10，但是我们实际应用中往往存储了大于10个的元素，那它的扩容是怎么实现的呢？

既然说到了扩容，那肯定是需要添加元素的时候才会涉及到扩容了，我们接着往下看：

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(1);
    }

我们看到add方法代码很简单，调用了我们明显能看到的就是一个元素的存储方法，并且将有效数据的个数加1。并没有看到我们所想看到的扩容的方法，现在ensureCapacityInternal我们是不知道它的作用的，我们接着看一下ensureCapacityInternal这个方法到底是做了什么事情吧。

public boolean add (E e) {    
    // 判断数组是否需要扩容的方法  
    ensureCapacityInternal (size + 1);    
    // 将数据存储到数据中，并且size进行加一的 *** 作，size默认为0    
    elementData [size++] = e;    
    // 添加成功返回 true    
    return true;
}

当我们进入ensureCapacityInternal方法后发现有一段modCount ++ 的代码，这个我后面会去跟大家解释，在这不浪费时间了。

我们看到在这做了一个判断，我们在add方法中传入了一个size + 1的数字。

现在假设我们要添加第11个元素了，这边的size + 1 = 11。（有人可能会问为什么等于10呢，因为size是有效数据的个数）

所以11是大于我们数组的初始长度10的，所以接下来要进入grow方法。grow的翻译是扩大，增长的意思，所以我们判断这个就是扩容的具体方法。

private void ensureCapacityInternal (int minCapacity) {    
    modCount ++;    
    // 判断将要存储    
    if (minCapacity - elementData.length > 0) {        
        // 进行扩容 *** 作，扩容大小为原数组长度的1.5倍        
        grow (minCapacity);    
    }
}

终于找到了我们最想看到的方法了，这里定义了两个变量去分别接收旧数组长度和新数组的长度，最后调用了Arrays.copyOf()方法；

这边传入了一个旧数组和新数组的长度，在其中创建一个新数组，将旧数组的数据存入新数组，返回一个带有旧数组数据的新数组，赋值给elementData。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 新数组长度 = 旧数组长度 + 旧数组长度往右移一位（通俗理解：除以2）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 这里这个方法暂时不用看，1.7没用到
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 判断数组是否操作最大存储量，这里的最大存储量并不是int整型的最大范围2^31-1
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
         // 传入老数组和新数组长度，在内部进行新数组创建，并且将老数组复制到新数组后返回新数组，赋	值给elementData
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

扩容内存指向图解：

JDK1.8的ArrayList源码分析

看完了1.7源码后我们接下来看1.8的源码，趁热打铁哦！

因为1.7和1.8的参数都是一样的，我们直接来看构造方法吧！

先看无参构造方法：

      public ArrayList(int initialCapacity) {
        // 判断我们传入的参数是否大于0
        if (initialCapacity > 0) {
            // 以我们传入的参数为长度创建一个数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // elementData等于一个变量
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }  

我们看到这边是判断了一下我们传入的参数，大于0以我们传入的参数创建数组，小于零直接抛出了一个异常，但是等于0进行了赋值，我们看下EMPTY_ELEMENTDATA是何方神圣吧。

private static final Object[] EMPTY_ELEMENTDATA = {};

看到这里我们就放心了，原来是一个空数组，真心佩服JDK的开发人员太厉害了。

接下来看一下无参构造方法吧：

	public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

我们看到DEFAULTCAPACITY_EMPTY_ELEMENTDATA就很难理解这是什么呢？不要着急往下看：

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

原来DEFAULTCAPACITY_EMPTY_ELEMENTDATA是定义的一个空数组。

我们就有一个猜想：1.8是不是不像1.7那样，new ArrayList的时候就创建了一个长度为10的数组，而是在添加数据的时候创建的呢？我们接着往下看：

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

我们发现这里和1.7一模一样，那么可能创建数组的 *** 作在ensureCapacityInternal方法中呢，接着往下看：

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

这里我们看到一共调用了两个方法，先从里面的方法看不容易被绕晕，我们看一下calculateCapacity方法具体做了什么？

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 判断当前elementData是否为空，如果为空返回Math.max(DEFAULT_CAPACITY, minCapacity)
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 取最大数
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 不为空返回我们传入的这个数，也就是size + 1
        return minCapacity;
    }

这里到了我们想要看到的代码了，这边判断了一下当前数组是不是为空，如果为空就取最大数。但是我们发现有个变量DEFAULT_CAPACITY在里面，这是什么呢？

private static final int DEFAULT_CAPACITY = 10;

原来DEFAULT_CAPACITY的值是10，这就对应了我们ArrayList默认长度为10。

接下来看另外一个ensureExplicitCapacity方法：

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

在这里我们又看到了熟悉的grow方法，我们整个的流程完善了。但是JDK1.8的grow有一点不一样的，听我道来。

    private void grow(int minCapacity) {
        // overflow-conscious code
        // 旧数组长度为0
        int oldCapacity = elementData.length;
        // 运算结果也为0
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 将我们得到的10赋值给newCapacity，用于创建数组
        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);
    }

这里可能有人看到modCount++;这段代码我没有给出一个解释，我在这里解释一下：

    
    protected transient int modCount = 0;

我们来看一下迭代器的部分源码：

	
    public Iterator iterator() {
        return new Itr();
    }

    
    private class Itr implements Iterator {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
         // 这里将 modCount 赋值给了 expectedModCount
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = 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 {
                this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            // 若修改后 modCount会变化 会与 expectedModCount 数值不相等
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

看源码可以得出获取迭代器时会将 expectedModCount 赋值为 modCount， 若在使用迭代器迭代期间修改列表则会导致两者不相等，调用next()时会进行checkForComodification检查抛异常。说明迭代时不可以进行修改 *** 作。

modCount主要目的就是用来限制用户在迭代时修改列表，造成数据错乱。

还有MAX_ARRAY_SIZE变量不知道大家注意了没有？我大概讲一下：

  
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

为什么数组最大长度要减8？

因为自己作为数组，除了存储数据本身以外，还需要32bytes的大小来存储对象后（object header）信息。Java中每个对象都包含了对象头，HotSpot虚拟机中对象头的大小不会超过32bytes，所以最大容量减8才不会移除。