Java基础进阶-ArrayList原理

港控/mmm° 2023-01-22 10:56 26阅读 0赞

### 1、ArrayList介绍 ###

ArrayList是List接口的实现类，它表示动态数组，何为动态数组？

我们定义一个数组类型的变量需要指定数组的长度，长度一旦指定就无法扩容，比如：我们定义一个100个元素长度的数组，当需要存储的元素个数达到100以上时多余的元素将无法存储，ArrayList动态数组可以解决这个问题，ArrayList可以实现自动扩容数组。

ArrayList的特点如下：

1）查询快

ArrayList的底层是数组，根据索引查询元素速度很快。

2）增删慢

向数组添加或删除元素后需要移动其它元素位置，所以对于频繁增删的需求不建议使用ArrayList。

3）线程不安全

在多线程章节会讲解线程安全的问题，这里先简单理解为当多线程访问ArrayList 中的元素时会出现数据错乱的问题。

### 2、ArrayList底层是一个数组 ###

ArrayList的底层是一个数组，查看ArrayList的源代码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70]  
阅读elementData的注释说明：

elementData是ArrayList存放元素的区域，ArrayList的容量就是这个数组的长度。

空的ArrayList使用一个空的Object\[\]数组初始化，当添加第一个元素的时候自动扩容至10个长度。

### 3、ArrayList的容量与大小 ###

构造ArrayList可以指定初始容量参数，如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70 1]  
初始容量即为Object\[\] elementData的长度。

ArrayList还有一个size的属性，它表示实际填入ArrayList的元素的多少，如下代码：

//指定初始容量为15
    List<String> list = new ArrayList<>(15);
    
    //添加元素
    list.add("hello");
    list.add("hello");
    list.add("pbteach");
    list.add(".com");
    //元素个数
    int size = list.size();
    System.out.println(size);

### 4、ArrayList自动扩容 ###

添加元素时判断容量是否够用，并进行自动扩容，查阅add添加元素的方法源代码，如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70 2]  
ensureCapacityInternal(size + 1);为扩容方法。

elementData\[size++\] = e; 将元素添加到末尾。

扩容方法如下：

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

calculateCapacity(elementData, minCapacity)计算容量，方法如下：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    	//如果数组为空则则判断minCapacity与默认容量10的大小，返回大者
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        	return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

grow为具体的扩容方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70_pic_center]  
int newCapacity = oldCapacity + (oldCapacity >> 1)表示默认将容量扩容至原来的1.5倍。

通过hugeCapacity(int minCapacity)方法得知容量最大为Integer.MAX\_VALUE。

确定扩容的容量后使用Arrays.copyOf方法复制原来的数组到新数组。

在执行remove方法移除元素后将后边的元素向左移动，最后一个元素置为null，源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70 3]  
上边红色方框的代码实现了将移除元素后边的元素向左移动，system.arraycopy方法的描述如下：

/**
     *将指定源数组中的数组从指定位置复制到目标数组的指定位置。 
     * src - 源数组。 
     * srcPos - 源数组中的起始位置。 
     * dest - 目标数组。 
     * destPos - 目的地数据中的起始位置。 
     * length - 要复制的数组元素的数量。 
     */
    public static void arraycopy(Object src,
                                 int srcPos,
                                 Object dest,
                                 int destPos,
                                 int length)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70]: /images/20221020/a7fe60c008b040839ea9cb60e838b746.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70 1]: /images/20221020/f6fd43f23e134a36918c4f67b05c7593.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70 2]: /images/20221020/59eee2f830524ced8643ddde2e93538d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/6a24346898874ad78d9d2c337b9aee2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA2MjMzOQ_size_16_color_FFFFFF_t_70 3]: /images/20221020/e9cbf227ac284ffda4ca16d69815bba4.png