Java中的ArrayList容量及扩容方式

 /** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;

 /** * 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; 

 /** * 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 = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity  MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

 // ArrayList 默认容量大小 private static final int DEFAULT_CAPACITY = 10; // 一个共享的空数组, 在空实例时使用 private static final Object[] EMPTY_ELEMENTDATA = {}; // 一个共享的空数组, 在使用默认 size 的空实例时使用 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /* 存储 ArrayList 元素的数组缓冲区 重点1: ArrayList 的容量是数组缓冲区的长度 重点2: 从这个元素也可以看的出来 ArrayList() 的底层就是一个 Object[] add 第一个元素时, 任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将被扩展为 DEFAULT_CAPACITY */ transient Object[] elementData; // ArrayList 的大小, 我们平常使用的 list.size() 底层就是记录的这个 size private int size; // ArrayList 最大 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

 /* 带参构造器, 参数为容量大小, 例如: 初始化一个容器为 20 类型为 Integer 的 ArrayList ArrayList list = new ArrayList(20); */ public ArrayList(int initialCapacity) { /* 初始化容量 > 0, elementData 初始化为初始化容量大小的数组 初始化容量 = 0, elementData = EMPTY_ELEMENTDATA (空数组) 初始化容量  0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }

 /* 将一个参数为 Collection 的集合转换为 ArrayList */ public ArrayList(Collection c) { // Collection 转换为数组 Object[] 类型 elementData = c.toArray(); // 判断当前对象大小是否和 Collection 长度相等并且不等于 0, false 的话 elementData 等于空数组了 if ((size = elementData.length) != 0) { // c.toArray() 可能不会正确地返回一个 Object[] 数组，所以使用 Arrays.copyOf() if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = EMPTY_ELEMENTDATA; } }

 /* 不带参构造器就像我们平时使用一样, 直接 new 一个 ArrayList 不需要传递任何参数 构造方法中直接将 elementData 初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA (空数组) */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

 public boolean add(E e) { // 这一行是关键, 看下面 ensureCapacityInternal(size + 1); // 将元素追加到集合的末尾 假如当前 size = 10 size++ 追加到第 11 位 elementData[size++] = e; return true; }

 private void ensureCapacityInternal(int minCapacity) { /* calculateCapacity() 方法, 刚初始化时会返回 10, 其他情况返回当前 size + 1 ensureExplicitCapacity() 方法, 调用扩容 */ ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { /* 使用无参构造器创建创建 ArrayList 的集合, 此时一定是相等的 */ if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { /* 两数相比返回最大值, 此时 Math.max(10, 1); 默认容量, 由此而来 */ return Math.max(DEFAULT_CAPACITY, minCapacity); } // 不相等的话只有返回当前的 size + 1 return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { // 增量, 记录修改/更新次数 modCount++; // 初始化: 10 - 0 > 0 // 其他: size + 1 > 0 if (minCapacity - elementData.length > 0) // 扩容操作 grow(minCapacity); } private void grow(int minCapacity) { // 老的长度, 初始化时为 0, int oldCapacity = elementData.length; // 新的长度此时 0 + (0 >> 1), newCapacity = 0 int newCapacity = oldCapacity + (oldCapacity >> 1); // 初始化场景: 0 - 10 <0 ? true newcapacity=10 if (newcapacity - mincapacity  0 返回 false if (newCapacity - MAX_ARRAY_SIZE > 0) // 超大长度才可以执行这个方法, 必须大于 MAX_ARRAY_SIZE 一般不会 newCapacity = hugeCapacity(minCapacity); // 复制原数组中的元素, 并扩容 elementData = Arrays.copyOf(elementData, newCapacity); } 

 private void ensureCapacityInternal(int minCapacity) { /* calculateCapacity() 方法, 正常扩容返回 size + 1, 比如 10 + 1, 因为默认长度为 10 当再次新增数据时就会出发扩容 ensureExplicitCapacity() 方法, 调用扩容 */ ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } /* elementData 不等于空数组 返回当前的 size + 1, 即 10 + 1 返回 11 */ return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { // 增量, 记录修改/更新次数 modCount++; // 其他: 11 - 10 > 0 true, 触发扩容, 如果当前下表是 5 的话 5 + 1 =6, 6  0) // 扩容操作 grow(minCapacity); } private void grow(int minCapacity) { // 老的长度 10 int oldCapacity = elementData.length; // 新的长度此时 10 + (10 >> 1), newCapacity = 15 int newCapacity = oldCapacity + (oldCapacity >> 1); // 15 - 11 <0 ? false if (newcapacity - mincapacity  0 返回 false if (newCapacity - MAX_ARRAY_SIZE > 0) // 超大长度才可以执行这个方法, 必须大于 MAX_ARRAY_SIZE 一般不会 newCapacity = hugeCapacity(minCapacity); // 复制原数组中的元素, 并扩容 newCapacity = 15 elementData = Arrays.copyOf(elementData, newCapacity); } 

 oldCapacity + (oldCapacity >> 1) 即: 10 + (10 >> 1)