系统编程

Zig 算法与数据结构实战：哈希表、树、图与排序

Zig 标准库提供了 ArrayList、HashMap、PriorityQueue 等基础容器，但理解其内部实现才能选对结构。本文手写开放寻址哈希表、二叉搜索树、二叉堆、邻接表图，讲解 BFS/DFS、拓扑排序与快速排序的 Zig 实现，并给出 LRU 缓存与并查集两个综合案例。

Plume 6 分钟阅读 2859 字

引言

算法与数据结构是工程能力的底座，但「会用库」和「懂原理」之间有巨大鸿沟。Zig 的优势在于：标准库源码可读、没有隐藏的 GC 与装箱、内存布局完全暴露——这让它成为从零实现并真正理解数据结构的理想语言。

本文从复杂度分析讲起，手写开放寻址哈希表、二叉搜索树、二叉堆、邻接表图与若干排序算法，最后给出 LRU 缓存与并查集两个工程级案例。所有代码可直接编译。

前置：标准库容器用法、手动内存管理。

目录

1. 结构选型与复杂度

1.1 常见操作复杂度对照

结构查找插入删除有序遍历
数组O(n)O(1)*O(n)天然有序
哈希表O(1)O(1)O(1)不支持
二叉搜索树O(log n)O(log n)O(log n)支持
平衡树（AVL/红黑）O(log n)O(log n)O(log n)支持
二叉堆O(n)O(log n)O(log n)仅取极值
跳表O(log n)O(log n)O(log n)支持

* 尾部插入摊销 O(1)，中间插入需搬移。

1.2 选型决策

需要按键快速查找？           → 哈希表
需要按序遍历 / 范围查询？     → 平衡树 / B 树
只需要极值？                 → 堆
数据量小（< 32）？           → 线性数组反而最快
需要最近使用淘汰？           → 哈希表 + 双向链表

2. 基准测试与性能度量

2.1 用 std.time.Timer

const std = @import("std");

test "benchmark linear vs hash" {
    var timer = try std.time.Timer.start();
    const elapsed = timer.read();
    std.debug.print("耗时 {d} ns\n", .{elapsed});
}

2.2 防止编译器优化掉

基准测试最常见的陷阱是编译器把「没有副作用的计算」整个删除。用 std.mem.doNotOptimizeAway 或 std.blackBox 阻止：

var sum: u64 = 0;
for (data) |x| sum +%= x;
std.mem.doNotOptimizeAway(sum);

3. 开放寻址哈希表

3.1 设计要点

开放寻址（open addressing）不用链表，冲突时按探测序列找下一个空槽。相比链地址法，它缓存更友好、无需为每个桶分配节点。

fn HashMap(comptime K: type, comptime V: type) type {
    return struct {
        const Self = @This();
        const Entry = struct {
            key: K,
            value: V,
            used: bool = false,
            tombstone: bool = false,
        };

        entries: []Entry,
        count: usize = 0,
        alloc: std.mem.Allocator,

        pub fn init(alloc: std.mem.Allocator, cap: usize) !Self {
            const entries = try alloc.alloc(Entry, cap);
            for (entries) |*e| e.* = .{ .key = undefined, .value = undefined };
            return .{ .entries = entries, .alloc = alloc };
        }

        pub fn deinit(self: *Self) void {
            self.alloc.free(self.entries);
        }
    };
}

3.2 哈希与探测

fn hash(key: []const u8) u64 {
    return std.hash.Wyhash.hash(0, key);
}

fn probe(self: *Self, key: []const u8) ?usize {
    const mask = self.entries.len - 1; // 容量必须是 2 的幂
    var idx: usize = @intCast(hash(key) & mask);
    var first_tombstone: ?usize = null;

    while (true) {
        const e = &self.entries[idx];
        if (!e.used and !e.tombstone) {
            return first_tombstone orelse idx;
        }
        if (e.used and std.mem.eql(u8, e.key, key)) return idx;
        if (e.tombstone and first_tombstone == null) first_tombstone = idx;
        idx = (idx + 1) & mask;
    }
}

3.3 删除与墓碑

开放寻址不能直接清空槽位，否则会截断探测链导致后续键查不到。删除时标记 tombstone = true，插入时可复用墓碑槽。

pub fn remove(self: *Self, key: []const u8) void {
    const idx = self.find(key) orelse return;
    self.entries[idx].tombstone = true;
    self.entries[idx].used = false;
    self.count -= 1;
}

3.4 负载因子与扩容

负载因子超过 0.7 时性能急剧下降（探测链变长）。此时分配两倍容量并重新插入所有存活条目：

if (self.count * 10 >= self.entries.len * 7) try self.grow();

踩坑：扩容后必须用新容量重新计算哈希位置，不能直接搬移——hash & mask 中的 mask 变了。

4. 二叉搜索树

4.1 节点定义

fn BST(comptime T: type) type {
    return struct {
        const Self = @This();
        pub const Node = struct {
            key: T,
            left: ?*Node = null,
            right: ?*Node = null,
        };

        root: ?*Node = null,
        alloc: std.mem.Allocator,

        pub fn insert(self: *Self, key: T) !void {
            const node = try self.alloc.create(Node);
            node.* = .{ .key = key };
            var slot = &self.root;
            while (slot.*) |cur| {
                if (key < cur.key) slot = &cur.left else slot = &cur.right;
            }
            slot.* = node;
        }
    };
}

var slot = &self.root 这种「指向指针的指针」写法非常 Zig——一次循环就能定位到要写入的位置，无需父节点回溯。

4.2 中序遍历

fn inorder(node: ?*Node, out: *std.ArrayList(T)) !void {
    const n = node orelse return;
    try inorder(n.left, out);
    try out.append(n.key);
    try inorder(n.right, out);
}

中序遍历二叉搜索树得到升序序列，这是 BST 的定义性质。

5. 二叉堆与优先队列

5.1 数组表示的完全二叉树

堆用数组存储，索引关系：父节点 (i-1)/2，左子 2i+1，右子 2i+2。无需指针，缓存友好。

fn MinHeap(comptime T: type) type {
    return struct {
        const Self = @This();
        items: std.ArrayList(T),

        pub fn init(alloc: std.mem.Allocator) Self {
            return .{ .items = std.ArrayList(T).init(alloc) };
        }

        pub fn push(self: *Self, value: T) !void {
            try self.items.append(value);
            var i = self.items.items.len - 1;
            while (i > 0) {
                const parent = (i - 1) / 2;
                if (self.items.items[parent] <= self.items.items[i]) break;
                std.mem.swap(T, &self.items.items[parent], &self.items.items[i]);
                i = parent;
            }
        }
    };
}

5.2 弹出最小值

pub fn pop(self: *Self) ?T {
    if (self.items.items.len == 0) return null;
    const top = self.items.items[0];
    const last = self.items.pop();
    if (self.items.items.len > 0) {
        self.items.items[0] = last.?;
        self.siftDown(0);
    }
    return top;
}

fn siftDown(self: *Self, start: usize) void {
    var i = start;
    const n = self.items.items.len;
    while (true) {
        const l = 2 * i + 1;
        const r = 2 * i + 2;
        var smallest = i;
        if (l < n and self.items.items[l] < self.items.items[smallest]) smallest = l;
        if (r < n and self.items.items[r] < self.items.items[smallest]) smallest = r;
        if (smallest == i) break;
        std.mem.swap(T, &self.items.items[i], &self.items.items[smallest]);
        i = smallest;
    }
}

6. 图的表示与遍历

6.1 邻接表

const Graph = struct {
    adj: []std.ArrayList(usize),
    alloc: std.mem.Allocator,

    pub fn init(alloc: std.mem.Allocator, n: usize) !Graph {
        const adj = try alloc.alloc(std.ArrayList(usize), n);
        for (adj) |*list| list.* = std.ArrayList(usize).init(alloc);
        return .{ .adj = adj, .alloc = alloc };
    }

    pub fn addEdge(self: *Graph, u: usize, v: usize) !void {
        try self.adj[u].append(v);
    }
};

稠密图（边数接近 n²）用邻接矩阵更省内存（位矩阵）；稀疏图用邻接表。

6.2 BFS

fn bfs(g: *Graph, start: usize, visited: []bool) !void {
    var queue = std.ArrayList(usize).init(g.alloc);
    defer queue.deinit();

    try queue.append(start);
    visited[start] = true;

    var head: usize = 0;
    while (head < queue.items.len) : (head += 1) {
        const u = queue.items[head];
        for (g.adj[u].items) |v| {
            if (!visited[v]) {
                visited[v] = true;
                try queue.append(v);
            }
        }
    }
}

用 head 索引而非 orderedRemove(0)，避免每次出队都搬移数组——BFS 队列是典型的 FIFO，索引推进即可。

6.3 DFS 与拓扑排序

fn topoSort(g: *Graph, n: usize, alloc: std.mem.Allocator) ![]usize {
    var indegree = try alloc.alloc(usize, n);
    defer alloc.free(indegree);
    @memset(indegree, 0);
    for (0..n) |u| for (g.adj[u].items) |v| {
        indegree[v] += 1;
    };

    var queue = std.ArrayList(usize).init(alloc);
    defer queue.deinit();
    for (0..n) |u| if (indegree[u] == 0) try queue.append(u);

    var order = std.ArrayList(usize).init(alloc);
    var head: usize = 0;
    while (head < queue.items.len) : (head += 1) {
        const u = queue.items[head];
        try order.append(u);
        for (g.adj[u].items) |v| {
            indegree[v] -= 1;
            if (indegree[v] == 0) try queue.append(v);
        }
    }
    return order.toOwnedSlice();
}

Kahn 算法：反复取出入度为 0 的节点。若最终输出节点数少于 n，说明存在环。

7. 排序算法实现

7.1 快速排序

fn quickSort(items: []i32, lo: usize, hi: usize) void {
    if (lo >= hi) return;
    const pivot = items[hi];
    var i = lo;
    for (lo..hi) |j| {
        if (items[j] < pivot) {
            std.mem.swap(i32, &items[i], &items[j]);
            i += 1;
        }
    }
    std.mem.swap(i32, &items[i], &items[hi]);
    if (i > lo) quickSort(items, lo, i - 1);
    quickSort(items, i + 1, hi);
}

平均 O(n log n)，最坏 O(n²)（已排序输入 + 取末元素为轴）。生产实现应随机选轴或三数取中，并切换小数组到插入排序。

7.2 用标准库

大多数场景直接用 std.mem.sort（内部是 pdqsort，即模式消除快速排序）：

std.mem.sort(i32, items, {}, std.sort.asc(i32));
std.mem.sort(Person, people, {}, struct {
    fn lessThan(_: void, a: Person, b: Person) bool {
        return a.age < b.age;
    }
}.lessThan);

8. 动态规划与记忆化

8.1 自顶向下 + 记忆化

fn fibMemo(n: usize, memo: []?u64) u64 {
    if (n <= 1) return n;
    if (memo[n]) |v| return v;
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo[n] = result;
    return result;
}

8.2 背包问题

fn knapsack(weights: []const u32, values: []const u32, capacity: u32, alloc: std.mem.Allocator) !u32 {
    const dp = try alloc.alloc(u32, capacity + 1);
    defer alloc.free(dp);
    @memset(dp, 0);

    for (weights, values) |w, v| {
        var c: u32 = capacity;
        while (c >= w) : (c -= 1) {
            dp[c] = @max(dp[c], dp[c - w] + v);
        }
    }
    return dp[capacity];
}

踩坑：0-1 背包的容量循环必须倒序，正序会让同一物品被重复选取（那是完全背包的写法）。

9. 综合案例：LRU 与并查集

9.1 LRU 缓存

哈希表 O(1) 定位 + 双向链表 O(1) 移动，是「最近最少使用」的标准实现：

const LruCache = struct {
    const Node = struct {
        key: u64,
        value: u64,
        prev: ?*Node = null,
        next: ?*Node = null,
    };

    map: std.AutoHashMap(u64, *Node),
    head: ?*Node = null, // 最近使用
    tail: ?*Node = null, // 最久未用
    capacity: usize,
    alloc: std.mem.Allocator,

    pub fn get(self: *LruCache, key: u64) ?u64 {
        const node = self.map.get(key) orelse return null;
        self.moveToFront(node);
        return node.value;
    }
};

get 命中后要把节点移到链表头，put 超容量时淘汰链表尾。

9.2 并查集

路径压缩 + 按秩合并，摊销复杂度接近 O(1)：

const DSU = struct {
    parent: []usize,
    rank: []u8,

    pub fn find(self: *DSU, x: usize) usize {
        var root = x;
        while (self.parent[root] != root) root = self.parent[root];
        // 路径压缩
        var cur = x;
        while (self.parent[cur] != root) {
            const next = self.parent[cur];
            self.parent[cur] = root;
            cur = next;
        }
        return root;
    }

    pub fn union(self: *DSU, a: usize, b: usize) void {
        const ra = self.find(a);
        const rb = self.find(b);
        if (ra == rb) return;
        if (self.rank[ra] < self.rank[rb]) {
            self.parent[ra] = rb;
        } else if (self.rank[ra] > self.rank[rb]) {
            self.parent[rb] = ra;
        } else {
            self.parent[rb] = ra;
            self.rank[ra] += 1;
        }
    }
};

并查集用于连通性判断、Kruskal 最小生成树、朋友圈问题等。

速查表

需求结构 / 算法Zig 实现要点
键值查找开放寻址哈希表容量 2 的幂 + hash & mask
删除键墓碑标记保留探测链，插入可复用
有序数据二叉搜索树 / 平衡树递归类型用 ?*Node
取极值二叉堆数组存储，2i+1 / 2i+2
建堆自底向上 sift-downO(n)
图遍历BFS / DFS队列用索引推进而非出队
拓扑排序Kahn 入度法输出数 < n 即有环
通用排序std.mem.sortpdqsort，不稳定
稳定排序归并排序需 O(n) 辅助空间
缓存淘汰LRUHashMap + 双向链表
连通性并查集路径压缩 + 按秩合并

一句话记忆

选结构先看操作模式：查找用哈希、有序用树、极值用堆、连通用并查集；实现时记住三件事——开放寻址删除要留墓碑、堆是数组且建堆 O(n)、DP 容量循环方向决定 0-1 还是完全背包。

相关阅读

延伸阅读

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「系统编程」更多文章

  1. Zig 解析器与编译器前端：词法分析、递归下降与 AST
  2. Zig 游戏开发实战：raylib、ECS 架构与游戏循环
  3. Zig 文本处理：Unicode、正则与高性能字符串