数组还是链表 90的人选错了数据结构性能差1000倍

修仙引入你用数组存了 100 万条数据要查一条要 1 秒。同样的数据换成哈希表查找只要 0.001 秒。同样的数据同样的 CPU为什么差 1000 倍答案你选错了法器。修仙者斗法有人用剑有人用印有人用镜。不是谁比谁强是法器克制关系。剑克近身印克远程镜克幻术。数据结构也一样——数组、链表、哈希表、树、图没有谁绝对强只有谁对场景。数据结构和算法在码农修仙体系里就是法器和功法。数据结构 法器你拿什么工具去操作数据算法 功法你怎么使用这个工具上一篇我们讲了代码在 CPU 里跑了一圈那是修炼内功让你能感知到计算机的灵气流转。这一篇讲的是筑基期最实在的功夫认识你的法器选对你的法器。这一关过不去给你再好的内功CPU 原理也是空转——你拿储物袋去打近身战能赢才怪。硬核主体一、五大法器总览——数据结构的修仙兵器谱修仙界有几件出名法器数据结构界也有五件常备兵器。看一眼兵器谱后面所有内容都从这里展开法器数据结构存储形态擅长不擅长储物袋数组 (Array)连续内存随机读取 O(1)中间插入删除 O(n)灵链链表 (LinkedList)离散节点指针插入删除 O(1)随机访问 O(n)千机镜哈希表 (HashMap)散列桶链表查找插入 O(1)有序遍历、范围查询灵树树 (Tree/Heap)层次节点排序/最值/优先需要平衡、维护复杂灵阵图 (Graph)节点边关系/路径/网络复杂度高、空间大这张表你必须背下来。筑基期的所有面试、所有工程问题本质都是这五行之间的选择。用一张图看五大法器的关系五大法器关系图文字版储物袋数组O(1) 随机读 / O(n) 插入删灵链链表O(n) 随机读 / O(1) 插入删千机镜哈希表O(1) 查找 / 哈希冲突需处理灵树树BST/HeapO(log n)灵阵图节点边BFS/DFS五大法器没有最强只有最合适。接下来我们一个个拆开看。二、储物袋 vs 灵链——数组与链表的恩怨这一对是数据结构的开山祖师所有高级结构都是它们的变体。2.1 储物袋数组伸手就取慢在挪动底层原理数组在内存中是连续的一段空间。假设数组基地址是1000每个元素占 4 字节那么第 i 个元素的地址就是1000 i * 4。CPU 只要做一次加法和一次乘法就能直接跳到那个位置取数据——这就是 O(1) 随机访问的物理本质。修仙类比储物袋里的灵物紧密排成一列你说第三个手直接伸过去就拿出来但你要在第二个和第三个之间塞一个新灵物后面所有灵物都要往后挪一位——O(n)代码示例# 储物袋数组随机访问 O(1)bag[灵草,灵石,灵剑,灵丹,灵符]print(bag[2])# 灵剑 —— 直接跳到偏移量 2瞬间取出# 中间插入O(n) —— 后面所有灵物都要后移bag.insert(2,灵珠)# 原来 bag[2] 之后的元素全部要后挪一个位置# 1万条数据要搬动9998个耗时线性增长# 用 enumerate 一句话看效果fori,iteminenumerate(bag):print(f第{i}格{item})为什么数组是 Python 列表、Java ArrayList 的底层因为绝大多数场景下按位置取数据是最高频操作——索引访问 O(1) 让你几乎无感知代价。2.2 灵链链表断丝重连慢在寻找底层原理链表的每个节点在内存中离散分布靠指针或引用串起来。每个节点存两样东西数据和指向下一个节点的指针。修仙类比一串灵珠每颗珠子用灵丝穿起珠子可以在不同地方你要第三颗得从第一颗开始数next→next→next——O(n)但你要在第二颗后插入新珠子断开灵丝穿上新珠重连——O(1)代码示例# 灵链链表的手动实现 —— 理解底层classLingZhu:灵珠链表的节点def__init__(self,data):self.datadata# 灵珠里装的灵物self.nextNone# 下一颗灵珠的指针灵丝# 用灵珠串一条灵链headLingZhu(灵草)head.nextLingZhu(灵石)head.next.nextLingZhu(灵剑)# 随机访问第2个O(n) —— 必须从头数nodeheadfor_inrange(2):nodenode.next# 灵丝一节一节递过去print(node.data)# 灵剑# 中间插入O(1) —— 断丝重连new_nodeLingZhu(灵珠)new_node.nexthead.next# 新珠子的灵丝接老珠子head.nextnew_node# 前一颗珠子的灵丝接新珠子# 完事不需要挪动其他珠子2.3 储物袋 vs 灵链——选哪个维度储物袋数组灵链链表内存连续缓存友好离散缓存不友好随机访问O(1) 胜O(n)头部插入O(n)O(1)中间插入O(n)O(1)找到位置后空间开销无额外开销每个节点多一个指针实际应用Python list、Java ArrayList、Go sliceLinux 内核链表、LRU 缓存记忆口诀“读多用袋写多用链。”注意现代编程语言Python list、Java ArrayList的动态数组已经优化了尾部插入——摊销 O(1)。所以实际工程中数组动态数组往往是默认首选。链表的真正优势在头部插入和不需要连续内存的场景比如嵌入式系统、操作系统内核。LeetCode 高频题206 反转链表——面试必考理解了灵链的本质这题就是送分defreverse_linked_list(head):反转灵链让灵丝全部反向prevNonecurrheadwhilecurr:next_nodecurr.next# 1. 先记住下一个节点灵丝不能断curr.nextprev# 2. 当前节点的灵丝反向指prevcurr# 3. prev 前进currnext_node# 4. curr 前进returnprev三步走记后→反指→前进。这四步循环跑完灵链就反过来了。三、千机镜——哈希表的魔法哈希表是最常用的数据结构之一。Python dict、Java HashMap、Go map、C unordered_map全是它。名字不同本质一样。3.1 千机镜的法门修仙类比你对千机镜报一个名字镜面一闪就给你对应的灵物——O(1)镜面背后的灵纹哈希函数决定了名字映射到哪个格子如果两个灵物映射到同一个格子哈希冲突需要把灵物用链子串起来链地址法哈希表 数组 哈希函数 冲突处理3.2 哈希函数把 key 变成数组下标defhash_func(key,size):最简哈希函数取模returnhash(key)%size# 把任意 key 映射到 [0, size) 区间理想情况下每个 key 映射到不同位置查找时算一次哈希、直接跳过去取——O(1)。3.3 哈希冲突两个 key 撞了怎么办实际中哈希函数再好冲突不可避免。两种主流解法解法思路特点链地址法每个格子挂一条链表储物袋→灵链实现简单JDK HashMap 用此法开放地址法冲突了就往后找空位缓存友好但易聚集Java 8 的 HashMap 玄机当链表长度超过 8 且数组长度 ≥ 64链表会转成红黑树灵树把查找复杂度从 O(n) 降到 O(log n)。即便被攻击也慢不到哪去。3.4 为什么是平均 O(1)哈希表的时间复杂度要看情况最好情况没有冲突O(1)平均情况冲突均匀分布O(1)最坏情况所有 key 撞同一个格子O(n)——但好哈希函数能避免负载因子load factor是关键哈希表元素数 / 数组长度。超过 0.75 就要扩容rehash重新分配更大的数组和重算哈希——代价是 O(n)但摊销下来还是 O(1)。3.5 千机镜的弱点千机镜不是万能的不保序——遍历顺序跟插入顺序无关范围查询废——查年龄 20-30 的人要扫整个表最坏 O(n)——哈希函数被攻击时HashDoS空间换时间——空数组也占内存面试经典LRU 缓存 哈希表 双向链表# LRU 缓存的精髓哈希表定位 双向链表维护访问顺序classLRUCache:def__init__(self,capacity):self.capcapacity self.cache{}# 千机镜O(1) 定位# 双向灵链头部最新尾部最旧删除尾部 O(1)defget(self,key):ifkeynotinself.cache:return-1# 移动到头部最近使用returnself.cache[key]defput(self,key,value):ifkeyinself.cache:self.cache[key]valueeliflen(self.cache)self.cap:# 删除最久未使用的尾部self.cache.pop(next(iter(self.cache)))self.cache[key]valueLeetCode 146 必考题理解哈希表 链表组合 真正懂数据结构。四、灵树——树结构的层次之美灵树是数据结构的组织架构图。宗门里有祖师→长老→弟子数据里也有根→枝→叶。4.1 二叉树与 BST二叉树每个节点最多两个子节点左、右。二叉搜索树BST左子树 根 右子树。修仙类比BST 功法分卷上卷基础、中卷进阶、下卷高阶找特定功法从上往下查比当前卷简单往左走难往右走——O(log n)BST 的平衡至关重要。如果插入有序数据1,2,3,4,5BST 会退化成链表——O(n)。所以有了平衡树AVL、红黑树、B 树。4.2 B 树数据库索引的根基MySQL InnoDB 索引底层是B 树。为什么不是二叉树因为磁盘 IO 贵B 树一个节点存多个 key树高度降到 3-4 层百万数据查一条只要 3 次磁盘 IO。这是数据库快的根因。4.3 堆功法修炼塔堆是完全二叉树分大顶堆根最大和小顶堆根最小。修仙类比功法修炼塔每次只能从塔顶根节点取走最强/最弱的功法取出后塔自动调整保持堆序Top K 问题用小顶堆——维护 K 个元素的小顶堆遍历 N 个数据比堆顶大就替换。最终堆里就是 Top K时间 O(N log K)。比排序快 10 倍以上。importheapqdeftop_k(nums,k):求最大的 k 个数 —— 灵树小顶堆法门heap[]# 小顶堆堆顶是最小的fornuminnums:iflen(heap)k:heapq.heappush(heap,num)elifnumheap[0]:# 比堆顶大就替换heapq.heapreplace(heap,num)returnheap4.4 树的递归本质所有树的问题都是递归问题。因为树本身的定义就是递归的——“树 根节点 左子树 右子树”。经典二叉树遍历前序/中序/后序definorder(root):中序遍历左→根→右BST 中序 升序ifnotroot:returninorder(root.left)# 先访左子树print(root.val)# 再访根inorder(root.right)# 最后访右子树练会这五行LeetCode 94/144/145 三连击直接拿下。五、灵阵——图结构的关系网络图是数据结构的终极形态——树是特殊的图链表也是特殊的图。万物皆可图。5.1 图的两大基本元素修仙类比节点Vertex 宗门、山头、人物边Edge 关系贸易、敌对、结盟有向图箭头表示方向“我借钱给他≠他借给我”无向图连线表示双向“互为好友”5.2 BFS 与 DFS图的两种修行算法修仙类比思路应用BFS (广度优先)层层扩散从外围查起用队列一圈一圈往外扩最短路径、社交网络几度好友DFS (深度优先)一条路走到黑用栈或递归一头扎到底拓扑排序、路径搜索、迷宫BFS 代码示例求二叉树最小深度fromcollectionsimportdequedefmin_depth(root):BFS 求灵树最浅深度 —— 层层扩散ifnotroot:return0queuedeque([(root,1)])# (节点, 深度)whilequeue:node,depthqueue.popleft()ifnotnode.leftandnotnode.right:# 第一个到达的叶子returndepth# 就是最浅ifnode.left:queue.append((node.left,depth1))ifnode.right:queue.append((node.right,depth1))DFS 代码示例求岛屿数量LeetCode 200 高频defnum_islands(grid):DFS 沉岛法 —— 把访问过的陆地都淹没ifnotgrid:return0count0foriinrange(len(grid)):forjinrange(len(grid[0])):ifgrid[i][j]1:dfs(grid,i,j)# 找到一座岛DFS 沉没count1returncountdefdfs(grid,i,j):递归淹没相连的陆地if(i0orilen(grid)orj0orjlen(grid[0])orgrid[i][j]!1):returngrid[i][j]0# 标记为已访问dfs(grid,i1,j)# 四个方向dfs(grid,i-1,j)dfs(grid,i,j1)dfs(grid,i,j-1)六、法器选择心法——什么时候用什么这是筑基期最实用的心法。给你一张表遇到场景直接对照场景推荐法器原因按编号访问元素储物袋数组索引 O(1)频繁中间插入删除灵链链表插入 O(1)按 key 快速查找千机镜哈希表查找 O(1)需要保持有序灵树平衡 BST插入查找 O(log n)取最值/优先队列灵树堆取顶 O(1)维护 O(log n)表示网络关系灵阵图表达能力强范围查询B 树/跳表有序 高效区间性能优化的第一步永远是先看你选对数据结构没有。修仙术语对照表修仙术语技术现实本篇详解法器数据结构全篇主线储物袋数组 (Array)§二灵链链表 (LinkedList)§二千机镜哈希表 (HashMap)§三灵树树 (Tree)§四灵阵图 (Graph)§五灵纹哈希函数§三.2灵丝指针 / 引用§二.2灵珠链表节点§二.2法器相克数据结构适用场景§六走火入魔用错数据结构导致性能灾难§六炼法器理解数据结构底层实现全篇功法修炼塔堆 (Heap)§四.3宗门组织架构树形结构§四.1势力关系网图结构§五.1层层扩散BFS 广度优先§五.2一条路走到黑DFS 深度优先§五.2想查全系列术语看 术语词典。突破条件数据结构筑基的六条硬指标逐条对照能默写五大法器数组、链表、哈希表、树、图的时间复杂度表能解释为什么数组能 O(1) 随机访问连续内存偏移计算能手写链表反转LeetCode 206和二叉树中序遍历LeetCode 94能解释哈希冲突的两种解决方案链地址法、开放地址法能用一句话说清 LRU 缓存为什么 哈希表 双向链表拿到一个实际场景能在三秒内选对数据结构最后一条是关键。会背复杂度表是炼气后期能在场景中选对法器才是筑基。多刷 LeetCode多看优秀开源代码的法器选择你的法器直觉会慢慢长出来。六条全勾你的数据结构地基就筑成了。下一步——理解你写的代码在 CPU 里怎么跑已在第5篇讲过以及操作系统这条天道规则下一篇。下期预告 互动下一篇【筑基·07】操作系统是天道规则你的程序运行在一个你不可见的天道法则之上——操作系统。进程调度、内存管理、文件系统这些都是天道定的规矩。你的程序不是跑在 CPU 上的是跑在天道规则里的。现在问你 法器自测给你一个需求——“实时统计最近 100 条用户行为日志”你选哪个法器评论区说出你的思路和法器选择看看跟你同门的有多少 话题你被数据结构选错坑过吗有没有一次线上故障根因就是用错了数据结构评论区聊聊你的走火入魔经历。 关注玄芯散人修炼不迷路。下一篇我们讲天道规则——操作系统。我是玄芯散人带你从炼气修到大乘。本文是「码农修仙传」系列第6篇。关注玄芯散人修炼不迷路。