ArrayList的get(int index)是O(1)，因其底层为连续内存的Object[]数组，可通过baseAddress + index * elementSize直接计算地址；扩容不影响读性能，但边界检查、GC移动、并发修改等会隐式拖慢速度。
为什么 ArrayList 的 get(int index) 是 O(1)？
因为底层是 Object[] 数组，而数组在内存中是连续存储的。给定起始地址和索引，JVM 可以直接算出目标元素的内存偏移量：baseAddress + index * elementSize，跳过遍历过程。
这和 LinkedList 形成鲜明对比——后者要从头或尾开始逐个跳 next 或 prev 指针，get() 是 O(n)。
注意：这个 O(1) 仅指「访问」，不包含边界检查开销（ArrayList 每次 get 都会执行 if (index >= size) 判断，但这是常数时间）。
elementData 数组真的一直满吗？扩容怎么影响随机访问？
ArrayList 的实际数据存放在私有字段 elementData 中，它的长度（elementData.length）通常 ≥ 当前元素个数（size）。多出来的空间叫「容量冗余」，用于避免频繁扩容。
扩容本身不影响已有元素的随机访问性能，但会触发一次数组复制：
- 旧数组内容被
System.arraycopy拷贝到新数组 - 拷贝完成后，
elementData指向新地址，但后续所有get()仍走相同计算逻辑 - 所以「扩容」是写操作的代价，和读操作无关
用 get() 时哪些操作会悄悄拖慢速度？
表面上 get() 很快，但以下情况会让它变慢，且容易被忽略：
- 发生 GC 时，如果
elementData被移动（比如 G1 的 Region 整理），JVM 会更新数组引用，但下次get()前需重新定位——这种延迟极小，但真实存在 - 大量使用
get(i)遍历，却没用增强 for 或迭代器：JIT 虽能优化，但手动下标访问可能错过逃逸分析带来的栈上分配机会 - 在高并发场景误用非线程安全的
ArrayList：没有锁，但若其他线程正在add()触发扩容，elementData引用可能被修改，此时get()可能读到旧数组（未同步）或抛ArrayIndexOutOfBoundsException
替代方案：什么时候不该依赖这个优势？
如果你的访问模式不是「稳定下标查值」，而是：
- 频繁按值查找（
indexOf()、contains()）→ 应考虑HashSet - 需要在中间反复插入/删除 →
ArrayList的add(int, E)和remove(int)是 O(n)，位移成本远高于随机访问收益 - 元素极大（如大 byte[]）且只读少量 → 连续内存反而导致 CPU cache line 加载浪费，可考虑对象池或稀疏结构
随机访问优势成立的前提，是「你真正在用下标」，而不是把它当通用容器硬套。
