ArrayList 扩容原理

List扩容实现步骤分两步： 1、扩容 把原来的数组复制到另一个内存空间更大的数组中 2、添加元素 把新元素添加到扩容以后的数组中

ArrayList 的构造函数

ArrayList的两个构造方法 ArrayList() ArrayList(int initialCapacity)

/** * 默认初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; /** *声明空数组 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /* *不会被序列化空对象 */ transient Object[] elementData; // non-private to simplify nested class access /** *无参构造中，我们看到了在用无参构造来创建对象的时候其实就是创建了一个空数组，长度为0 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 带初始容量参数的构造函数。（用户自己指定容量） */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) {//初始容量大于0 //创建initialCapacity大小的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {//初始容量等于0 //创建空数组 this.elementData = EMPTY_ELEMENTDATA; } else {//初始容量小于0，抛出异常 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回 *如果指定的集合为null，throws NullPointerException。 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }

ArrayList add方法扩容机制

/** * 将指定的元素追加到此列表的末尾。 */ public boolean add(E e) { //添加元素之前，先调用ensureCapacityInternal方法 ensureCapacityInternal(size + 1); // Increments modCount!! //这里看到ArrayList添加元素的实质就相当于为数组赋值 elementData[size++] = e; return true; } 调用 ensureCapacityInternal() 方法就一定会进过（执行）这个方法 //得到最小扩容量 private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 获取默认的容量和传入参数的较大值 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } //判断是否需要扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) //调用grow方法进行扩容，调用此方法代表已经开始扩容了 grow(minCapacity); } /** * 要分配的最大数组大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * ArrayList扩容的核心方法。 */ private void grow(int minCapacity) { // oldCapacity为旧容量，newCapacity为新容量 int oldCapacity = elementData.length; //将oldCapacity 右移一位，其效果相当于oldCapacity /2， //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍， int newCapacity = oldCapacity + (oldCapacity >> 1); //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量， if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE， //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。 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); }

当我们要 add 进第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0 成立，所以会进入 grow(minCapacity) 方法。 当add第2个元素时，minCapacity 为2，此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。 添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。 　　直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。