ArrayList的底层实现原理

曾经终败给现在 2022-03-17 01:50 278阅读 0赞

# **ArrayList源码分析** #

1、java.util.ArrayList<E> : List 接口的大小可变数组的实现类

*  ArrayList 内部基于 数组 存储 各个元素。
 *  所谓大小可变数组，是指当 数组容量不足以存放新的元素时，创建新数组，并将原数组中的内容复制过来。

2、ArrayList底层实现原理

*  构造方法源码分析
    
    ![复制代码][copycode.gif]
    
        //对象数组：ArrayList的底层数据结构，transient表示该字段不进行序列化操作
        transient Object[] elementData;
        //实例化一个空数组
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        //实例化一个空数组
        private static final Object[] EMPTY_ELEMENTDATA = {};
        
        /**
         *指定初始容量的有参构造
         */
        public ArrayList(int initialCapacity) {
                 //如果初始容量大于0就，对象数组就指向到一个新的数组，大小为所指定的大小
                if (initialCapacity > 0) {
                    this.elementData = new Object[initialCapacity];
                } else if (initialCapacity == 0) {
                    //如果大于0就指向一个空数组
                    this.elementData = EMPTY_ELEMENTDATA;
                } else {
                    throw new IllegalArgumentException("Illegal Capacity: "+
                                                       initialCapacity);
                }
        }
        /**
        * 无参构造
        */
        public ArrayList() {
                 //对象数组就指向到一个空数组
                this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
    ![复制代码][copycode.gif]
    
    ArrayList基于数组实现，构造方法有有参构造和无参构造如果指定了初始容量且大于0就将对象数组指定到一个新的数组，大小为所指定的大小。如果调用无参构造就将对象数组指定到一个空的数组。
 *  添加方法源码分析
    
    ![复制代码][copycode.gif]
    
        //elementData中已存放的元素的个数，注意：不是elementData的容量
        private int size;
        //elementData的默认容量为10
        private static final int DEFAULT_CAPACITY = 10;
        //对象数组：ArrayList的底层数据结构，transient表示该字段不进行序列化操作
        transient Object[] elementData;
        //实例化一个空数组
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        //实例化一个空数组
        private static final Object[] EMPTY_ELEMENTDATA = {};
        
        protected transient int modCount = 0;
        
        @Native public static final int   MAX_VALUE = 0x7fffffff;
        
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        
        /**
         * 向elementData末尾中添加元素
         */
        public boolean add(E e) {
               //确保对象数组elementData有足够的容量，可以将新加入的元素e加进去
                ensureCapacityInternal(size + 1);  
                //加入新元素e，size加1
                elementData[size++] = e;
                return true;
        }
        
        // minCapacity = seize+1，即表示执行完添加操作后，数组中的元素个数 
        private void ensureCapacityInternal(int minCapacity) {
                //判断是否是空数组
                if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                    //用最小容量和10进行比较，取最大值赋值给最小容量
                    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
                }
        
                ensureExplicitCapacity(minCapacity);
         }
        
        /**
         *确保数组的容量足够存放新加入的元素，若不够，要扩容
         */
        private void ensureExplicitCapacity(int minCapacity) {
                modCount++;
                //如果数组个数minCapacity （size+1）大于数组长度就需要进行扩容
                if (minCapacity - elementData.length > 0)
                    grow(minCapacity);
        }
        
        private void grow(int minCapacity) {
                int oldCapacity = elementData.length;
                // 将旧的数组容量增加为原来的1.5倍作为新的容量
                int newCapacity = oldCapacity + (oldCapacity >> 1);             
               //如果新的容量小于数组个数，将数组个数赋值给新容量
                if (newCapacity - minCapacity < 0)
                    newCapacity = minCapacity;
               // 如果新的容量大于最大容量，就根据数组个数来决定新的容量大小
                if (newCapacity - MAX_ARRAY_SIZE > 0)
                    newCapacity = hugeCapacity(minCapacity);
                // 根据新的容量，将数组拷贝到新的数组并赋值给数组
                elementData = Arrays.copyOf(elementData, newCapacity);
        }
        
        private static int hugeCapacity(int minCapacity) {
               // 如果数组个数小于0抛出OutOfMemoryError异常
                if (minCapacity < 0) // overflow
                    throw new OutOfMemoryError();       
               // 如果最数组个数大于最大容量 就返回最大值，否则返回最大容量
                return (minCapacity > MAX_ARRAY_SIZE) ?
                    Integer.MAX_VALUE :
                    MAX_ARRAY_SIZE;
        }
        /**
         * 向elementData指定位置添加元素
         */
        public void add(int index, E element) {
               //指定位置检查
                rangeCheckForAdd(index);
                // 扩容检查
                ensureCapacityInternal(size + 1);  // Increments modCount!!
                //通过拷贝使数组内位置为 index 到 （size-1）的元素往后移动一位
                System.arraycopy(elementData, index, elementData, index + 1,
                                 size - index);         
                // 找到位置添加元素
                elementData[index] = element;
                // 元素个数加一
                size++;
        }
        // 判断指定位置是否超出数组个数
        private void rangeCheckForAdd(int index) {
                if (index > size || index < 0)
                    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        /**
         * @param      src      原数组.
         * @param      srcPos   原数组的起始位置.
         * @param      dest     目标数组.
         * @param      destPos  目标数组的起始位置.
         * @param      length   拷贝长度.
         */
        public static native void arraycopy(Object src,  int  srcPos,
                                                Object dest, int destPos,
                                                int length);
    
    ![复制代码][copycode.gif]
    
    ArrayList在无参的add方法中，每次插入新的元素时，先判断是否需要扩容，判断数组是否为空，为空则建默认的容量10赋值给minCapacity，判断是否要扩容，第一次添加，数组的size是10，之后添加元素时，在ensureExplicitCapacity方法中判断数组元素个数即size+1（形参minCapacity）是否超过数组长度，超过则需要进行扩容操作，扩容是将旧的容量扩大到1.5倍，然后将数组拷贝到新的数组完成扩容操作。最后将元素添加，并size+1。ArrayList在指定位置添加元素时，是先检查指定位置是否在数组范围内，即数组中元素个数是1，则index得小于或者低于1。然后通过拷贝使数组内位置为 index 到 （size-1）的元素往后移动一位，腾出位置之后放入元素，数组个数加一。
 *  删除方法源码分析
    
    ![复制代码][copycode.gif]
    
        public E remove(int index) {
               //指定位置检查
                rangeCheck(index);
                modCount++;       
               //保留要删除的值
                E oldValue = elementData(index);
               //要移动元素个数
                int numMoved = size - index - 1;
                if (numMoved > 0)
                //通过拷贝使数组内位置为 index+1到 （size-1）的元素往前移动一位
                    System.arraycopy(elementData, index+1, elementData, index,
                                     numMoved);
                //清除末尾元素让GC回收
                elementData[--size] = null; // clear to let GC do its work
                //返回删除的值
                return oldValue;
            }
    
    ![复制代码][copycode.gif]
    
    删除指定位置的元素，先对index进行检查，在将要删除的值保留，计算出需要移动元素个数，再通过拷贝使数组内位置为 index+1到 （size-1）的元素往前移动一位，最后将末尾元素清理让GC回收返回删除值。由于List接口继承了Collection，因此ArrayList还有一个来自Collection接口定义的删除对象boolean remove( Object o ) ，而ArrayList自定义的remove方法是T remove(int index)删除的是下标位置的对象并返回值。

[copycode.gif]: /images/20220317/c1adb25727f74abcafe112e9b31362b5.png