[Java 源码] 美团一面~ArrayList 的底层实现

- 日理万妓 2024-02-17 10:43 18阅读 0赞

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

*   *   *  1. ArrayList 与 数组的区别
         *  2 ArrayList 的初始化容量
         *  3. ArrayList 的扩容具体指什么
         *  4. ArrayList是如何实现扩容的？
         *  5. ArrayList有缩容吗？

#### 1. ArrayList 与 数组的区别 ####

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

#### 2 ArrayList 的初始化容量 ####

// 默认容量是10
    private static final int DEFAULT_CAPACITY = 10;
    // 如果容量为0的时候，就返回这个数组
    private static final Object[] EMPTY_ELEMENTDATA = {
        };
    // 使用默认容量10时，返回这个数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    // 元素存放的数组
    transient Object[] elementData;
    // 元素的个数
    private int size;
    
    // 记录被修改的次数
    protected transient int modCount = 0;
    // 数组的最大值
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

ArrayList有三个构造方法，不同的构造方法的容量是不一样的，具体可以查看JDK 源码。  
● 如果不传入初始容量，就使用默认容量，并设置 elementData为DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA  
● 如果传入初始容量，会判断这个传入的值，如果大于0，就 new一个新的Object数组，如果等于0，就直接设置 elementData为 EMPTY\_ELEMENTDATA。  
● 如果传入一个 Collection，则会调用toArray()方法把它变成一个数组并赋值给elementData。同样会判断它的长度是否为0，如果为0，设置elementData为EMPTY\_ELEMENTDATA。

#### 3. ArrayList 的扩容具体指什么 ####

ArrayList里面有两个概念，一个是capacity，它表示的就是“容量”，其实质是数组elementData的长度。而size则表示的“存放的元素的个数”。  
因为 Java 中，数组操作不能越界，所以我们必须要保证在插入操作的时候，不会抛出数组越界异常。

#### 4. ArrayList是如何实现扩容的？ ####

扩容主要分两种，自动扩容和手动扩容。  
自动扩容底层主要是三个私有方法：

// 扩容一个
    private Object[] grow() {
        
    	return grow(size + 1);
    }
    
    // 保证扩容到期望容量minCapacity及以上
    private Object[] grow(int minCapacity) {
        
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
    
    // 根据期望容量minCapacity计算实际需要扩容的容量
    private int newCapacity(int minCapacity) {
        
        // overflow-conscious code
        int oldCapacity = elementData.length; // 得到旧容量
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 设置新容量为旧容量的1.5倍
        if (newCapacity - minCapacity <= 0) {
         // 如果新容量仍然小于期望容量
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 如果是使用的默认容量
                return Math.max(DEFAULT_CAPACITY, minCapacity); // 取默认容量和期望容量较大值返回
            if (minCapacity < 0) // overflow // 检查期望容量是否越界（int 的范围）
                throw new OutOfMemoryError();
            return minCapacity; // 返回期望容量
        }
        // 如果新容量大于期望容量，判断一下新容量是否越界
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

可以看到，底层其实是调用了Arrays.copyOf方法来进行扩充数组容量的。这里我们主要看一下最后一个方法newCapacity(int minCapacity)的实现。

> 默认情况下，新的容量会是原容量的1.5倍，这里用了位运算提高效率。一般情况下，如果扩容1.5倍后就大于期望容量，那就返回这个1.5倍旧容量的值。而如果小于期望容量，那就返回期望容量。这里对默认容量10做了特殊处理。  
> 使用1.5倍这个数值而不是直接使用期望容量，是为了防止频繁扩容影响性能。试想如果每次add操作都要扩容一次，那性能将会非常低下。

手动扩容主要是一个公有方法ensureCapacity：

public void ensureCapacity(int minCapacity) {
        
        if (minCapacity > elementData.length
            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                 && minCapacity <= DEFAULT_CAPACITY)) {
        
            modCount++;
            grow(minCapacity);
        }
    }

#### 5. ArrayList有缩容吗？ ####

ArrayList没有缩容。无论是remove方法还是clear方法，它们都不会改变现有数组elementData的长度。但是它们都会把相应位置的元素设置为null，以便垃圾收集器回收掉不使用的元素，节省内存。