ArrayList 扩容机制详解

ArrayList 扩容机制详解

ArrayList 是 Java 用得最多的 List，底层是动态数组。理解扩容机制能避免一些性能问题。

1. 底层结构

transientObject[]elementData;privateintsize;

// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;

注意：new ArrayList() 的时候，elementData 是一个空数组，不是长度 10 的数组。第一次 add 的时候才扩容到 10。 ```java private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

2. add 操作

publicbooleanadd(Ee){ensureCapacityInternal(size+1);elementData[size++]=e;returntrue;}privatevoidensureCapacityInternal(intminCapacity){ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));}privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA)returnMath.max(DEFAULT_CAPACITY,minCapacity);// 第一次扩到 max(10, 1)returnminCapacity;}privatevoidensureExplicitCapacity(intminCapacity){modCount++;if(minCapacity-elementData.length>0)grow(minCapacity);// 需要扩容}

3. grow 扩容

privatevoidgrow(intminCapacity){intoldCapacity=elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);// 1.5 倍if(newCapacity<minCapacity)newCapacity=minCapacity;if(newCapacity>MAX_ARRAY_SIZE)newCapacity=hugeCapacity(minCapacity);elementData=Arrays.copyOf(elementData,newCapacity);}

扩容为原来的 1.5 倍（oldCapacity + oldCapacity / 2）。

Arrays.copyOf底层调用 System.arraycopy，是 native 方法，内存拷贝效率很高。

4. 指定初始容量

如果知道大概要放多少元素，指定初始容量可以避免多次扩容：

// 知道要放 1000 个元素List<String>list=newArrayList<>(1000);

不指定的话：10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → 244 → 366 → 549 → 823 → 1234。中间扩容了 12 次！

每次扩容都要数组拷贝，频繁扩容会影响性能。特别是数据量大的时候，一次扩容拷贝几万个元素，耗时不少。

5. 批量添加

// addAll 效率更高List<String>list=newArrayList<>(existingList.size());list.addAll(existingList);// 比 for 循环 add 好，因为内部做了容量预检查

6. trimToSize

list.trimToSize();// 缩小到实际 size

大量删除后数组还有冗余空间，可以用 trimToSize 回收内存。

7. 数组和链表的选择

ArrayList 随机访问 O(1)，中间插入删除 O(n)。
LinkedList 随机访问 O(n)，头尾操作 O(1)。

绝大多数场景 ArrayList 性能更好，因为：CPU 缓存对连续内存布局友好，随机访问效率远高于链表的指针跳转。除非大量头尾操作，否则优先用 ArrayList。