ArrayList源码：add 方法

布满荆棘的人生 2023-01-23 01:05 113阅读 0赞

## 1. add(E e)： ##

// 向列表中追加一个元素。
    // size：当前列表中元素的数量。
    public boolean add(E e) { 
        // size+1 表示最小容量。最小容量 == 当前列表中元素个数+1。
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 到这里已经扩容结束了。将新元素追加到数组。
        elementData[size++] = e;
        // 添加成功，返回 true。
        return true;
    }

看下扩容函数： `ensureCapacityInternal(size + 1)`

private void ensureCapacityInternal(int minCapacity) { 
        // 1.先计算出所需的最小容量。
        // 2.确认最小容量，并执行扩容。
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

（1）计算所需的最小容量。如果是向空列表中 add 元素，最小容量取 `默认容量(10)` 和 `待添加的元素个数` 中较大的那个。如果是向非空列表中 add 元素，最小容量直接取：`当前列表中元素的个数 + 待添加的元素的个数`。

// 计算需要的最小容量。minCapacity == 当前数组元素个数 + 要添加的元素的个数。
    // DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
    // DEFAULT_CAPACITY = 10
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        // 向空数组中添加元素，比如第一次 add 元素时才会触发
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            // 返回 默认容量 和 minCapacity 中最大的。
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 向非空数组 add 时，直接返回 minCapacity。
        return minCapacity;
    }

（2.1）确认是否扩容。只有当 计算所需要的最小容量 大于 当前数组的长度时，才扩容。

// minCapacity 是计算出来的最小容量。
    private void ensureExplicitCapacity(int minCapacity) { 
        // 这个是校验并发用的。
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            // 当需要的最小容量 > 当前数组的长度时， 执行扩容。
            grow(minCapacity);
    }

（2.2） 执行扩容。

// minCapacity 是所需的细小容量。
    private void grow(int minCapacity) { 
        // 当前数组的长度。
        int oldCapacity = elementData.length;
        // 扩容到当前数组长度的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果扩容后的容量还小于所需的最小容量，那就以计算需要的为准（再将容量扩大）。
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 再判断，如果新容量是个很大的数子，快逼近 int 的极限的了，但还没有溢出，
        // 那就直接将新容量扩大到 int 的极限。
        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);
    }
    
    // 极大的扩容
    private static int hugeCapacity(int minCapacity) { 
        // 如果容量超 int 范围了，报异常。
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 三段式，确定大容量的准确值。
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
    }

## 2. addAll(Collection<? extends E> c) ##

// 向列表中追加一个list。
    public boolean addAll(Collection<? extends E> c) { 
        // 拿出 list 中元素保存到数组中。
        Object[] a = c.toArray();
        // 获取追加的元素个数。
        int numNew = a.length;
        // 给原本的 elementData 扩容。
        ensureCapacityInternal(size + numNew);  // Increments modCount
        // 将 a 数组中的元素从 0 开始，依次复制到 elementData 的 size 位置开始，并往后推
        // 总共复制 numNew 个。
        System.arraycopy(a, 0, elementData, size, numNew);
        // 更新列表长度。
        size += numNew;
        return numNew != 0;
    }

## 3. add(int index, E element) ##

// 在指定索引出插入元素。
       public void add(int index, E element) { 
           // 检查是否越界。
           rangeCheckForAdd(index);
           // 扩容。
           ensureCapacityInternal(size + 1);  // Increments modCount!!
           // 将 index 位置以及后面的元素，向后移动 1 为。
           System.arraycopy(elementData, index, elementData, index + 1,
                            size - index);
           // 在指定位置插入元素。
           elementData[index] = element;
           // 列表中元素个数 + 1。
           size++;
       }

## 4. addAll(int index, Collection<? extends E> c) ##

// 在指定索引出插入一个集合。
       public boolean addAll(int index, Collection<? extends E> c) { 
           // 检查索引是否越界。
           rangeCheckForAdd(index);
           // 集合里的元素保存到数组中。
           Object[] a = c.toArray();
           // 数组长度。
           int numNew = a.length;
           // 扩容。
           ensureCapacityInternal(size + numNew);  // Increments modCount
           // 原数组中要向后移动的元素的个数。
           int numMoved = size - index;
           // 如果向后移动的元素的个数大于 0。
           if (numMoved > 0)
               // index 位置开始向后，总共 numMoved 元素，均向后移动 numNew 的距离。
               System.arraycopy(elementData, index, elementData, index + numNew,
                                numMoved);
           // 将 a 中的元素从 elementData 的 index 位置开始，其次复制到 elementData 中。
           System.arraycopy(a, 0, elementData, index, numNew);
           // 列表中总元素个数更新。
           size += numNew;
           return numNew != 0;
       }

## 5. ArrayList() 无参构造函数。 ##

private static final int DEFAULT_CAPACITY = 10;
    
    public ArrayList() { 
        // 创建空数组，此时 ArrayList 对象默认的 capacity = 10。
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

## 6. 小问题 ##

public class MyArrayListAdd { 
    
      public static void main(String[] args){ 
        ArrayList<String> demo = new ArrayList<>();
        demo.add("diego");
        demo.add("amos");
      }
    }

三行代码，每执行一行，列表容量和数组的数组的长度是分别是多少？

ArrayList<String> demo = new ArrayList<>();

默认容量：10 ，空数组长度是：0

demo.add("diego");

向空列表中 add 元素，需求容量是 1，默认容量是 10 ，取较大的，所以计算的最小容量是 10。因为 最小容量大于当前数组长度，要扩容，最终确认的容量也是 10，因此创建长度为 10 的数组，最后向里面追加一个元素。

容量：10，数组长度：10，但里面只有一个元素。

demo.add("amos");

向非空列表中 add 元素，需求容量是 2，所以计算出来的最小容量直接是 2。因为计算出来的最小容量小于当前数组的长度。不需要扩容。直接在向数组中追加新元素。

容量：2，数组长度 10，里面有两个元素。

# 7. Vector 和 ArrayList 的区别是什么？ #

> **Vector 是线程安全版的 ArrayList。**

对比一下 add 方法的源码就能看清楚了

// Vector.java
    
    // synchronized 加锁 
      public synchronized boolean add(E e) { 
          modCount++;
          ensureCapacityHelper(elementCount + 1);
          elementData[elementCount++] = e;
          return true;
      }

// ArrayList.java
    public boolean add(E e) { 
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }