文章首发于：clawhub.club

集合扩容就是集合容量大小不能满足需要存储数据的数量，而需要将elementData 容器大小增大，以存储更多的元素。
ArrayList的扩容机制提高了性能，如果每次只扩充一个，那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。
如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
   // 集合最大容量
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认储是容量10
private static final int DEFAULT_CAPACITY = 10;
   /**
    * 添加元素
    * @param e
    * @return
    */
   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       elementData[size++] = e;
       return true;
   }
   /**
    * 确认集合内部容量大小
    * @param minCapacity 添加元素后容器的最小容量
    */
   private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }
   /**
    * 计算集合的容量
    * @param elementData 存储数据的容器
    * @param minCapacity 添加元素后容器的最小容量
    * @return
    */
   private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //获取默认的容量和传入参数的较大值
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           return Math.max(DEFAULT_CAPACITY, minCapacity);
       }

       return minCapacity;
   }
   /**
    * 确认明确的容量大小
    * @param minCapacity 添加元素后容器的最小容量
    */
   private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
	// 如果最小容量大于元素个数
       if (minCapacity - elementData.length > 0)
	    // 扩容
           grow(minCapacity);
   }

   /**
    * 扩容方法
    * @param minCapacity 添加元素后容器的最小容量
    */
   private void grow(int minCapacity) {
       // 扩容前容器大小
       int oldCapacity = elementData.length;
       // 扩容关键算法，newCapacity 扩容后容器大小：扩大了1.5倍
       int newCapacity = oldCapacity + (oldCapacity >> 1);
	// 然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
       if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
	// 再检查新容量是否超出了ArrayList所定义的最大容量，
       // 若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
       if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
       // 将扩容后的容器赋值给存储容器
       elementData = Arrays.copyOf(elementData, newCapacity);
   }
   /**
   * 溢出处理
   */
   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) throw new OutOfMemoryError();
       // 超过最大值不合法，直接将容量大小定义为Intager 的最大值
       return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
   }

扩容算法是首先获取到扩容前容器的大小。然后通过oldCapacity + (oldCapacity >> 1) 来计算扩容后的容器大小newCapacity。
这里用到了>> 右移运算，即容量增大原来的1.5倍。
还要注意的是，这里扩充容量时，用的时Arrays.copyOf方法,其内部也是使用的System.arraycopy方法。
区别：

  • arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置
  • copyOf()是系统自动在内部新建一个数组，并返回该数组。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
       public static <T> T[] copyOf(T[] original, int newLength) {
           return (T[]) copyOf(original, newLength, original.getClass());
       }
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
           @SuppressWarnings("unchecked")
           T[] copy = ((Object)newType == (Object)Object[].class)
               ? (T[]) new Object[newLength]
               : (T[]) Array.newInstance(newType.getComponentType(), newLength);
           System.arraycopy(original, 0, copy, 0,
                            Math.min(original.length, newLength));
           return copy;
       }