【筑基·06】数据结构就是功法

码农修仙传 · 筑基期 · 第6篇 我是玄芯散人，带你从炼气修到大乘。

境界标识

╔══════════════════════════════════╗
║     筑基期 · 第6篇               ║
║     数据结构就是功法              ║
║     预计阅读：10分钟              ║
╚══════════════════════════════════╝

修仙引入

你用数组存了 100 万条数据，要查一条要 1 秒。同样的数据换成哈希表，查找只要 0.001 秒。同样的数据，同样的 CPU，为什么差 1000 倍？

答案：你选错了法器。

修仙者斗法，有人用剑，有人用印，有人用镜。不是谁比谁强，是法器克制关系。剑克近身，印克远程，镜克幻术。数据结构也一样——数组、链表、哈希表、树、图，没有谁绝对强，只有谁对场景。

数据结构和算法，在码农修仙体系里就是法器和功法。

数据结构 = 法器：你拿什么工具去操作数据
算法 = 功法：你怎么使用这个工具

上一篇我们讲了"代码在 CPU 里跑了一圈"，那是修炼内功，让你能感知到计算机的灵气流转。这一篇讲的是筑基期最实在的功夫：认识你的法器，选对你的法器。

这一关过不去，给你再好的内功（CPU 原理）也是空转——你拿储物袋去打近身战，能赢才怪。

硬核主体

一、五大法器总览——数据结构的修仙兵器谱

修仙界有几件出名法器，数据结构界也有五件常备兵器。看一眼兵器谱，后面所有内容都从这里展开：

法器	数据结构	存储形态	擅长	不擅长
储物袋	数组 (Array)	连续内存	随机读取 O(1)	中间插入删除 O(n)
灵链	链表 (LinkedList)	离散节点+指针	插入删除 O(1)	随机访问 O(n)
千机镜	哈希表 (HashMap)	散列桶+链表	查找插入 O(1)	有序遍历、范围查询
灵树	树 (Tree/Heap)	层次节点	排序/最值/优先	需要平衡、维护复杂
灵阵	图 (Graph)	节点+边	关系/路径/网络	复杂度高、空间大

这张表你必须背下来。筑基期的所有面试、所有工程问题，本质都是这五行之间的选择。

用一张图看五大法器的关系：

五大法器，没有最强，只有最合适。接下来我们一个个拆开看。

二、储物袋 vs 灵链——数组与链表的恩怨

这一对是数据结构的"开山祖师"，所有高级结构都是它们的变体。

2.1 储物袋（数组）：伸手就取，慢在挪动

底层原理： 数组在内存中是连续的一段空间。假设数组基地址是 1000，每个元素占 4 字节，那么第 i 个元素的地址就是 1000 + i * 4。CPU 只要做一次加法和一次乘法，就能直接跳到那个位置取数据——这就是 O(1) 随机访问的物理本质。

修仙类比：

储物袋里的灵物紧密排成一列
你说"第三个"，手直接伸过去就拿出来
但你要在第二个和第三个之间塞一个新灵物，后面所有灵物都要往后挪一位——O(n)

代码示例：

python

# 储物袋（数组）：随机访问 O(1)
bag = ["灵草", "灵石", "灵剑", "灵丹", "灵符"]
print(bag[2])  # "灵剑" —— 直接跳到偏移量 2，瞬间取出

# 中间插入：O(n) —— 后面所有灵物都要后移
bag.insert(2, "灵珠")
# 原来 bag[2] 之后的元素全部要后挪一个位置
# 1万条数据，要搬动9998个，耗时线性增长

# 用 enumerate 一句话看效果
for i, item in enumerate(bag):
    print(f"第{i}格：{item}")

为什么数组是 Python 列表、Java ArrayList 的底层？ 因为绝大多数场景下，"按位置取数据"是最高频操作——索引访问 O(1) 让你几乎无感知代价。

2.2 灵链（链表）：断丝重连，慢在寻找

底层原理： 链表的每个节点在内存中离散分布，靠"指针"（或引用）串起来。每个节点存两样东西：数据和指向下一个节点的指针。

修仙类比：

一串灵珠，每颗珠子用灵丝穿起，珠子可以在不同地方
你要第三颗？得从第一颗开始数（next→next→next）——O(n)
但你要在第二颗后插入新珠子？断开灵丝，穿上新珠，重连——O(1)

代码示例：

python

# 灵链（链表）的手动实现 —— 理解底层
class LingZhu:
    """灵珠：链表的节点"""
    def __init__(self, data):
        self.data = data        # 灵珠里装的灵物
        self.next = None        # 下一颗灵珠的指针（灵丝）

# 用灵珠串一条灵链
head = LingZhu("灵草")
head.next = LingZhu("灵石")
head.next.next = LingZhu("灵剑")

# 随机访问第2个：O(n) —— 必须从头数
node = head
for _ in range(2):
    node = node.next  # 灵丝一节一节递过去
print(node.data)  # "灵剑"

# 中间插入：O(1) —— 断丝重连
new_node = LingZhu("灵珠")
new_node.next = head.next  # 新珠子的灵丝接老珠子
head.next = new_node       # 前一颗珠子的灵丝接新珠子
# 完事！不需要挪动其他珠子

2.3 储物袋 vs 灵链——选哪个？

维度	储物袋（数组）	灵链（链表）
内存	连续，缓存友好	离散，缓存不友好
随机访问	O(1) 胜	O(n)
头部插入	O(n)	O(1) 胜
中间插入	O(n)	O(1)（找到位置后）
空间开销	无额外开销	每个节点多一个指针
实际应用	Python list、Java ArrayList、Go slice	Linux 内核链表、LRU 缓存

记忆口诀："读多用袋，写多用链。"

注意：现代编程语言（Python list、Java ArrayList）的"动态数组"已经优化了尾部插入——摊销 O(1)。所以实际工程中数组（动态数组）往往是默认首选。链表的真正优势在头部插入和不需要连续内存的场景（比如嵌入式系统、操作系统内核）。

LeetCode 高频题：206 反转链表——面试必考，理解了灵链的本质这题就是送分：

python

def reverse_linked_list(head):
    """反转灵链：让灵丝全部反向"""
    prev = None
    curr = head
    while curr:
        next_node = curr.next  # 1. 先记住下一个节点（灵丝不能断）
        curr.next = prev       # 2. 当前节点的灵丝反向指
        prev = curr            # 3. prev 前进
        curr = next_node       # 4. curr 前进
    return prev

三步走：记后→反指→前进。这四步循环跑完，灵链就反过来了。

三、千机镜——哈希表的魔法

哈希表是最常用的数据结构之一。Python dict、Java HashMap、Go map、C++ unordered_map，全是它。名字不同，本质一样。

3.1 千机镜的法门

修仙类比：

你对千机镜报一个名字，镜面一闪就给你对应的灵物——O(1)
镜面背后的灵纹（哈希函数）决定了"名字"映射到哪个格子
如果两个灵物映射到同一个格子（哈希冲突），需要把灵物用链子串起来（链地址法）

哈希表 = 数组 + 哈希函数 + 冲突处理

3.2 哈希函数：把 key 变成数组下标

python

def hash_func(key, size):
    """最简哈希函数：取模"""
    return hash(key) % size  # 把任意 key 映射到 [0, size) 区间

理想情况下，每个 key 映射到不同位置，查找时算一次哈希、直接跳过去取——O(1)。

3.3 哈希冲突：两个 key 撞了怎么办？

实际中哈希函数再好，冲突不可避免。两种主流解法：

解法	思路	特点
链地址法	每个格子挂一条链表（储物袋→灵链）	实现简单，JDK HashMap 用此法
开放地址法	冲突了就往后找空位	缓存友好，但易聚集

Java 8 的 HashMap 玄机：当链表长度超过 8 且数组长度 ≥ 64，链表会转成红黑树（灵树），把查找复杂度从 O(n) 降到 O(log n)。这就是为什么 HashMap 即使被攻击也慢不到哪去。

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 缓存 = 哈希表 + 双向链表

python

# LRU 缓存的精髓：哈希表定位 + 双向链表维护访问顺序
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # 千机镜：O(1) 定位
        # 双向灵链：头部最新，尾部最旧，删除尾部 O(1)

    def get(self, key):
        if key not in self.cache:
            return -1
        # 移动到头部（最近使用）
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache[key] = value
        elif len(self.cache) >= self.cap:
            # 删除最久未使用的（尾部）
            self.cache.pop(next(iter(self.cache)))
        self.cache[key] = value

LeetCode 146 必考题，理解哈希表 + 链表组合 = 真正懂数据结构。

四、灵树——树结构的层次之美

灵树是数据结构的"组织架构图"。宗门里有祖师→长老→弟子，数据里也有根→枝→叶。

4.1 二叉树与 BST

二叉树：每个节点最多两个子节点（左、右）。二叉搜索树 (BST)：左子树 < 根 < 右子树。

修仙类比：

BST = 功法分卷：上卷基础、中卷进阶、下卷高阶
找特定功法：从上往下查，比当前卷简单往左走，难往右走——O(log n)

BST 的平衡至关重要。如果插入有序数据（1,2,3,4,5），BST 会退化成链表——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 倍以上。

python

import heapq

def top_k(nums, k):
    """求最大的 k 个数 —— 灵树（小顶堆）法门"""
    heap = []  # 小顶堆：堆顶是最小的
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:  # 比堆顶大就替换
            heapq.heapreplace(heap, num)
    return heap

4.4 树的递归本质

所有树的问题，都是递归问题。 因为树本身的定义就是递归的——"树 = 根节点 + 左子树 + 右子树"。

经典：二叉树遍历（前序/中序/后序）：

python

def inorder(root):
    """中序遍历：左→根→右，BST 中序 = 升序"""
    if not root:
        return
    inorder(root.left)    # 先访左子树
    print(root.val)       # 再访根
    inorder(root.right)   # 最后访右子树

练会这五行，LeetCode 94/144/145 三连击直接拿下。

五、灵阵——图结构的关系网络

图是数据结构的终极形态——树是特殊的图，链表也是特殊的图。万物皆可图。

5.1 图的两大基本元素

修仙类比：

节点 (Vertex) = 宗门、山头、人物
边 (Edge) = 关系：贸易、敌对、结盟
有向图：箭头表示方向（"我借钱给他"≠"他借给我"）
无向图：连线表示双向（"互为好友"）

5.2 BFS 与 DFS：图的两种修行

算法	修仙类比	思路	应用
BFS (广度优先)	层层扩散，从外围查起	用队列，一圈一圈往外扩	最短路径、社交网络"几度好友"
DFS (深度优先)	一条路走到黑	用栈（或递归），一头扎到底	拓扑排序、路径搜索、迷宫

BFS 代码示例（求二叉树最小深度）：

python

from collections import deque

def min_depth(root):
    """BFS 求灵树最浅深度 —— 层层扩散"""
    if not root:
        return 0
    queue = deque([(root, 1)])  # (节点, 深度)
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:  # 第一个到达的叶子
            return depth                       # 就是最浅
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

DFS 代码示例（求岛屿数量，LeetCode 200 高频）：

python

def num_islands(grid):
    """DFS 沉岛法 —— 把访问过的陆地都淹没"""
    if not grid:
        return 0
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(grid, i, j)  # 找到一座岛，DFS 沉没
                count += 1
    return count

def dfs(grid, i, j):
    """递归淹没相连的陆地"""
    if (i < 0 or i >= len(grid) or
        j < 0 or j >= len(grid[0]) or
        grid[i][j] != '1'):
        return
    grid[i][j] = '0'  # 标记为已访问
    dfs(grid, i+1, j)  # 四个方向
    dfs(grid, i-1, j)
    dfs(grid, i, j+1)
    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篇。系列导航见 xren.ren

【筑基·06】数据结构就是功法 ​

境界标识 ​

修仙引入 ​

硬核主体 ​

一、五大法器总览——数据结构的修仙兵器谱 ​

二、储物袋 vs 灵链——数组与链表的恩怨 ​

2.1 储物袋（数组）：伸手就取，慢在挪动 ​

2.2 灵链（链表）：断丝重连，慢在寻找 ​

2.3 储物袋 vs 灵链——选哪个？ ​

三、千机镜——哈希表的魔法 ​

3.1 千机镜的法门 ​

3.2 哈希函数：把 key 变成数组下标 ​

3.3 哈希冲突：两个 key 撞了怎么办？ ​

3.4 为什么是平均 O(1)？ ​

3.5 千机镜的弱点 ​

四、灵树——树结构的层次之美 ​

4.1 二叉树与 BST ​

4.2 B+ 树：数据库索引的根基 ​

4.3 堆：功法修炼塔 ​

4.4 树的递归本质 ​

五、灵阵——图结构的关系网络 ​

5.1 图的两大基本元素 ​

5.2 BFS 与 DFS：图的两种修行 ​

六、法器选择心法——什么时候用什么 ​

修仙术语对照表 ​

突破条件 ​

下期预告 + 互动 ​

【筑基·06】数据结构就是功法

境界标识

修仙引入

硬核主体

一、五大法器总览——数据结构的修仙兵器谱

二、储物袋 vs 灵链——数组与链表的恩怨

2.1 储物袋（数组）：伸手就取，慢在挪动

2.2 灵链（链表）：断丝重连，慢在寻找

2.3 储物袋 vs 灵链——选哪个？

三、千机镜——哈希表的魔法

3.1 千机镜的法门

3.2 哈希函数：把 key 变成数组下标

3.3 哈希冲突：两个 key 撞了怎么办？

3.4 为什么是平均 O(1)？

3.5 千机镜的弱点

四、灵树——树结构的层次之美

4.1 二叉树与 BST

4.2 B+ 树：数据库索引的根基

4.3 堆：功法修炼塔

4.4 树的递归本质

五、灵阵——图结构的关系网络

5.1 图的两大基本元素

5.2 BFS 与 DFS：图的两种修行

六、法器选择心法——什么时候用什么

修仙术语对照表

突破条件

下期预告 + 互动