系统编程

Zig std 标准库容器：从 ArrayList 到 HashMap

本文系统讲解 Zig 标准库的容器家族：ArrayList/StringArrayList、HashMap/StringHashMap、ArrayHashMap/StringArrayHashMap 的 API、容量管理、内存所有权与迭代排序实践，并给出综合的词频统计示例。

Plume 7 分钟阅读 3409 字

与大多数语言的标准库不同，Zig 的容器从不隐藏分配器。每一个 ArrayList、HashMap 的构造都必须显式传入一个 std.mem.Allocator，容器的内存生命周期因此完全透明。这正是 https://plumephp.com/zig-memory-management/ 中"显式优于隐式"哲学的容器侧体现。

本文深入 std.ArrayList、std.HashMap、std.ArrayHashMap 三大容器家族，覆盖 API 语义、容量管理、内存所有权、排序迭代与工程陷阱。

1. 容器的内存所有权模型

1.1 Allocator 从构造到析构

所有容器都遵循同一个生命周期契约：

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // 容器自己持有 backing 内存
    var list = std.ArrayList(u32).init(allocator);
    defer list.deinit(); // 归还 backing 内存

    try list.append(1);
    try list.append(2);
    std.debug.print("items = {any}\n", .{list.items});
}

init(allocator) 只是记录分配器引用，不分配任何内存；第一次 append 触发首次分配。deinit() 释放容器持有的 backing 内存。

1.2 谁拥有元素？

三条所有权铁律：

  1. 容器拥有"存储区"：items / backing array 归容器所有，deinit 后指针失效。
  2. 容器不拥有元素的引用语义：如果元素是切片（如 []const u8），容器只保存切片指针，切片的底层内存由你管理。
  3. 清空 ≠ 释放：clearRetainingCapacity() 保留容量但逻辑清空；deinit() 彻底释放。

1.3 容量三件套

方法语义
ensureTotalCapacity(n)预留至少 n 个元素的容量，不会改变 len
clearRetainingCapacity()清空元素但保留 backing 内存
shrinkAndFree(n)缩小容量到 n 并释放多余内存（n ≥ len 时合法）

使用 ensureTotalCapacity 批量插入是高性能的关键——避免反复 realloc：

const expected: usize = 10_000;
try list.ensureTotalCapacity(expected);
var i: usize = 0;
while (i < expected) : (i += 1) {
    list.appendAssumeCapacity(i); // 不检查容量，直接写入
}

appendAssumeCapacity 跳过容量检查，若容量不足会越界——只在 ensureTotalCapacity 之后用。

2. ArrayList 与 StringArrayList

2.1 ArrayList(T) 核心 API

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var list = std.ArrayList(i32).init(allocator);
    defer list.deinit();

    try list.append(10);                  // 尾部追加
    try list.appendSlice(&.{ 20, 30 });   // 批量追加
    try list.insert(0, 5);                // 头部插入 O(n)
    _ = list.orderedRemove(0);            // 删除并保持顺序 O(n)
    _ = list.swapRemove(0);               // 删除但不保序 O(1)

    // 视图切片，可以直接排序
    const items = list.items;             // []i32

    // 转为调用方拥有的切片（容器清零）
    const owned = try list.toOwnedSlice();
    defer allocator.free(owned);
}

常用方法速查：

方法复杂度说明
append(item)摊还 O(1)尾部追加
appendSlice(s)O(n)批量追加
insert(i, item)O(n)任意位置插入
orderedRemove(i)O(n)保序删除
swapRemove(i)O(1)用尾部元素填补空洞
resize(n)O(n)改变长度，多出的位置未初始化
ensureTotalCapacity(n)O(n)预留容量
toOwnedSlice()O(n)转移所有权
deinit()O(n)释放 backing

2.2 字符串专用别名

std.StringArrayList 就是 ArrayList([]const u8) 的别名：

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var words = std.StringArrayList.init(allocator);
    defer words.deinit();

    try words.append("zig");
    try words.append("comptime");
    try words.append("allocator");

    for (words.items) |w| {
        std.debug.print("{s}\n", .{w});
    }
}

陷阱：StringArrayList 保存的是切片的拷贝，不是内容的拷贝。如果切片指向堆内存，你必须独立管理那块内存的生命周期；最常见的模式是用 Arena 分配器一次管到底。

3. HashMap 与 StringHashMap

3.1 构造与基本操作

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var ages = std.StringHashMap(u8).init(allocator);
    defer ages.deinit();

    try ages.put("alice", 30);
    try ages.put("bob", 25);

    // 读
    if (ages.get("alice")) |age| {
        std.debug.print("alice = {d}\n", .{age});
    }

    // 写（推荐 getOrPut，避免两次哈希）
    const gop = try ages.getOrPut("carol");
    if (!gop.found_existing) {
        gop.key_ptr.* = "carol";   // 键的拷贝（指针拷贝）
    }
    gop.value_ptr.* = 28;

    // 删
    _ = ages.fetchRemove("bob");

    std.debug.print("count = {d}\n", .{ages.count()});
}

类型别名对照：

别名实际类型适用场景
std.StringHashMap(V)HashMap([]const u8, V, StringIndexContext, ...)字符串键
std.AutoHashMap(K, V)HashMap(K, V, AutoContext)键类型可用 == 比较（整数、枚举、指针等）
std.HashMap(K, V, Context)原始泛型需要自定义哈希/比较

3.2 getOrPut 的完整语义

getOrPut(key) 返回一个结构：

const result = try map.getOrPut(key);
// result.found_existing: bool — 键是否已存在
// result.key_ptr: *K      — 键的存储位置
// result.value_ptr: *V    — 值的存储位置
  • 键已存在：found_existing == true，直接改 value_ptr.*；
  • 键不存在：found_existing == false，必须先写 key_ptr.*，否则键是未定义值，后续查找会出错。

对于字符串键，gop.key_ptr.* = "carol" 拷贝的是 []const u8 这个切片头（指针+长度），不是字符串内容。若键指向的堆字符串会在插入后被释放，就会产生悬垂键。

3.3 自定义哈希与比较 Context

当键不是简单类型（例如结构体）时，需要提供 hash 与 eql 上下文：

const std = @import("std");

const User = struct { id: u32, name: []const u8 };

const UserContext = struct {
    pub fn hash(_: UserContext, user: User) u64 {
        return std.hash.Wyhash.hash(0, std.mem.asBytes(&user.id));
    }
    pub fn eql(_: UserContext, a: User, b: User) bool {
        return a.id == b.id;
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // 以 User 为键，值为字符串
    var map = std.HashMap(User, []const u8, UserContext, 80).init(allocator);
    defer map.deinit();

    try map.put(.{ .id = 1, .name = "plume" }, "admin");
    const roles = map.get(.{ .id = 1, .name = "plume" });
    std.debug.print("roles = {any}\n", .{roles});
}

80 是最大负载因子（百分比），超过后自动扩容。哈希函数用 std.hash.Wyhash（Zig 默认字符串哈希，快且分布好）。

3.4 容量与哈希碰撞

HashMap 自动管理负载因子，但批量插入前 ensureTotalCapacity 能避免多次 rehash：

// 已知要插入 1000 个键
try map.ensureTotalCapacity(1000);
// 之后可以用 putAssumeCapacity 无检查插入
for (keys) |k| {
    map.putAssumeCapacity(k, value);
}

哈希碰撞的代价：最坏情况下 HashMap 退化为 O(n) 查找。Zig 使用开放寻址 + 平方探测，Wyhash 对常见键分布足够均匀。

4. ArrayHashMap：有序遍历

4.1 与 HashMap 的本质区别

ArrayHashMap(K, V, Context) 在哈希表之外额外维护一个并行数组，记录插入顺序。代价是删除变为 O(n)（需要维护数组），换来的收益是可预测的迭代顺序：

特性HashMapArrayHashMap
查找O(1) 摊还O(1) 摊还
插入O(1) 摊还O(1) 摊还（数组尾部追加）
删除O(1) 摊还O(n)（数组紧凑化）
迭代顺序哈希桶顺序（不稳定）插入顺序
额外内存无一个元素数组
别名StringHashMapStringArrayHashMap

4.2 使用与有序遍历

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var map = std.StringArrayHashMap(i32).init(allocator);
    defer map.deinit();

    try map.put("third", 3);
    try map.put("first", 1);
    try map.put("second", 2);

    // 按插入顺序遍历
    for (map.keys(), map.values()) |k, v| {
        std.debug.print("{s} = {d}\n", .{ k, v });
    }
    // 输出：
    // third = 3
    // first = 1
    // second = 2

    // 按键排序遍历（keys 是普通切片，直接排序）
    const keys = map.keys();
    std.sort.block([]const u8, keys, {}, lessThan);
    for (keys) |k| {
        std.debug.print("sorted: {s}\n", .{k});
    }
}

fn lessThan(_: void, a: []const u8, b: []const u8) bool {
    return std.mem.order(u8, a, b) == .lt;
}

4.3 索引访问与定位

ArrayHashMap 提供索引能力，用于 LRU、有序缓存等场景：

// 判断键是否已存在，并取索引
if (map.getIndex("first")) |idx| {
    std.debug.print("first 在索引 {d}\n", .{idx});
}

// 用有序数组的语义删除
_ = map.swapRemoveAt(0);   // 哈希表 O(1)，数组交换删除
// 或保序删除
_ = map.orderedRemoveAt(0); // 数组整体前移 O(n)

5. 排序与迭代实战

5.1 排序 API

Zig 0.13+ 推荐使用 std.sort 命名空间，替代旧 std.mem.sort：

const std = @import("std");

const Person = struct { name: []const u8, age: u8 };

fn byAge(_: void, a: Person, b: Person) bool {
    return a.age < b.age;
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var people = std.ArrayList(Person).init(allocator);
    defer people.deinit();
    try people.appendSlice(&.{
        .{ .name = "bob", .age = 25 },
        .{ .name = "alice", .age = 30 },
        .{ .name = "carol", .age = 22 },
    });

    // 不稳定排序（块排序，快）
    std.sort.block(Person, people.items, {}, byAge);

    // 稳定排序（归并），结构体含多个字段时推荐
    std.sort.insertion(Person, people.items, {}, byAge);
    // 或 std.sort.merge

    for (people.items) |p| {
        std.debug.print("{s}: {d}\n", .{ p.name, p.age });
    }
}

lessThan 的签名固定为 fn (context: anytype, lhs: T, rhs: T) bool，context 在排序期间透传，可携带比较所需的辅助状态。

5.2 HashMap 迭代器

var it = map.iterator();
while (it.next()) |entry| {
    // entry.key_ptr: *const K
    // entry.value_ptr: *V
    std.debug.print("{s} -> {d}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
}

迭代中删除元素：std.HashMap 的迭代器不提供 remove()。安全做法是先把待删键收集起来，迭代结束后再删：

var to_remove = std.ArrayList([]const u8).init(allocator);
defer to_remove.deinit();

var it = map.iterator();
while (it.next()) |entry| {
    if (shouldDrop(entry.value_ptr.*)) {
        try to_remove.append(entry.key_ptr.*);
    }
}
for (to_remove.items) |k| {
    _ = map.fetchRemove(k);
}

5.3 数组排序 + 去重

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var list = std.ArrayList(u32).init(allocator);
    defer list.deinit();
    try list.appendSlice(&.{ 3, 1, 2, 3, 4, 1 });

    std.sort.block(u32, list.items, {}, lessU32);
    const deduped = std.mem.trim(u32, list.items, &.{}); // 占位示意

    // 原地去重：排序后保留唯一元素
    var n: usize = 0;
    for (list.items) |v| {
        if (n == 0 or list.items[n - 1] != v) {
            list.items[n] = v;
            n += 1;
        }
    }
    list.shrinkRetainingCapacity(n); // 逻辑长度缩短

    std.debug.print("去重后: {any}\n", .{list.items});
}

fn lessU32(_: void, a: u32, b: u32) bool {
    return a < b;
}

shrinkRetainingCapacity(n) 只改变逻辑长度，不释放内存——配合"排序后去重"是标准配方。

6. 综合示例：词频统计器

把上述容器串起来——统计一段文本的单词频率，输出 Top N：

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const text =
        \\zig is fast, zig is safe, zig is explicit.
        \\allocator allocator allocator!
    ;

    // 用 Arena：单词切片指向 text 内部，无需逐份拷贝
    var arena = std.heap.ArenaAllocator.init(allocator);
    defer arena.deinit();
    const arena_alloc = arena.allocator();

    var freq = std.StringArrayHashMap(usize).init(arena_alloc);

    var it = std.mem.tokenizeAny(u8, text, " .,!?;:");
    while (it.next()) |word| {
        const gop = try freq.getOrPut(word);
        gop.value_ptr.* += 1;
    }

    // 按键排序（字母序）输出全部
    const keys = freq.keys();
    std.sort.block([]const u8, keys, {}, lessThan);
    for (keys) |k| {
        std.debug.print("{s}: {d}\n", .{ k, freq.get(k).? });
    }
}

fn lessThan(_: void, a: []const u8, b: []const u8) bool {
    return std.mem.order(u8, a, b) == .lt;
}

这里的两个关键点：

  1. 用 StringArrayHashMap 得到确定性顺序（词频并列时需要稳定展示）；
  2. 用 Arena 管理键内存——tokenizeAny 产出的切片直接作为键，插入即存切片头，因为 text 是编译期字符串常量、生命周期全局，不存在悬垂问题。如果词来自堆内存，请为键独立分配拷贝。

7. 陷阱与最佳实践

7.1 常见陷阱

陷阱后果规避
list.append 后仍用旧 items 指针悬垂指针（realloc 移动了 backing）每次取 list.items 时重新求值
HashMap 键指向堆字符串后被释放未定义行为Arena / 拷贝键
用 getOrPut 但忘写 key_ptr.*哈希表损坏，查找失败found_existing == false 时必写键
迭代中删除迭代器失效先收集后删除
不调 ensureTotalCapacity 批量插入多次 realloc，性能骤降批量前预留容量
只 clearRetainingCapacity 就以为释放了内存峰值高配合 shrinkAndFree

7.2 容量选择决策表

你的场景推荐容器理由
需要按键查找 + 顺序输出StringArrayHashMap保序 + O(1) 查找
只关心查找/去重StringHashMap / AutoHashMap删除 O(1)，内存更省
动态列表 + 索引ArrayList最简单、最通用
大量短字符串StringArrayList + Arena一次分配，零碎片
需要自定义键类型HashMap(K, V, Context)自定义 hash/eql

7.3 总结

Zig 容器的设计哲学可以浓缩为一句话：容器只管理自己的 backing 内存，元素的生命周期始终由你掌握。这与 https://plumephp.com/zig-memory-management/ 的 Arena/分配器模式、https://plumephp.com/zig-performance-optimization/ 中的缓存友好原则一脉相承。选对容器、管好容量、明确所有权，Zig 的数据结构代码就能既快又安全。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「系统编程」更多文章

  1. Zig 嵌入式开发：交叉编译与 MCU 裸机实践
  2. Zig 裸机开发：从零编写最小内核
  3. Zig 高级 FFI：动态库、回调、内存布局与 C++ ABI