ArrayList集合-底层原理-浅分析

ArrayList介绍

ArrayList想必开发者对其都不陌生，对其熟练的使用是开发中的基本要求。它是我们开发中非常常用的数据存储容器之一，其底层是数组实现的，我们可以在集合中存储任意类型的数据，ArrayList是线程不安全的，非常适合用于对元素进行查找，效率较高，其增、删效率较低。

底层数据结构

ArrayList其底层数据结构采用的是数组存储结构-即线性表中的顺序表结构。

上干货-底层浅分析(基于java-8版本)

类中部分成员属性

进入ArrayList源码中，可以看到一些它的私有属性(记住这些私有属性，非常重要-用于后续分析)
请添加图片描述

构造方法

请添加图片描述

ArrayList提供了无参和有参构造方法，并且无参构造方法中，数组指向了一个空数组。其次在有参构造中，对于传入的数组大小，做了分类判断，传入的参数为0时数组又指向了另一个空数组，这两个数组的作用在后续分析中会介绍。当传入的参数为负数时，会抛出一个运行时异常。很奇怪？怎么这个异常不需要try-catch，也没有在方法处做抛出声明。
竟然谈到了异常，就简单的介绍一下异常类型吧

异常类分两大类型：Error类代表了编译和系统的错误，不允许捕获；Exception类代表了标准Java库方法所激发的异常。Exception类还包含运行异常类Runtime_Exception和非运行异常类Non_RuntimeException这两个直接的子类。

运行异常类对应于编译错误，它是指Java程序在运行时产生的由解释器引发的各种异常。运行异常可能出现在任何地方，且出现频率很高，因此为了避免巨大的系统资源开销，编译器不对异常进行检查。所以Java语言中的运行异常不一定被捕获。出现运行错误往往表示代码有错误，如：算数异常（如被0除）、下标异常（如数组越界）等。

非运行异常时Non_RuntimeException类及其子类的实例，又称为可检测异常。Java编译器利用分析方法或构造方法中可能产生的结果来检测Java程序中是否含有检测异常的处理程序，对于每个可能的可检测异常，方法或构造方法的throws子句必须列出该异常对应的类。在Java的标准包java.lang java.util 和 java.net 中定义的异常都是非运行异常。

进入IllegalArgumentException中看看是否真的是运行时异常？
请添加图片描述
请添加图片描述

add-添加方法

在idea中进入ArrayList按Ctrl+F搜索add方法，就能马上定位到add方法处。

请添加图片描述
进入**ensureCapacityInternal(size+1)**方法分析
请添加图片描述
进入1方法后，发现它调用了2个方法，并且对其中一个方法传入数组，实际元素个数+1，解下来分析方法2-calculateCapacity

请添加图片描述
请添加图片描述
看到这里我们似乎明白了这个方法的作用。当我们使用无参构造的时候，并且第一次调用该方法时，会执行下面的代码

 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }

而DEFAULT_CAPACITY等于10，minCapacity=1；所以此时该方法的返回值就是10，而如果我们调用的是有参构造或者无参构造第二次调用add（因为这个时候elementData不再是空数组了）就会直接返回size+1。

请添加图片描述
将calculateCapacity方法的返回值传入到ensureExplicitCapacity方法中，minCapacity变量在除了无参构造第一次调用add时值为10，其他情况基本上都是为元素个数+1，而 elementData.length为数组的长度。根据这个if条件的判断，大概意思是如果（元素的个数长度+1）或10大于了数组的长度，就执行grow方法，所以预测一波，grow方法应该是数组的扩容方法。

请添加图片描述
通过对其grow方法的分析，可以知道该方法主要是进行扩容。在通过无参构造创建ArrayList对象，第一次调用add时**，newCapacity - minCapacity为0-10小于0所以 newCapacity 被赋予为10，然后通过Arrays.copyOf**方法得到一个数组长度为10的新数组(扩容后的-拷贝)。并且通过上述的源码分析，可知当元素个数小于10时，ArrayList都不会对其扩容了。那问题来了，元素个数大于10时-即满容，ArrayList怎么扩容呢？还是扩容10吗？请看下面分析。
请添加图片描述
通过之前的分析可知，传入grow中的参数为11(元素个数+1)-满容时，元素个数为10。

请添加图片描述
带入参数11分析后，可知数组又扩容到了15的长度，即为原数组长度的1.5倍。哦，到此就知道了，在无参构造时，默认数组长度为0，在第一次调用add方法时，会扩容到10，而后续满容后的扩容与第一次不同，数组扩容到原数组长度的1.5倍。 光说无参构造了，那有参构造呢？也是一样吗？
通过之前的源码分析，如果传入的参数大于0，就会new一个长度为参数值的数组。这类似于无参构造第一次调用add获取一个长度为10的新数组，所以后续的扩容肯定也和无参构造后续的调用扩容一样。
那传入的参数为0的数组不是指向了空数组吗？那又是怎么扩容的？

请添加图片描述
请添加图片描述
通过上述图可知，有参构造的空数组与无参构造的空数组不一样，所以在调用calculateCapacity方法时，直接返回(size+1)也就是元素个数+1，所以后续的扩容自然而然与无参构造第二次及其以后调用add方法的扩容是一样的，都为原数组的1.5倍。

请添加图片描述
至此add方法浅分析完成。

add的重载方法

**add(int index, E element)**在指定位置index元素之前插入元素element
请添加图片描述
上述图片可以看到，在方法内部主要是调用了3个方法，并且第二个方法之前已经分析过了，第一个方法和第3个方法比较陌生，一起看看是其实现内部吧。
方法1
请添加图片描述
焕然大悟，原来就是个数组越界判断。

方法3

System中提供了一个静态方法arraycopy(),可以使用这个方法来实现数组之间的复制。对于一维数组来说，这种复制属性值传递，修改副本不会影响原来的值。对于二维或者一维数组中存放的是对象时，复制结果是一维的引用变量传递给副本的一维数组，修改副本时，会影响原来的数组
参数：
Object src：the source array. 源数组
int srcPos：starting position in the source array. 在源数组中，开始复制的位置
Object dest：the destination array. 目标数组
int destPos：starting position in the destination data. 在目标数组中，开始赋值的位置
int length：the number of array elements to be copied. 被复制的数组元素的数量

请添加图片描述
该方法看起来很陌生，其实就是一个数组的复制-浅复制和深复制。奇怪了？为什么这里要使用该方法？其实在数组指定的下标之前插入元素时，该下标元素及其以后的元素都要向后移位。我们一般都是通过for循环实现的，但是这样子效率比较低，因此ArrayList采用了效率更高一点的方法替代了普通的for循环移位。

ArrayList是如何实现ForEach循环的？

实现foreach循环，只需要实现Iterable接口中的相关方法即可。
请添加图片描述
请添加图片描述
请添加图片描述
请添加图片描述
果然ArrayList是实现了Iterable接口，而实现Iterable接口需要重写以下方法(ArrayList中的方法)

 public Iterator<E> iterator() {
        return new Itr();
    }

在该方法中返回了一个Itr对象，点进去查看？
请添加图片描述
发现它实现了Iterator接口，重写了hasNext方法和next方法，即可实现foreach循环遍历了，并且看到了熟悉的modCount变量，之前在add方法调用中出现过。

小试牛刀-模拟ArrayList

编写顺序表，模拟ArrayList，验证是否真的扩容为1.5倍

public class SequenceList<T> implements Iterable<T>{
    /**
     *
     * @author wsg
     * @date 2022/7/23
     * 数组默认长度
     */
    private static final int DEFAULT_CAPACITY = 10;

   /**
    *
    * @author wsg
    * @date 2022/7/23
    * 有参构造传入的数组大小为0时赋予的空数组
    */
    private static final Object[] EMPTY = {};


    /**
     *
     * @author wsg
     * @date 2022/7/23
     * 无参造传入赋予的空数组
     */
    private static final Object[] DEFAULT = {};
   /**
    *
    * @author wsg
    * @date 2022/7/23
    * 数组-存储数据
    */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     *
     * @author wsg
     * @date 2022/7/23
     * 数组中元素的实际大小
     */
    private int size;

    public SequenceList(int capacity) {
        //数组初始化
        if(capacity>0){
            elementData= new Object[capacity];

        }else if(capacity==0){
            elementData=EMPTY;
        }else{
            throw new IllegalArgumentException("Illegal Capacity: "+
                   capacity);
        }
        
    }
    
    public SequenceList(){
        elementData=DEFAULT;
    }

    public boolean add(T e){
        ensureCapacityInternal(size+1);
        elementData[size++]=e;
        System.out.println(elementData.length);
        return true;
    }

    public boolean add(int i,T e){
        //在线性表中的第i个元素之前插入一个值为e的数据元素
        if(i<0||i>=size){
            throw new ArrayIndexOutOfBoundsException("Illegal Capacity: "+i);
        }
        System.arraycopy(elementData,i,elementData,i+1,size-i);
        elementData[i]=e;
        size++;
        return true;
    }
    public void ensureCapacityInternal(int minCapacity){
        ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));
    }
    public int calculateCapacity(Object[] elementData, int minCapacity){

        if(elementData==DEFAULT){
            //无参构造
            return Math.max(DEFAULT_CAPACITY,minCapacity);
        }
        return minCapacity;
    }
    private void ensureExplicitCapacity(int minCapacity) {
        if(minCapacity-elementData.length>0){
            grow(minCapacity);
        }
    }
    private void grow(int minCapacity) {
        //扩容
        if(minCapacity==11){
            int a=1;
        }
        int olderCapacity=elementData.length;
        int newCapacity=olderCapacity+(olderCapacity>>1);
        if(newCapacity-minCapacity<0){
            newCapacity=minCapacity;
        }
        elementData= Arrays.copyOf(elementData,newCapacity);
    }
    public void clear(){//空置线性表
        for(int i=0;i<this.size;i++){
            elementData[i]=null;
        }
        this.size=0;
    }
    public boolean isEmpty(){//判断线性表是否为空，是返回true 否则返回false

        return this.size==0;
    }
    public int length(){//获取线性表中的元素的个数
        return this.size;
    }
    public T get(int i){//读取并返回线性表中的第i个元素的值
            if(i<0||i>=this.size){
                throw new ArrayIndexOutOfBoundsException("Illegal Capacity: "+i);
            }
            return (T) elementData[i];
    }

    public T remove(int i){
        //删除并返回线性表中第i个数据元素
        if(i<0||i>=size){
            throw new ArrayIndexOutOfBoundsException("Illegal Capacity: "+i);
        }
        //元素前移
        T temp= (T) elementData[i];
//        for(int index=i;i<size;i++){
//            elementData[i]=elementData[i+1];
//        }
        System.arraycopy(elementData,i+1,elementData,i,size-1-i);
        elementData[--size]=null;
        return temp;
    }

    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }
    private class SIterator implements Iterator{
        private int cusor;

        public SIterator() {
            this.cusor=0;
        }

        @Override
        public boolean hasNext() {
            return cusor<size;
        }

        @Override
        public Object next() {
            return elementData[cusor++];
        }
    }
}

在add方法中输出数组的长度
请添加图片描述
测试
请添加图片描述
请添加图片描述
请添加图片描述
通过测试结果，无参构造第一次扩充确实10，后续都是原数组长度的1.5倍扩充。

请添加图片描述
请添加图片描述

扩容机制为原数组长度的1.5倍

请添加图片描述
请添加图片描述
有参构造，传入的值为0，通过结果可以观察到，第一个元素添时，数组长度为1，后续都为原数组长度的1.5倍扩容(满容后)。

总结

在java8中，如果通过无参构造创建ArrayList对象，第一次添加元素时，数组长度会由原长度0扩充到10，后续满容后再添加元素，扩充到原数组长度的1.5倍。有参构造，如果传入的参数为0，则第一添加元素，数组长度为1,后续满容后扩充原则为原数组长度的1.5倍。

结尾

案例可能会有bug，其次如果有错误，请谅解，谢谢！

版权声明：本文为qq_47139621原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。