二维数组在内存中是如何存储和寻址的？

简化版

内存本身是一维的，二维数组要「压平」成一维来存。主流语言（C、Java、Python）用行优先（row-major）：一行存完接着存下一行。元素 a[i][j] 的地址 = 首地址 + (i × 列数 + j) × 元素大小。所以按行遍历比按列遍历快——按行遍历访问的是连续内存，缓存命中率高。

详细版

二维数组逻辑上是「行 × 列」的表格，但物理内存是一条线，必须按某种顺序展开：

行优先（Row-major）：a[0][0], a[0][1], …, a[0][n-1], a[1][0], …，一行接一行。C/C++、Java（一维展开时）、Python NumPy 默认都是它。
列优先（Column-major）：一列接一列存。Fortran、MATLAB、R 用它。

行优先下，a[i][j]（共 cols 列，元素大小 size）的地址：

addr = base + (i × cols + j) × size

这也是一个乘加公式，所以二维数组的随机访问同样是 O(1)。

注意 Java 的特殊性：Java 的「二维数组」其实是「数组的数组」——int[][] 是一个存着若干个一维数组引用的数组，每一行是独立对象、内存不一定连续，可以是「锯齿数组」（每行长度不同）。而 C 的 int a[3][4] 是真正连续的一整块。

完整版教学

一、为什么要「行优先/列优先」

物理内存是一维线性地址空间，而二维数组是二维的，中间必须有一套「二维坐标 → 一维偏移」的映射规则。行优先和列优先就是两种映射约定，区别只在于「先把行铺平，还是先把列铺平」。选哪种是语言设计的历史选择，本身没有优劣，但用的时候要顺着它的方向遍历才快。

二、行优先寻址公式的推导

假设数组 m 行 n 列，行优先存储。第 i 行前面有 i 行，每行 n 个元素，所以第 i 行第一个元素前面有 i × n 个元素；再往后数 j 个就到 a[i][j]。所以它相对首地址的偏移是 (i × n + j) 个元素，乘以元素大小 size：

addr(a[i][j]) = base + (i × n + j) × size

列优先则是 base + (j × m + i) × size。

三、遍历顺序为什么影响性能（缓存）

行优先存储下，a[i][0], a[i][1], a[i][2]… 在内存里是紧挨着的。所以：

// 快：按行遍历，顺着内存走，缓存命中率高
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        sum += a[i][j];

// 慢：按列遍历，每次跨一整行的距离跳，频繁 cache miss
for (int j = 0; j < n; j++)
    for (int i = 0; i < m; i++)
        sum += a[i][j];

两段代码复杂度都是 O(m×n)，但第一段能显著更快，因为它访问连续内存、充分利用了 CPU 缓存预取。这是「复杂度相同、常数不同」的经典例子。

四、Java 的「数组的数组」

C 里 int a[3][4] 是一整块 48 字节连续内存。而 Java 的 int[][] a = new int[3][4] 实际上是：一个长度 3 的数组，每个元素是一个指向「长度 4 的一维数组」的引用。这带来两点不同：

各行是独立对象，内存不保证连续，缓存优势不如 C 的真二维数组。
支持锯齿数组（jagged array）：a[0] 可以长度 4、a[1] 长度 2，每行不等长。

五、实战怎么用

遍历二维数组时让内层循环走连续维度（行优先就内层遍历列），提升缓存命中。
大矩阵运算（图像、科学计算）尤其要注意访问顺序，行列遍历顺序错了可能慢好几倍。

表示方式	内存特点	下标换算/访问特点
C 行优先二维数组	整块连续内存	`addr = base + (i * cols + j) * size`
Fortran/Matlab 列优先数组	整块连续内存	同一列相邻，列遍历更友好
Java `int[][]`	外层数组保存每行引用	每一行可以是不同对象，甚至长度不同

数字例子：int a[1000][1000] 若按行优先存储，一行有 1000 个 int，约 4000 字节。按行遍历时相邻访问地址只差 4 字节；按列遍历时连续两次访问可能相差 4000 字节，更容易浪费缓存。

二维数组题不要只说“矩阵”。面试官通常想听到：行优先/列优先、地址公式、遍历顺序对缓存的影响，以及 Java 这种“数组的数组”的特殊性。

六、常见误区与追问

误区：二维数组一定是二维空间里分散存的。 许多语言会把它线性铺到一维连续内存中，只是通过下标公式模拟二维。
误区：a[i][j] 和 a[j][i] 成本总是一样。 单次访问复杂度一样，但批量遍历时是否连续会影响缓存命中率。
误区：Java 的 int[][] 和 C 的 int[][] 内存模型完全一样。 Java 外层存行引用，每一行是独立数组；C 的固定二维数组通常是一整块连续空间。
追问：行优先里 a[i][j] 地址怎么算？ 若列数为 cols，元素大小为 size，地址是 base + (i * cols + j) * size。
追问：为什么循环顺序会影响性能？ 内层循环如果访问连续地址，CPU 缓存和预取更有效；跳列访问可能频繁跨缓存行。
追问：矩阵转置为什么常影响局部性？ 转置会把原来的行访问变成列访问，若处理不当就会从连续访问变成大步长跳跃。

七、加强记忆

内存是一维的，二维数组要按行优先（C/Java/Python，一行接一行）或列优先（Fortran/MATLAB）压平。行优先下 a[i][j] 地址 = 首地址 + (i×列数 + j)×元素大小，随机访问仍 O(1)。按存储方向遍历（行优先就按行）能命中缓存、快得多。Java 的 int[][] 是「数组的数组」，各行独立、可锯齿、内存未必连续。

简化版

详细版