ArrayList核心源码(扩容机制)解读

前言

目前发现JDK集合是真的重要，不仅要知道怎么使用，各个集合间有什么区别，如何进行选择，还要知道底层实现的原理是啥。心情好的话，还要自己手撕代码实现集合。目前看来，集合也是面试中的重灾区，所以我就乘机好好研究了一下下。

ArraysList简述

   Array List 是容量可以改变的非线程安全集合。使用非常之广泛，其内部实现使用动态数组进行存储，集合扩容时会创建更大的数组空间，把原有数据copy到新数组中。 ArrayList 支持对元素的快速随机访问，但是插入与删除时速度通常很慢，因为这个过程很有可能需要移动其他元素。

继承体系

源码解析

     /**
     * Default initial capacity.  默认的容量大小为10 
     */
    private static final int DEFAULT_CAPACITY = 10;

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

    /**
     * 一个默认空数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存放真正存放集合数据的数组
     */
    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;

2.构造方法

public ArrayList(int initialCapacity) { //带参的构造方法
        if (initialCapacity > 0) { //判断传入的initialCapacity > 0
            this.elementData = new Object[initialCapacity]; //new 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.
     */
    public ArrayList() {  
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //等于默认的空数组
    }

3.add(E e) 方法

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!! 这里就是核心,    
        //传入size+1是先预先判断，假如将当前的元素加入到集合中，集合中容量是否够，是否需要扩容
        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++;  //这里modCount+1,是保证fail-fast机制的

        // overflow-conscious code 有溢出意识的代码
        if (minCapacity - elementData.length > 0) //意味着最小需要的容量要大于数组的长度  
        //假设，我minCapacity就只要2，而elementData.length是3，那还有扩容的必要吗？？？
            grow(minCapacity); //执行核心的扩容方法
    }

    扩容的核心方法
    private void grow(int minCapacity) { //这个就是之前执行得到需要的最小容量
        // overflow-conscious code  有溢出意识的代码
        int oldCapacity = elementData.length;//拿到数组的旧容量
        int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量在旧容量下*1.5倍
        if (newCapacity - minCapacity < 0)//如果新容量还是比我需要的容量（minCapacity）小
            newCapacity = minCapacity;  //新容量就变为我自己的想要的容量(minCapacity)
        if (newCapacity - MAX_ARRAY_SIZE > 0) //如果新容量大于最大容量
            newCapacity = hugeCapacity(minCapacity); //newCapacity=根据minCapacity得到一个能容忍的最大容量
        // minCapacity is usually close to size, so this is a win:
        //minCapacity通常接近大小，因此这是一个胜利
        elementData = Arrays.copyOf(elementData, newCapacity); //将数组进行复制，其实还是对System.ArrayCopy封装而已
    }

    private static int hugeCapacity(int minCapacity) { //根据minCapacity得到最大的capacity
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add()方法总结：

 1.调用add(E e),首先会执行ensureCapacityInternal(size+1),传入的值是size+1,也就是说假如我将这个值加  
   入到集合中，集合中的容量是否够，是否需要扩容。  
 2.ensureCapacityInternal(size+1)，会去判断数组是否已经初始化，没有的话，就拿到（size+1) 与
   DEFAULT_CAPACITY中的最大值。将最大的值传入到ensureExplicitCapacit()中
 3.ensureExplicitCapacit()中判断是否有必要去扩容,当size+1 > elementData.length,执行grow()
 4.在grow方法中，newCapacity=oldCapacity + (oldCapacity >> 1),也就是原先数组基础上的1.5倍，然后判  
 断newCapacity的长度是不是超过限定的最大限度，不然的话，执行hugeCapacity得到最大的capacity,最后     
 ArrayCopy 一下就完事

4.remove(int index) 方法

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); //数组copy
        elementData[--size] = null; // clear to let GC do its work  GC收集

        return oldValue;
    }

总结：

再来看一下 HashMap ，它默认的capacity大小为10。如果它需要放置 1000 个元素,在没有设置初始值的情  
况下，会 随着元素的不断增加 , 需要被动扩容7次才可以完成存储。所以，一般情况下，可以能在自己预估  
容量大小的情况下，在new ArrayList的时候传入initCapacity,来减少扩容带来的数组copy消耗时间。

谢谢大家的阅读，以上纯属个人理解，我是一个初生牛犊不怕虎的99后小伙子，如果遇到什么问题，请在评论区留言哦！！！