元数据卡
- 前置知识：数组、链表、哈希表、二叉搜索树
- 预计时间：35 分钟
- 核心难度：进阶
- 完成标志：理解四种高级数据结构的核心思想和典型应用场景
你的进度
你站在算法森林的尽头。基础数据结构你都会了，但遇到千万级数据时，散列表的范围查询是永远的痛。这一章给你四把钥匙：布隆过滤器、并查集、线段树、Trie。四个专题独立，可按需跳跃学习。
布隆过滤器——想找的东西大概率不存在
100 万条禁入名单，查一个人名。哈希表内存太大。布隆过滤器能确定说"不在"，说"在"时可能误报。
核心： k 个哈希函数映射到 m 位的位数组。插入设 k 位为 1；查询检查是否全 1——有 0 则肯定不存在。
python
import hashlib, struct
class BloomFilter:
def __init__(self, s, k):
self.b=[0]*s; self.k=k
def _p(self, x):
h=hashlib.md5(x.encode()).digest()
h1,h2=struct.unpack('ii',h[:8])
return [(h1+i*h2)%len(self.b) for i in range(self.k)]
def add(self, x):
for p in self._p(x): self.b[p]=1
def contains(self, x):
return all(self.b[p] for p in self._p(x))
bf=BloomFilter(1000,3)
bf.add("malice")
print(bf.contains("malice"), bf.contains("unknown"))
# 预期: True False应用： 缓存穿透防护。
并查集——你是我兄弟吗？
1000 个营地，实时判断两个营地是否连通。并查集用树表示集合，根是代表元。
python
class UnionFind:
def __init__(self, n):
self.par = list(range(n)); self.rk = [0]*n; self.cnt = n
def find(self, x):
while self.par[x] != x:
self.par[x] = self.par[self.par[x]]; x = self.par[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb: return False
if self.rk[ra] < self.rk[rb]: ra, rb = rb, ra
self.par[rb] = ra
if self.rk[ra] == self.rk[rb]: self.rk[ra] += 1
self.cnt -= 1; return True
uf = UnionFind(10)
uf.union(0,1); uf.union(1,2); uf.union(3,4)
print(uf.connected(0,2), uf.connected(0,3))
uf.union(2,3)
print(uf.connected(0,3), uf.cnt)
# 预期: True False True 6复杂度： 路径压缩+按秩合并后 O(alpha(n))，反阿克曼函数，宇宙原子数也 <= 5。 应用： Kruskal 最小生成树。
线段树——区间查询和更新
查第 3 到第 8 个营地的总物资，随时更新。数组 O(n)，线段树 O(log n)。
python
class SegTree:
def __init__(self, data):
self.n = len(data); self.t = [0]*(4*self.n)
self._b(data, 0, 0, self.n-1)
def _b(self, d, n, l, r):
if l == r: self.t[n]=d[l]; return
m = (l+r)//2
self._b(d, n*2+1, l, m); self._b(d, n*2+2, m+1, r)
self.t[n] = self.t[n*2+1] + self.t[n*2+2]
def update(self, i, v):
self._u(0, 0, self.n-1, i, v)
def _u(self, n, l, r, i, v):
if l == r: self.t[n]=v; return
m = (l+r)//2
if i<=m: self._u(n*2+1,l,m,i,v)
else: self._u(n*2+2,m+1,r,i,v)
self.t[n] = self.t[n*2+1] + self.t[n*2+2]
def query(self, ql, qr):
return self._q(0, 0, self.n-1, ql, qr)
def _q(self, n, l, r, ql, qr):
if ql<=l and r<=qr: return self.t[n]
if r<ql or l>qr: return 0
m = (l+r)//2
return self._q(n*2+1,l,m,ql,qr)+self._q(n*2+2,m+1,r,ql,qr)
seg = SegTree([1,3,5,7,9,11])
print(seg.query(1,3)); seg.update(2,6); print(seg.query(1,3))
# 预期: 15 16应用： 区间和+更新、RMQ。
Trie——林间驿站的自动索引
10 亿条物资名称，输"火"字浮现"火焰草""火石"等。Trie 共享共同前缀。
python
class Trie:
class Node:
def __init__(self):
self.ch={}; self.end=False
def __init__(self):
self.root = self.Node()
def insert(self, w):
cur=self.root
for c in w:
if c not in cur.ch: cur.ch[c]=self.Node()
cur=cur.ch[c]
cur.end=True
def autocomplete(self, p):
cur=self.root
for c in p:
if c not in cur.ch: return []
cur = cur.ch[c]
res = []; self._dfs(cur, list(p), res); return res
def _dfs(self, n, path, res):
if n.end: res.append(''.join(path))
for c in sorted(n.ch):
path.append(c); self._dfs(n.ch[c], path, res); path.pop()
t = Trie()
for w in ["北京烤鸭","北京烤鸭店","北京烤鸭做法","北京烤鱼","北京烤肉"]:
t.insert(w)
print(t.autocomplete("北京烤"))
# 预期: ['北京烤鸭','北京烤鸭店','北京烤鸭做法','北京烤鱼','北京烤肉']应用： 搜索引擎自动补全、IP 路由最长前缀匹配。
四种速览
| 数据结构 | 一句话 | 应用 |
|---|---|---|
| 布隆过滤器 | 用位图判断肯定不在 | 缓存穿透防护 |
| 并查集 | 只关心你属于哪个圈子 | Kruskal 最小生成树 |
| 线段树 | 区间递归切半存结果 | 区间查询+更新 |
| Trie | 相同前缀不用重复存 | 搜索引擎自动补全 |
常见陷阱
| 卡点 | 怎么办 |
|---|---|
| 布隆过滤器不支持删除 | 用计数布隆过滤器 |
| 并查集递归 find 爆栈 | 用迭代版 |
| 线段树数组大小 | 开 4*n 安全 |
| Trie children 选型 | 英文用数组[26]，中文用字典 |
旅人笔记
四个数据结构的共同主线：用空间换时间，用结构换效率。算法森林探险到此结束。
卷末：下一站 Vol 3
你已经学会了二分法、分治、数组、链表、树、图、散列、并查集、线段树、Trie。接下来钻进计算机地心。