从面试角度分析ArrayList源码

电玩女神 2021-09-18 06:20 384阅读 0赞

> 注：本系列文章中用到的jdk版本均为`java8`

`ArrayList`类图如下：

![66b8e10aa027583ce382c27faa308fb2.png][]

`ArrayList`的底层是由数组实现的，数组的特点是`固定`大小，而`ArrayList`实现了`动态扩容`。

`ArrayList`部分变量如下，在下面的分析中会用到这些变量。

/** * 默认容量 */
    private static final int DEFAULT_CAPACITY = 10;
    /** * 空的对象数组 */
    private static final Object[] EMPTY_ELEMENTDATA = { };
    /** * 无参构造器创建的空数组 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    /** * 存放数据的数组的缓存变量 */
    transient Object[] elementData;
    /** * 元素数量 */
    private int size;

### 一、初始化ArrayList ###

初始化`ArrayList`一般会使用以下两个构造器

#### 1.1 无参构造器 ####

初始化`ArrayList`的时候如果不指定大小，则会创建一个空数组。

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

#### 1.2 指定数组大小的构造器 ####

创建一个**预估**大小的数组，指定大小后只是指定了数组初始值的大小，不影响后面扩容，指定的好处就是可以节省内存及时间上的开销。

public ArrayList(int initialCapacity) { 
        if (initialCapacity > 0) { 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }

### 二、添加元素、动态扩容 ###

ArrayList.add(E e)源码：

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

`add()`中`elementData[size++] = e`很好理解，就是将元素插入第`size`个位置，然后将`size++`，我们重点来看看`ensureCapacityInternal(size + 1)`方法；

private void ensureCapacityInternal(int minCapacity) { 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

`ensureCapacityInternal()`方法中判断缓存变量`elementData`是否为空，也就是判断是否是第一次添加元素，如果是第一次添加元素，则设置初始化大小为默认容量`10`，否则为传入的参数。这个方法的目的就是**获取初始化数组容量**。获取到初始化容量后调用`ensureExplicitCapacity(minCapacity)`方法；

private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

`ensureExplicitCapacity(minCapacity)`方法用来判断是否需要扩容，假如第一次添加元素，`minCapacity`为`10`，`elementData`容量为`0`，那么就需要去扩容。调用`grow(minCapacity)`方法。

// 数组的最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    private void grow(int minCapacity) { 
        // overflow-conscious code
        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);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

`grow(minCapacity)`方法对数组进行扩容，扩容大小为原数组的`1.5`倍，如果计算出的扩容容量比需要的容量小，则扩容大小为需要的容量，如果扩容容量比数组最大容量大，则调用`hugeCapacity(minCapacity)`方法，将数组扩容为整数的最大长度，然后将`elemetData`数组指向新扩容的内存空间并将元素复制到新空间。

当需要的集合容量特别大时，扩容`1.5`倍就会非常消耗空间，因此建议初始化时预估一个容量大小。

### 三、删除元素 ###

`ArrayList`提供两种删除元素的方法，可以通过`索引`和`元素`进行删除。两种删除大同小异，删除元素后，将后面的元素一次向前移动。

ArrayList.remove(int index)源码：

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);
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }

删除元素时，首先会判断索引是否大于`ArrayList`的大小，如果索引范围正确，则将索引位置的下一个元素赋值到索引位置，将`ArrayList`的大小`-1`，最后返回移除的元素。操作图如下，假如我要移除索引为`1`的元素：

![39d1f96653c8575de1138d8dc3ed4a5d.png][]

### 四、总结 ###

`ArrayList`底层是数组实现的，可以进行动态扩容，扩容大小为原来的1.5倍，虽然可以通过动态扩容，但是数组非常大时会特别浪费空间，因此建议初始化时预估数组大小。`ArrayList`允许插入重复值和空值。`ArrayList`实现了`RandomAccess`接口，支持快速随机访问，就是可以通过索引快速查到某个元素，因此遍历时使用for循环的方式效率更高。`ArrayList`是线程不安全的，可以通过`Collections.synchronizedList`将其转变为线程安全的集合，不过一般不会使用，`Vector`和`CopyOnWriteArrayList`是线程安全的，`Vector`性能一般，逐渐被`CopyOnWriteArrayList`取代了。

## 点关注、不迷路 ##

如果觉得文章不错，欢迎**关注**、**点赞**、**收藏**，你们的支持是我创作的动力，感谢大家。

如果文章写的有问题，请不要吝惜文笔，欢迎留言指出，我会及时核查修改。

如果你还想看到更多别的东西，可以微信搜索「**Java旅途**」进行关注。「**Java旅途**」目前已经整理各种中间件的使用教程及各类Java相关的面试题。扫描下方**二维码**进行关注就可以得到这些资料。

[66b8e10aa027583ce382c27faa308fb2.png]: /images/20210918/94b67621166e44d5af2a46b9b0f63b6b.png
[39d1f96653c8575de1138d8dc3ed4a5d.png]: /images/20210918/49f60e2ed94f4b688ed6b63978ba6333.png