数组的随机访问为什么是 O(1)？下标是怎么定位到元素的？

简化版

因为数组是一整块连续内存，且每个元素大小相同，所以第 i 个元素的地址可以直接用公式算出来：地址 = 首地址 + i × 元素大小。一步乘加就定位，不用遍历，所以随机访问是 O(1)。

详细版

数组随机访问 O(1) 靠两个前提：

1. 内存连续：整个数组占用一段连续的地址空间，从首地址开始一个挨一个排。
2. 元素等长：每个元素占用固定字节数（int 4 字节、long 8 字节…）。

有了这两点，访问 arr[i] 时，CPU 不需要从头找，而是直接计算：

addr(arr[i]) = base_address + i × element_size

比如 int[] a，首地址 0x1000，int 占 4 字节，那么 a[3] 的地址就是 0x1000 + 3×4 = 0x100C，一次算术运算搞定，与数组多大、i 多大都无关，恒定时间。

这也解释了为什么数组下标从 0 开始：下标本质是「相对首地址的偏移量」，第 0 个元素偏移 0，公式最简洁，不用每次多做一次 -1。

完整版教学

一、随机访问 vs 顺序访问

• 随机访问（Random Access）：不管访问第几个元素，代价都一样（O(1)），可以「随便跳」。数组就是随机访问的代表。
• 顺序访问（Sequential Access）：只能从头一个一个走，想到第 k 个得先经过前 k-1 个。链表就是典型，访问第 k 个是 O(k)。

数组能做到随机访问，正是因为「地址可计算」；链表节点内存分散、地址不可预测，只能顺着指针走，所以做不到。

二、寻址公式的推导

设数组首地址为 base，每个元素占 size 字节。第 0 个元素放在 base，第 1 个放在 base + size，第 2 个放在 base + 2×size……第 i 个自然就在：

base + i × size

这是一个乘法加一个加法，是常数次运算，所以 O(1)。CPU 甚至有专门的寻址模式（base + index × scale）来一条指令完成，非常快。

三、为什么下标从 0 而不是 1

如果下标从 1 开始，寻址公式要写成 base + (i-1) × size，每次访问都多一次减法。从 0 开始时公式是最干净的 base + i × size，偏移量和下标直接对应。这是 C 语言等把下标定为「从 0 开始」的底层原因——下标就是偏移量。

四、连续内存带来的额外好处：缓存友好

除了 O(1) 寻址，连续内存还有个隐藏优势：CPU 缓存预取。访问 a[i] 时，CPU 会把它附近的一整块（缓存行）也加载进缓存，于是接着访问 a[i+1]、a[i+2] 时直接命中缓存，飞快。这就是为什么遍历数组通常比遍历链表快很多——即使复杂度相同，数组对缓存更友好。

五、代价：这份「连续」不是白来的

O(1) 随机访问的代价是「必须连续」，于是：

• 长度固定，扩容要重新申请连续大块内存并拷贝。
• 中间插入/删除要搬移后续元素（O(n)），因为要维持连续。

数组是拿「增删灵活性」换来了「随机访问和缓存友好」，链表则是反过来。

结构	访问第 k 个元素	原因
数组	O(1)	连续存储，元素大小固定，可直接算地址
链表	O(n)	只能从头沿指针走到第 k 个
哈希表	平均 O(1) 按 key 查找	靠哈希定位桶，不是按下标地址计算

具体算一次：假设 int[] a 的起始地址是 0x1000，一个 int 占 4 字节，那么 a[100] 的地址是 0x1000 + 100 * 4 = 0x1190。CPU 不需要看 a[0] 到 a[99] 的值，只要做一次地址计算即可。

六、常见误区与追问

• 误区：数组查找元素一定是 O(1)。 按下标访问是 O(1)，按值查找例如找值 42 仍要遍历，通常是 O(n)。
• 误区：随机访问表示访问顺序随机。 这里的“随机”是指可以直接访问任意下标，不依赖前一个元素。
• 误区：所有语言的二维数组都一定连续。 C 的二维数组通常按行连续，Java 的 int[][] 是数组的数组，每一行是独立对象。
• 追问：为什么数组下标通常从 0 开始？ 因为第 0 个元素偏移量就是 0，地址公式可直接写成 base + i * size。
• 追问：数组越界为什么危险？ 越界下标会算出不属于该数组的地址；安全语言会检查并抛异常，C/C++ 则可能产生未定义行为。
• 追问：O(1) 是否代表耗时完全一样？ 不是，O(1) 表示不随 n 增长；不同层级缓存命中、内存位置仍会影响常数时间。

七、加强记忆

数组随机访问 O(1)，是因为内存连续 + 元素等长，第 i 个元素地址可直接用 首地址 + i × 元素大小 算出，一步到位、不用遍历。下标从 0 开始正是因为它就是「相对首地址的偏移量」。连续内存还顺带带来缓存友好，代价是长度固定、中间增删要搬移。