ArrayList的扩容机制

ArrayList的扩容机制是其动态数组实现的核心，确保在添加元素时容量自动调整。以下是其详细机制：

1. 初始容量

• 默认初始容量为10（当使用无参构造函数创建时）。
• 用户可通过构造函数指定初始容量，以减少初期扩容次数。

2. 触发扩容条件

当添加元素（如add()或addAll()）时，若当前元素数量（size）加1超过数组长度（elementData.length），则触发扩容。

3. 扩容策略

• 计算新容量：新容量通常为旧容量的1.5倍（即newCapacity = oldCapacity + (oldCapacity >> 1)）。
• 确保最小容量：若新容量仍小于所需的最小容量（如size + numNewElements），则直接使用最小容量作为新容量。
• 处理大容量情况：若新容量超过预设的最大数组大小（MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8），则调整至Integer.MAX_VALUE，否则抛出OutOfMemoryError。

4. 扩容实现步骤

1. 检查容量：确定当前数组是否已满。
2. 计算新容量：

   int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍旧容量
   if (newCapacity - minCapacity < 0) {newCapacity = minCapacity; // 确保满足最低需求
   }
   

3. 处理大容量异常：

   if (newCapacity > MAX_ARRAY_SIZE) {newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
   }
   

4. 数组复制：使用Arrays.copyOf()将旧数组数据迁移到新数组。

5. 手动优化扩容

用户可通过ensureCapacity(int minCapacity)提前扩容，避免多次自动扩容的开销。此方法直接将容量扩展至minCapacity或更大（若1.5倍旧容量仍不足）。

6. 示例说明

• 默认扩容：初始容量10，添加第11个元素时扩容至15（10 + 5）。
• 批量添加：若当前容量10，需添加6个元素（总size=11），直接扩容至15；若需添加11个元素（总size=16），则扩容至16（因1.5倍旧容量15不足）。

7. 性能建议

• 预分配容量：在已知数据量较大时，通过构造函数或ensureCapacity()预设容量，减少扩容次数。
• 避免频繁插入：扩容涉及数组复制，时间复杂度为O(n)，建议批量操作。

8. 最大容量限制

• 理论最大值为Integer.MAX_VALUE，但实际受虚拟机限制，接近时可能抛出内存错误。

总结

ArrayList通过1.5倍动态扩容平衡了内存使用与性能，同时在必要时直接扩展至所需容量，确保高效的数据管理。理解其机制有助于优化代码性能，特别是在处理大量数据时。