ArrayList源码研究

约定不等于承诺〃 2023-10-08 13:04 44阅读 0赞

#### 文章目录 ####

*  ArrayList
 *   *  构造方法
     *   *   *  \*\*无参构造\*\*
             *  \*\*有参构造\*\*
     *  add();
     *   *  第一次添加
         *  第二次添加
         *  第十一次添加
     *  get()方法
     *  set()方法
     *  remove()方法
     *  FailFast机制

背景：实习加工作也有近半年时间了，每天增删改查重复的枯燥无味，于是乎，最近开始了源码的研究，首先便是我们最常用的List接口中的ArrayList

## ArrayList ##

List<Object> list = new ArrayList<>();

新建一个ArrayList，ctrl加鼠标点进去  
除了里面的方法以外，是这么一堆代码

/**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {
        };
    
        /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    
        /**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        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;

**什么意思呢**

/**
           默认的数组的长度
         */
    	private static final int DEFAULT_CAPACITY = 10;
    	/**
         空数组
         */
        private static final Object[] EMPTY_ELEMENTDATA = {
        };
        /**
         用于默认大小的空实例的共享空数组实例。我们将其与空元素数据区分开来，以了解添加第一个元素时要充气多少。
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
         /**
           集合中存储数据的 数组对象
         */
        transient Object[] elementData; // non-private to simplify nested class access
        /**
         *  集合中元素的个数
         */
        private int size;

一共五个参数，可以看出，ArrayList`本质上其实还是一个数组`，只不过`数组是固定长度的`，而`ArrayList添加了动态扩容的机制`，但是，这种`动态扩容其实就是重新创建了一个新的数组，然后把旧数组赋值给新数组`，因为我们看不到创建新数组并赋值的过程，所以一般就把ArrayList称为长度可变的，把数组称为长度不可变  
里面的参数看完了，接下来往下看，首先映入眼帘的就是它的两个 构造方法–无参构造与有参构造，也就是对应着我们创建ArrayList时是否初始化参数。

### 构造方法 ###

##### **无参构造** #####

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

根据源码可以看出来，当我们创建一个新的空的ArrayList时，也就是把默认的数组实例`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`赋值给了集合中存储数据的数组对象`elementData`

##### **有参构造** #####

public ArrayList(int initialCapacity) {
        
            if (initialCapacity > 0) {
        
                // 初始长度大于0 就创建一个指定大小的数组
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
        
                // {}数组赋值给 this.elementData
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
        
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

如码，也是创建了一个指定长度的数组赋值给`elementData`

再往下就是add方法了，不过经过研究，发现add方法在添加数据时步骤不完全一样  
假设创建时为`无参`

### add(); ###

#### 第一次添加 ####

list.add(1);

public boolean add(E e) {
        
    	//e = 1
        // 确定容量 动态扩容 size 初始 0
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将要添加的元素 添加到数组中 elementData[0] = 1 --> size = 1
        elementData[size++] = e;
        return true;
    }

首先调用add方法，将数据传递进来，这时，初始容量为0，也就是size为0，这时会  
首先调用ensureCapacityInternal()方法，传递的参数是`size+1`也就是 `1` 让我们点进去看看里面是什么：

/**
    *int minCapacity = 1
    */
    private void ensureCapacityInternal(int minCapacity) {
        
            // ensureExplicitCapacity(默认数组实例，1) 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

好家伙，继续往里面点，先看括号里的calculateCapacity(）方法

/**
    * elementData {}
      minCapacity 1
    */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
            // 10与1比较大小  return 10
            //DEFAULT_CAPACITY:刚才源码里定义的参数，默认长度10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

这里，首先做了一个比较，如果数据为默认数组实例，则比较默认长度和当前长度的大小，返回较大的那个，由于是第一次添加，数据为默认数组实例，所以返回`10`，让我们返回刚才那个方法

/**
    *int minCapacity = 1
    */
    private void ensureCapacityInternal(int minCapacity) {
        
            // ensureExplicitCapacity(10) 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

这时，括号中的数据就变成了刚才返回的`10`了，然后进入ensureExplicitCapacity()方法

private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++; // 增长 操作次数
    
        // 10-0>0  所以需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

，这里，首先记录了操作次数`modCount`,有同学会问，操作次数`modCount`哪来的，刚才也没看到定义这个参数，大家想一下，ArrayList继承了谁？想不起来吧，贴图！  
![在这里插入图片描述][cd4536a8938c48b4b06ce0e62bc94b43.png]  
`modCount`是Arraylist的父类`AbstractList`中定义的一个`protected`变量，这个变量定义在Abstract.java文件的偏下的位置，第601行。

protected transient int modCount = 0;//记录操作次数

了解了`modCount`，再接着往下看，判断`minCapacity - elementData.length > 0`，也就是`10-0是否>0`，显而易见，执行`grow()`方法，继续点进去，

private void grow(int minCapacity) {
         // 10
        // overflow-conscious code
        int oldCapacity = elementData.length; // 0
        // newCapacity = 0
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            // newCapacity = 10 
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)//这里正常情况下都是不走这一步的
            newCapacity = hugeCapacity(minCapacity);//你会创建一个长度超过int最大值的ArrayList吗
        //返回一个新的数组 长度为10
        //Arrays的copyOf()方法传回的数组是新的数组对象,第二个参数指定要建立的新数组长度
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

到这里，已经可以看出来ArrayList所谓的扩容是怎么一回事了，  
首先，定义老数组容量`oldCapacity = elementData.length`即`oldCapacity = 0`  
然后进行`移位运算`（即将其转为二进制然后向左或向右移位），获取新数组的容量`newCapacity = oldCapacity + (oldCapacity >> 1)`，这里由于0右移后还是0，所以`newCapacity = 0`  
将新数组的容量与当前大小比较（当前为默认实例，长度为10），取大的那个，**然后与**`MAX_ARRAY_SIZE`（int的最大值）**比较**，防止长度超出可控范围，这里给出源码里`MAX_ARRAY_SIZE`的定义

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    public static final int   MAX_VALUE = 0x7fffffff;//即int最大值,7fffffff是8位16进制

再然后,`Arrays.copyOf(elementData, newCapacity);`!!!是不是很熟悉了，**复制拷贝数据到新数组**  
至次，第一次添加就结束了

#### 第二次添加 ####

此时数据为

elementData = {
        1,,,,,,,,,};
    size = 1;

一步一步的点进去，这里就不再重复解释一次了，大家看参数就好

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

区别在于这一步，数据不等于默认数组实例，所以直接返回`minCapacity=2`

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //与第一次添加时不同的地方
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 2
        return minCapacity;
    }

private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++;
    	///这里，2-10<0，所以不需要扩容
        // overflow-conscious code 2 - 10
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

至此，结束第二次添加，往下一直到第10次添加都不需要扩容，所以略过。。。。。。

#### 第十一次添加 ####

此时数据为：

elementData = {
        1,2,3,4,5,6,7,8,9,10};
    size = 10;

不再解释，看参数

list.add(11);

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

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

**当到这一步，因为11>10，所以需要扩容了**

private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++;
    
        // 11 - 10 > 0  所以需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
         // 11
        // 10
        int oldCapacity = elementData.length;
        // 15  newCapacity 是oldCapacity的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);//!!!!!!!!!!!!!!!!!!!注意这里
        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:
        // {1,2,3,4,5,6,7,8,9,10} -- > {1,2,3,4,5,6,7,8,9,10,,,,,}
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

这里就看出来为什么`ArrayList`的扩容机制，是扩容`1.5倍`了吧  
旧长度进行移位运算，右移一位，即×0.5，再加上原来的长度，  
然后`Arrays.copyOf(elementData，15)`，创建新数组并将旧数组复制进去

### get()方法 ###

这就比较简单了，源码点进去，走起：

public E get(int index) {
        
        // 检查下标是否合法
        rangeCheck(index);
    	// 通过下标获取数组对应的元素
        return elementData(index);
    }

### set()方法 ###

和get难度差不多

public E set(int index, E element) {
        
        rangeCheck(index); // 检查下标
    	// 获取下标原来的值
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

返回原来下标的值

### remove()方法 ###

假如要删除ArrayList\{1,2,3,4,5,6,7,8,9\}中的4，4的下标为3  
则

remove(3);

public E remove(int index) {
        
        rangeCheck(index);
        //记录修改次数
        modCount++;
        E oldValue = elementData(index);
    	// 获取要移动的元素的个数 {1,2,3,4,5,6,7,8,9} // 3  size=9  index=3
        //  {1,2,3,5,6,7,8,9,null}
        int numMoved = size - index - 1; // 5
        if (numMoved > 0)
            // 参数：源数组 开始下标 目标数组 开始下标 长度
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    	// 删除的节点对应的信息
        return oldValue;
    }

返回原来下标的值

### FailFast机制 ###

快速失败的机制，Java集合类为了应对`并发访问在集合迭代过程中，内部结构发生变化`的一种防护措施，这种错误检查的机制为这种可能发生错误通过抛出 `java.util.ConcurrentModificationException`

记得刚才那个`记录修改次数`的参数`modCount`吗？以及为什么ArrayList是`非线程安全的`  
留下个彩蛋，同学们可以百度了解下这个机制

答案：  
每次操作时都会将`modCount`\+1，当多线程环境下，假设，一个线程正在遍历，另一个线程对其做了修改操作，那么遍历的这个线程在遍历时会发现`modCount`这个参数与开始遍历时不一样，于是触发FailFast机制，使其快速失败，抛出异常。

[cd4536a8938c48b4b06ce0e62bc94b43.png]: https://img-blog.csdnimg.cn/cd4536a8938c48b4b06ce0e62bc94b43.png