菜鸟学JAVA之——ArrayList源码解读（易懂）

ゞ浴缸里的玫瑰 2023-06-23 13:13 16阅读 0赞

# ArrayList源码解读 #

**ArrayList底层是数组实现的**

首先了解几个必要的成员变量

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    { 
    		private static final int DEFAULT_CAPACITY = 10; //默认容量大小为10
       		private static final Object[] EMPTY_ELEMENTDATA = { };//内容放在这里，刚开始这个数组对象没有内容。当用户指定该 ArrayList 容量为 0 时，返回该空数组
         
    		private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { }; //默认的空的没有任何内容的数组。当用户没有指定 ArrayList 的容量时(即调用无参构造函数)，返回的是该数组
        
        /* ArrayList基于数组实现，用该数组保存数据, ArrayList 的容量就是该数组的长度 - 该值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入 ArrayList 中时，数组将扩容值 DEFAULT_CAPACITY(10) */
      		transient Object[] elementData; 
      		private int size;//记录容器有效数据个数
    }

`DEFAULTCAPACITY_EMPTY_ELEMENTDATA` 与 `EMPTY_ELEMENTDATA` 的区别就是：`DEFAULTCAPACITY_EMPTY_ELEMENTDATA` 数组是默认返回的，而后者是在用户指定容量为 0 时返回

**1.ArrayList()构造函数**

public ArrayList(int initialCapacity) { //可传参
            if (initialCapacity > 0) {   //初始化容量大小大于0
                this.elementData = new Object[initialCapacity];//new一个新的数组
            } else if (initialCapacity == 0) {   //参数为0，那就用定义的空数组
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
        
         public ArrayList() {  //不传参时调用这个构造方法
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
        /* 这里参数表示：传一个Collection进来为了创建ArrayList对象时把Collection里所有的内容放入ArrayList里面去。比如传进一个TreeSet的对象进来 */
        public ArrayList(Collection<? extends E> c) { 
            elementData = c.toArray();//得到这个对象的数组。方法定义在Collection接口里
            if ((size = elementData.length) != 0) { //如果当前数组长度不为空
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                //c.toArray可能没有返回一个Object数组，比如我们下面测试的传的就是String类型的
                if (elementData.getClass() != Object[].class)//判断一下
                    elementData = Arrays.copyOf(elementData, size, Object[].class); //把elementData里的内容当作Object复制出来，放入elementData里
            } else { /
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

**2.trimToSize**

public void trimToSize() { 
            modCount++;
            if (size < elementData.length) {  //如果elementData太长了，比如只放了一个值，size为1，而数组长度为10(默认)，那就需要把多余的切掉
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

**3.ensureCapacity()**  
`ensureCapacity()` 是提供给用户使用的方法，在 `ArrayList` 的实现中并没有使用，他使用的是`ensureCapacityInternal`

public void ensureCapacity(int minCapacity) { 
            
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) //minExpand：最小扩充容量，默认是10
                ? 0  //如果保存内容的数组 不是 默认的空数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）（意思就是用户指定了长度），那就先不要扩充（哪怕是用户指定长度为0也不要扩容，不要问为什么，用户乐意呀）
                : DEFAULT_CAPACITY; //如果是（意思就是通过无参的ArrayList创建的容器，用户没有指定长度，默认为0。如果要添加一个元素则要扩容，扩容的大小就是默认的大小10），那就先扩充10个
    			//上面无参构造函数创建后，当元素第一次被加入时，扩容至默认容量 10,就是靠上面这句代码
            if (minCapacity > minExpand) {   //如果最小容量大于最小扩充，则以用户指定的为准，否则还是10
                ensureExplicitCapacity(minCapacity);
            }
        }

**4.ensureCapacityInternal()、ensureExplicitCapacity()**  
add方法在添加元素之前会先调用`ensureCapacityInternal`方法，主要是有两个目的：1.如果没初始化则进行初始化；2.校验添加元素后是否需要扩容。

private void ensureCapacityInternal(int minCapacity) { 
            // 若 elementData == {}，则取 minCapacity 为 默认容量和参数 minCapacity 之间的最大值
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                minCapacity= Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            ensureExplicitCapacity(minCapacity);
        }
    
        
        private void ensureExplicitCapacity(int minCapacity) { 
            modCount++;
    
            // 如果添加该元素后的大小超过数组大小，则进行扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);//扩容
        }

**5.grow() 扩容**

private void grow(int minCapacity) { 
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1); //新的大小 = 老的大小+老的大小/2 如 oldCapacity = 10,则 newCapacity = 10 + (10 >> 1) = 10 + 5 = 15
            if (newCapacity - minCapacity < 0) //若 newCapacity 依旧小于 minCapacity
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0) //若 newCapacity 大于最大存储容量，则进行大容量分配
                newCapacity = hugeCapacity(minCapacity);
            elementData = Arrays.copyOf(elementData, newCapacity); //将elementData扩容为newCapacity大小再赋值回去
        }

把上面的代码走一遍，方便理解。比如现在新创建一个对象，没有放任何内容，调用`ensureCapacity`传的参数为13， 这时`elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA` ，则`minExpand = DEFAULT_CAPACITY`=10.然后13>10，调用`ensureExplicitCapacity`，且把13传入。因为`minCapacity - elementData.length`=13-10 > 0，所以执行grow，`newCapacity`为0，`newCapacity - minCapacity` = 0-13 < 0，所以`newCapacity`为13.所以新数组`elementData`大小变为13

**6.toArray()**

/* * 返回 ArrayList 的 Object 数组 * - 包含 ArrayList 的所有储存元素 * - 对返回的该数组进行操作，不会影响该 ArrayList（相当于分配了一个新的数组）==>该操作是安全的 * - 元素存储顺序与 ArrayList 中的一致 */
        public Object[] toArray() { 
            return Arrays.copyOf(elementData, size);
        }

**7.add()**

public boolean add(E e) { 
            ensureCapacityInternal(size + 1);  //第一件事就是确认长度，因为如果往里放一个值则可能导致数组溢出，所以先判断一下。如果将导致溢出则自动扩容（原来大小的1.5倍）
            elementData[size++] = e;
            return true;
        }
    
    //相当于插入一个元素
    public void add(int index, E element) { 
            rangeCheckForAdd(index); //检查index是否合理
    
            ensureCapacityInternal(size + 1);  //确认长度
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);//表示在原来数组的基础上将index位置上的值拷贝到index+1的位置上，从index开始依次往后拷贝size-index个
        //eg：容量10，有效值有5个，index为3，则要将3号位置的值拷贝到4号位置，将4号位置的值拷贝到5号位
            elementData[index] = element;//将要加入的元素放在index处
            size++;
        }

**8.remove()**

/** * 移除指定位置的元素 * index 之后的所有元素依次左移一位 * @param index 指定位置 * @return 被移除的元素 * @throws IndexOutOfBoundsException */
    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);  //从index+1的位置开始挪，向前挪一位，挪动numMoved个
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }

> 学习参考：  
> [https://blog.csdn.net/qq\_33842627/article/details/88701461][https_blog.csdn.net_qq_33842627_article_details_88701461]  
> [https://www.cnblogs.com/gxl1995/p/7534171344218b3784f1beb90d621337.html][https_www.cnblogs.com_gxl1995_p_7534171344218b3784f1beb90d621337.html]

[https_blog.csdn.net_qq_33842627_article_details_88701461]: https://blog.csdn.net/qq_33842627/article/details/88701461
[https_www.cnblogs.com_gxl1995_p_7534171344218b3784f1beb90d621337.html]: https://www.cnblogs.com/gxl1995/p/7534171344218b3784f1beb90d621337.html