ArrayList初始化及扩容机制（源码分析）
ArrayList的无参构造及扩容机制
- 首先在主函数中调用
ArrayList的无参构造方法生成一个List实例list：
List<String> list = new ArrayList<>();
点进去构造方法：
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
点进去DEFAULTCAPACITY_EMPTY_ELEMENTDATA：
/** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- 说明
ArrayList的无参构造生成了一个空的Object[]； - 此时在主函数中调用add()方法：
list.add("a");
点进去add：
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
- 注意此时
size为0，ensureCapacityInternal传入的参数为1； - 点进去
ensureCapacityInternal：
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
- 注意此时
calculateCapacity传入的参数elementData为空Object[]，minCapacity为1； - 继续点进去
calculateCapacity：
private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }
由第2步可知，此时elementData仍然是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，因此if语句条件成立，返回DEFAULT_CAPACITY与minCapacity中较大的一个。已知minCapacity此时为1，点进去DEFAULT_CAPACITY：
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;
- 因此返回的是
DEFAULT_CAPACITY，值为10； - 点进去第6步中的
ensureExplicitCapacity方法：
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
- 此时入参
minCapacity为10，而elementData的length仍为0，因此满足if条件，进入grow方法； - 点进去
grow：
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; 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); }
此时oldCapacity为0，newCapacity为0+0/2，依然为0，minCapacity为10，满足newCapacity - minCapacity < 0条件，因此将minCapacity赋值给newCapacity，此时newCapacity为10；点进去MAX_ARRAY_SIZE：
/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- 不满足
newCapacity - MAX_ARRAY_SIZE > 0条件，新的elementData被从旧的elementData复制过来。 - 从以上内容可以看出，当调用ArrayList的无参构造来创建一个List实例list时，其实创建了一个空的Object[]，初始容量为0；当第一次调用add方法时，容量被扩展到DEFAULT_CAPACITY，值为10；
然后可以一直向list中插入元素，直至list的size达到10；因为这时在第8步中，minCapacity一直小于等于elementData的length，因此不会调用grow方法扩容。
list的size达到10后，此时再次调用add方法向list中插入元素，此时在第5步ensureCapacityInternal方法传入的minCapacity为11，第8步满足minCapacity - elementData.length > 0条件，进入grow方法，此时oldCapacity为10，newCapacity为 oldCapacity + (oldCapacity >> 1)，值为15，然后将旧的elementData复制到新的elementData，扩容就完成了。
每次扩容1.5倍，直至达到MAX_ARRAY_SIZE，也就是Integer.MAX_VALUE - 8时，进入hugeCapacity方法：
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
如果容量已经大于Integer.MAX_VALUE，抛出OOM；如果介于Integer.MAX_VALUE - 8和Integer.MAX_VALUE之间，返回Integer.MAX_VALUE，否则返回Integer.MAX_VALUE - 8；
ArrayList指定容量构造函数
- 首先在主函数中调用
ArrayList的指定容量构造方法生成一个List实例list：
List<String> list = new ArrayList<>(20);
2.点进去构造方法：
/** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */ 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); } }
如果指定的初始容量大于0，那么是合法的，创建一个长度为initialCapacity的Object[]赋给elementData即可；如果指定的初始容量为0，那么也是合法的，创建一个空Object[]赋给elementData即可；如果指定的初始容量小于0，非法，抛出异常；
3.如果initialCapacity大于等于10，那么在list的size达到initialCapacity后，正常扩容即可；
4.如果initialCapacity小于10，以0为例，那么在第一次调用add方法时，calculateCapacity方法传入的minCapacity为1，但是此时elementData为EMPTY_ELEMENTDATA，而不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，因此返回的是minCapacity，值为1，而不是DEFAULT_CAPACITY，值为10；所以经过第一次扩容，list的容量仅仅被扩展为1；以此类推，第二次扩容，容量被扩展为2；第三次扩容，容量被扩展为3；第四次扩容，容量被扩展为4；第五次扩容，容量被扩展为6；第六次扩容，容量被扩展为9；第七次扩容，容量被扩展为13；此时容量才达到10以上。
ArrayList有参构造函数
- 直接在构造函数中传入一个
List实例：
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
2.点进去构造函数：
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public ArrayList(Collection<? extends E> c) { Object[] a = c.toArray(); if ((size = a.length) != 0) { if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { // replace with empty array. elementData = EMPTY_ELEMENTDATA; } }
首先将传入的集合c转换为Object[]形式，然后将该数组的长度赋值给size，并判断是否为0，若不为0，判断集合c的类型，如为ArrayList类型，则直接将c转换得到的Object[]赋值给elementData即可；否则使用Arrays.copyOf将c转换得到的Object[]转换成相应类型复制给elementData即可；若size为0，将空Object[]赋值给elementData即可；
