数组能实现O(1)索引访问，根本原因是内存连续存储与地址公式base + i × size的硬件级直接计算，CPU单周期完成定位，无需遍历、比较或跳转。

数组能实现 O(1) 索引访问，根本原因不是算法多巧妙，而是内存连续 + 地址公式硬编码——CPU 一步算出地址，直接取值，不查、不跳、不循环。

连续内存是 O(1) 的物理基础

数组在内存中必须是一整块紧挨着的空间。比如一个 int 数组，每个元素占 4 字节，那么：

• A[0] 在地址 0x1000
• A[1] 在地址 0x1004（0x1000 + 1 × 4）
• A[2] 在地址 0x1008（0x1000 + 2 × 4）

这种等距排列让“第几个”和“在哪儿”之间形成确定的数学关系。一旦内存不连续（如链表），就只能靠指针逐个跳转，时间自然变成 O(n)。

地址公式：一次乘加搞定定位

给定首地址 base、索引 i、单个元素字节数 size，目标地址就是：

base + i × size

这个计算由 CPU 的地址生成单元（AGU）在单个时钟周期内完成。无论 i 是 5 还是 500000，运算步骤数恒定。这就是 O(1) 的硬件级保障。

注意：这是按 下标 访问，不是按 值 查找。按值搜索仍需遍历，复杂度是 O(n)。

栈上数组和堆上数组访问速度一样快

函数内定义的局部数组（栈分配）和 new/malloc 分配的数组（堆分配），只要内存块本身连续，地址计算逻辑完全一致。CPU 只认起始地址 + 偏移量，不管这块内存来自栈还是堆。

区别只在分配/释放方式，不影响运行时的访问行为。

为什么不能只靠数组实现所有 O(1) 操作

数组虽有 O(1) 随机访问，但插入/删除中间元素要移动后续数据，时间复杂度是 O(n)。而哈希表支持 O(1) 插入删除，却无法用索引随机访问。

典型解法是组合使用：

• 用数组存元素，支撑 getRandom() 的 O(1) 随机访问
• 用哈希表记录 “值 → 数组索引”，支撑 insert/remove 的 O(1) 定位与判断
• 删除时用“末尾元素覆盖待删位置 + 更新映射”避免搬移，保持 O(1)

这种结构正是 LeetCode 380 题 RandomizedSet 的核心设计思路。