数组大概是每位编程学习者第一个需要深想一层的数据结构。我带的入门系列写到第四讲时标题就定成了04-数组这个位置有点讲究——前面几讲刚学会变量和循环一到数组立刻要面对连续内存、索引、越界这些真正来自底层的问题。这篇文章就把数组整个拆开它在内存里到底长什么样、增删改查的时间成本为什么差别这么大、多维数组在真实项目里怎么被使用、实战里反复出现的几个大坑以及什么时候该换台改用别的结构。适合刚学到函数和循环、准备系统性入门的同学也适合写了两三年代码但对底层总是糊着一层雾的老手。别嫌它基础数组这一小块能牵出整整一套计算机内存观。1. 在基础系列第04讲里数组为什么是先学会逛再学会住1.1 为什么前几讲一定是变量和循环我带课的时候有个明显感受学员学到第四讲前面已经能把一个变量拿来算数、用 if 判断方向、用 for 循环重复干活。这时候最缺的不是新语法而是把一批数据装在一起的能力。比如写一个学生成绩计算程序五个学生的分数难道要定义 score1、score2、score3、score4、score5 五个变量吗十个呢一百个呢光变量名就够你维护一晚上。数组的出现不是多了一个语法糖而是把不受数量限制地存放一批同类数据变成了现实。更关键的是有了数组循环才真正有了用武之地——因为循环要遍历的东西必须是一个打包好的整体。没有数组的循环只是在原地重复动作有了数组的循环才是在批量处理数据。1.2 数组解决的问题只有一句话把这句话写出来记住它等于记住了数组的一半数组用一块连续的内存按固定大小存放一组元素并通过下标直接访问任意一个元素。拆开看有四个关键词连续、同一类型、大小固定、下标访问。连续决定了性能上限固定大小决定了扩容逻辑下标是访问方式也是后面各种 bug 的温床。很多初学者把数组当成一串数据就完事了其实没抓住要害它本质上是内存空间上的一段契约契约规定第几个格子放什么计算机就能根据起步地址直接算出目标地址不需要挨个去找。这句话在后面学指针、切片、缓冲区时还会反复用到。1.3 从数组到线性表的第一个岔路口在数据结构教科书里数组通常被归为线性表的两种实现之一另一种是链表。线性表描述的是元素之间前后线性的关系数组用连续空间去实现它链表用节点和指针去实现它。栈和队列在工程上经常直接建立在数组之上所以说学透数组等于同时把栈队列的底座打牢了。等后面碰到哈希表时很多同学一脸懵其实哈希表底层往往就是数组 哈希函数数组是所有复合结构的地基。所以我常说第04讲的角色不是讲一个新知识点而是把整栋楼的地基打实。地基是实心的还是空心的后面所有结构都会直接反映出来。2. 从内存布局看数组连续空间与索引寻址的物理真相2.1 连续内存的物理意义像一排固定编号的储物柜拿健身房储物柜打比方最形象。柜子一个挨一个从0号排到 N-1 号每格大小一模一样管理员手里有一张图纸标明这排柜子从哪个地址开始。你要取第 i 格的东西不需要从0号开始挨个开柜门直接用起始地址 i × 单格大小就能算出第 i 格的精确位置一步到位。数组就是这个模型。在进程的内存空间里数组就是一个有固定起始地址的连续区间。这个连续带来两大后果一是随机访问变快任何位置都能直接算出来二是创建数组时必须一次性申请一整块大小合适的空间申请完了就基本锁定这正是数组创建后大小不轻易变的根源。理解了这个后面学动态扩容和稀疏数组都会顺很多。2.2 索引从0开始是偏移量不是序号为什么主流语言里第一个元素的下标都是0而不是更符合人类直觉的1因为底层寻址公式是 base_address index × item_size这个 index 本质上代表偏移量不是序号。如果从1开始公式就得变成 base_address (index−1) × item_size每次寻址都多一次减法CPU 不高兴编译器也要多绕一圈。从0开始牺牲一点人类的仪式感换的是寻址开销的极简化。这个细节也解释了为什么面试官总爱问数组下标为什么从0开始答案就三个字偏移量。等你在项目里做底层缓存、做自定义数据布局时会发现这种偏移量思维到处都是不只是数组一家的事。2.3 一条公式看懂随机访问为什么是 O(1)给一段 C 风格的示意代码其实任何语言底层都差不多// 假设int数组首地址是base每个int占4字节 int value arr[3]; // 底层翻译成: value *(base 3 * 4) // 不管数组里有10个元素还是有1亿个元素 // 都只做一次乘法和一次加法所以数组的随机访问时间复杂度恒为 O(1)。但注意这里快的只是按已知下标取元素不是查找某个值。如果不知道值在哪你只能从头到尾逐个比那是 O(n) 的线性扫描。把这两个概念搅在一起是最常见的性能误区。有些人一听说数组性能好就拿数组做全表查找数据量一大性能断崖式下跌然后反过来骂数组没用。其实不是数组没用是它根本不负责按值找人它能干的是我知道你要找第几个我直接告诉你地址。工具用错位置再好的工具也白搭。3. 增删改查的性能账数组的读写优势来自哪里代价又埋在何处3.1 查询与更新真正的用武之地把数组四个基本操作摆在一起情况一目了然操作是否知道位置时间复杂度原因按索引查询知道O(1)地址直接算出来按索引修改知道O(1)地址直接算出来在指定位置插入知道O(n)后面的元素全部要后移删除指定位置元素知道O(n)后面的元素全部要前移前两行是数组的看家本领。比如游戏引擎一帧要更新几千个粒子的坐标每个粒子都按下标改数据这种场景数组是绝对主力。再比如排行榜功能第5名分数变更直接 arr[4] 新分数一步到位不需要挪动任何其他人。凡是数据规模基本固定、按位置读写特别频繁的场景数组天然就是最优选择硬要换哈希表或链表反而更慢因为你还多付了哈希计算和指针操作的成本。3.2 插入和删除为什么是噩梦看一个具体例子数组是 [1, 2, 3, 4, 5]要在下标0的位置插入0。物理上必须先让1挪到1号位、2挪到2号位、3挪到3号位……最后5挪到5号位再把0放进0号位。插入位置越靠前要搬动的元素越多。平均下来复杂度是 O(n)。删除同理删除末尾是 O(1)因为后面没人需要搬删除开头则要把后面所有元素全部往前挪一步。所以有新手问队列用数组实现出队不就很慢工程上的解法是循环数组用 head、tail 两个指针维护逻辑上的首尾元素搬动变成指针移动浪费的空间也能循环复用。这是后话。你现在只需要记住一条铁律数据如果高频在头部或中间增删数组会把你折磨得欲仙欲死。3.3 动态扩容摊还分析第一课为了不让数组一满就卡死主流语言都提供了动态数组比如 JavaScript 的 Array、Python 的 list、Java 的 ArrayList。它内部本质上还是数组只是在装不下时申请一块更大的新空间把旧元素整体拷贝过去。最常见的策略是翻倍扩容容量从4变88变1616变32。单看某一次扩容成本是 O(n)因为所有元素都要搬一次家但把许多次 push 操作整体看每次普通 push 是 O(1)偶尔一次扩容是 O(n)平均下来每次 push 的成本仍然是常数。这就是摊还复杂度的直觉虽然某一刻会很疼但平均下来不疼。注意扩容倍数不是随便定的翻倍是简单且有效的方案如果懒到每次只加1个容量插入 n 个元素的总代价会退化到 O(n²)这是很多旧代码卡顿的隐性原因。4. 多维数组的现实战场矩阵、图像与表格数据怎么被数组管理4.1 二维数组的内存排布与遍历顺序二维数组可以理解成数组的数组。在真正采用连续内存的语言里一张 3 行 4 列的矩阵内存中就是按行铺开的第一行4个元素、第二行4个元素、第三行4个元素。所以访问 arr[i][j] 时底层地址 base (i × 列数 j) × 元素大小。这个排布方式直接影响遍历性能按行遍历时访问的地址是连续递增的CPU 缓存命中率很高按列遍历时每次都要跳过一整行缓存频繁失效。我早年用同样大小的矩阵做过测试行优先遍历比列优先遍历有时能快出三四倍。这个差距在图像处理、矩阵运算里会被放大得非常明显因为你处理的可是千万级元素。4.2 实战案例图像灰度矩阵的读取与翻转图像在内存里最常见的形态就是二维数组或像素缓冲区。举个例子一张 8 位灰度图读进来后每个像素就是一个 0 到 255 的整数整张图就是一个 height 行 width 列的二维数组。要做水平翻转本质就是每一行内部对称交换// 假设grayscale是height行width列的二维数组 function flipHorizontal(grayscale) { const height grayscale.length; const width grayscale[0].length; for (let i 0; i height; i) { for (let j 0; j width / 2; j) { const mirror width - 1 - j; [grayscale[i][j], grayscale[i][mirror]] [grayscale[i][mirror], grayscale[i][j]]; } } }你看一旦把图像看成二维数组翻转、裁剪、缩放这些操作就都变成了下标的计算问题。这个思路在很多图像算法里反复出现。顺便提醒一个坑灰度值合法范围是0到255计算翻转时如果下标写错越界后图像会出现一条莫名其妙的亮线或暗线视觉上还特别难发现比报错揪心多了。4.3 表格数据的扁平化处理日常开发里Excel 导入、CSV 解析、数据库查询结果大部分都能看成二维表格。有时候为了传参方便或者做矩阵运算需要把二维拉成一维。很多新手拉平表格时容易忽略一个现实每一行长度未必完全一致不能用每行固定列数的假设去硬算下标。用 JavaScript 示范const matrix [[1, 2], [3, 4, 5], [6]]; const flat matrix.flat(); console.log(flat); // [1, 2, 3, 4, 5, 6]二维下标映射到一维的公式是 index row × 每行列数 col。反过来也要记住当你拿到一个一维数组和一个列数 colCount你可以随时推算出它对应的行列位置。把二维是人类视角一维是内存视角这个观念建立起来很多数据处理上的困惑会自己消散。做存储、做序列化、做底层传输时大家都在二维和一维之间来回换算数组就是那个换算的源头。5. 数组实战的坑位清单越界、拷贝、初始化与索引错位5.1 越界访问编译器和运行时都救不了你数组最著名的坑是越界访问。C 语言里 arr[10] 这种访问不会报编译错误运行起来直接读数组后面的未知内存区域返回一堆垃圾值程序往往在很久以后才莫名崩溃。我见过一个实验课上的例子某同学把数组下标写成了循环变量数据量小的时候碰巧没事数据量一大就偶发异常排查了两天才发现是少写了一个边界条件。哪怕在会抛异常的现代语言里越界也只是从读垃圾值变成了抛异常逻辑上的边界错误照样防不住。经验法则只有两条涉及数组索引的循环统一写成 i length别写 i length倒序遍历时写 i 0别让它一路走到 -1。5.2 拷贝陷阱以为复制了其实还在共享数组是引用类型直接赋值只是复制了地址并没有复制数据。无数人在这里第一次翻车const a [1, 2, 3]; const b a; // b和a指向同一个数组 b[0] 99; console.log(a[0]); // 输出99a也被改了要真正拷贝可以用 a.slice()、[...a] 或者 concat。但注意这些方法做的都是浅拷贝如果数组里装的是嵌套数组或者对象内层元素仍然是共享的。判断逻辑很简单只装数字、字符串这些基本类型的数组浅拷贝够用装着对象或嵌套数组的必须做深拷贝或者逐层展开。Python 里也一样a[:] 和 copy() 都是浅拷贝嵌套列表照样会联动。这个问题我几乎在每个项目评审里都会见到特别是做缓存、做快照、做撤销功能时浅拷贝导致的数据错乱能让你怀疑人生。5.3 初始化与索引错位热烈欢迎凌晨三点的bug初始化也有三种常见坑。第一空数组里想用固定下标直接赋值比如先声明一个空数组再去设置 arr[5]中间的 arr[0] 到 arr[4] 全是 undefined不是你想象中的默认0。第二创建全是0的二维数组很容易写出嵌套引用复用结果每一行其实是同一个数组改一行变全图联动。这个错误已经坑了十几届学生了解决方案是每一行都单独初始化。第三删除元素时索引会自动前移继续用旧下标会莫名跳过元素const arr [10, 20, 30, 40, 50]; for (let i 0; i arr.length; i) { if (arr[i] % 20 0) { arr.splice(i, 1); // 删除时后面的元素前移i却已经自增 } } console.log(arr); // 你以为删掉了20和40实际结果是 [10, 30, 50]? 并不是30被跳过了实际跑一下就知道了删掉20时30、40、50整体前移循环变量继续往后走下次比较的是4030被漏掉了。正确处理是倒序遍历删除或者用 filter 生成新数组。像这种索引错位问题写业务代码时几乎天天碰到。经验就一句话在数组里做删除优先倒序遍历别用正序遍历硬扛。6. 什么时候别再硬用数组与链表和哈希表的选型对比6.1 选型的三把尺子读写比、增减频度、内存结构做结构选型不用背一堆理论先问自己三个问题。第一数据是按位置读得多还是按值查找得多按位置读、下标固定数组天下无敌按值查找且数据量大数组 O(n) 的线性扫描会很吃力。第二数据是不是频繁在头部或中间插入删除如果是高频增删链表可能更合适因为改指针是 O(1)但代价是链表随机访问变成 O(n)不可能两头好处都占。第三数据规模是固定的还是持续膨胀的数据一旦定长且量大数组优势格外明显如果完全不可控动态数组或哈希结构则要谨慎评估扩容代价。三把尺子量下来选型基本不会离谱。6.2 数组、链表、哈希表的对比清单维度数组/动态数组链表哈希表按索引读取O(1)O(n)不适用键而不是索引按值查找O(n)O(n)平均O(1)头部插入O(n)O(1)平均O(1)中间插入O(n)O(1)已知前驱节点平均O(1)尾部插入均摊O(1)O(n)不带尾指针时平均O(1)内存布局连续空间分散节点桶数组加节点这张表不能解决所有问题但能解决一大半为什么我的代码这么慢的困惑。最常见的反模式用户量很大又需要按用户ID频繁查找结果用数组存用户列表每次查找都线性扫一遍人越多响应越慢。换成哈希表之后查询时间几乎不随数据量增长。反过来有些人迷信哈希表快拿它去存一个固定10个元素的坐标列表遍历时还要算哈希、处理冲突反倒不如数组直接。工具没有绝对的好只看匹配不匹配。6.3 哈希表底层也是数组复合结构的世界观一个容易被忽略的事实是哈希表通常就是数组 哈希函数。key 经过哈希得到一个整数下标落到一个桶数组里冲突再靠拉链等手段解决。表面上看数组和哈希表是两个分支但底层数组仍然是地基。同样栈和队列用数组实现起来非常自然优先队列用数组当堆的载体布隆过滤器本质上也是用位数组去标记存在与否。把这些串起来看你会发现数组不是数据结构里的一颗孤星而是很多复杂结构的建筑材料。这也是为什么我总劝刚入门的同学宁可多花一晚上把数组的连续内存、索引寻址、拷贝陷阱彻底搞明白也别急着背十个名词。地基不牢后面每一层都会摇摇晃晃。我个人写代码这些年最有价值的习惯之一就是在决定用哪种结构之前问自己一句接下来我最高频的操作是什么如果是按下标读那我闭着眼选数组如果是头部频繁增删我老老实实考虑链表或队列如果是按键查人那就果断上哈希表。还有一个小技巧想分享给后面学到这一课的同学数组相关的 bug 九成以上集中在下标和边界上调试时先在关键位置把 i、j、length 这几个值打印出来很多时候答案一眼就跳出来了。别嫌数组简单越简单的东西越需要想得深这也是04-数组这一讲值得反复打磨的原因。
