17370845950

ArrayList是基于动态数组实现的列表，底层用transient Object[]存储元素并维护size变量；初始为空数组，首次add时初始化为长度10；扩容按1.5倍增长，上限为Integer.MAX_VALUE-8；支持O(1)随机访问，但中间增删需移动元素，时间复杂度O(n)，且非线程安全。

ArrayList 在 Java 中是一个基于数组实现的动态列表，核心特点是“用数组存数据，但能自动变大”。它不是固定长度的普通数组，而是一套封装好的、带扩容逻辑的对象容器。

底层用 Object[] 数组存储元素

ArrayList 的真实数据存在一个叫 elementData 的数组里：

• 类型是 transient Object[]，意味着它不参与默认序列化（序列化时会走自定义逻辑）
• 所有添加的元素——无论 Integer、String 还是 null——都会被装箱或直接引用，存进这个数组
• 同时维护一个 size 变量，记录当前实际有几个有效元素（不是数组长度）

初始容量和空数组的两种状态

创建 ArrayList 时，并不总是一上来就分配 10 个位置：

• 调用无参构造器 new ArrayList() → elementData 指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA（一个空数组）
• 第一次 add 元素时，才真正初始化为长度为 10 的数组
• 若用 new ArrayList(0) 或负数容量 → 直接指向 EMPTY_ELEMENTDATA（也是空数组），后续扩容按需增长，不会硬拉到 10

扩容机制：1.5 倍增长，不是翻倍

当 size == elementData.length，再 add 就会触发扩容：

• 计算新容量：oldCapacity + (oldCapacity >> 1)，即原长 × 1.5（位运算提速）
• 如果算出来还不够用（比如 minCapacity 要求更高），就直接取 minCapacity
• 最大不超过 Integer.MAX_VALUE - 8（JVM 数组长度上限预留空间）
• 用 Arrays.copyOf() 把老数组内容复制到新数组，旧数组丢弃

为什么查得快、中间增删慢？

这是由数组结构决定的天然特性：

• get(i) / set(i, e)：直接通过下标访问内存，O(1)
• add(e)（末尾）：只要不扩容，也是 O(1)
• add(i, e) / remove(i)：要把 i 后面所有元素整体移动，平均 O(n)
• 不支持线程安全——没加锁，多线程写必须外部同步