Day 53: std.hash_map模块：哈希映射

1. 引言：高效键值存储

哈希映射（Hash Map）是现代编程中用于快速键值查找的最核心数据结构之一。Zig的std.HashMap提供了一个高性能、灵活且内存高效的实现。它利用了Zig的comptime和泛型能力，允许用户自定义键的哈希和比较逻辑，同时也需要显式地管理内存，这完全符合Zig的语言哲学。

2. `HashMap(K, V, Context)`

std.HashMap是一个泛型结构体，需要三个编译期参数：

K: 键（Key）的类型。
V: 值（Value）的类型。
Context: 一个上下文类型，用于定义键的哈希和相等性比较。通常，你可以使用std.hash_map.DefaultContext，它能处理大部分基本类型。

初始化一个HashMap需要一个分配器和上下文实例：

const std = @import("std");

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

    // 使用默认上下文，适用于字符串键
    var map = std.HashMap(u8, i32, std.hash_map.DefaultContext).init(allocator);
    defer map.deinit();

    // ... 使用map
}

对于自定义类型，你需要提供一个实现了hash和eql函数的上下文。

3. 操作：`put`, `get`, `delete`

HashMap的核心操作是插入、检索和删除。

put(key: K, value: V) !void: 插入或更新一个键值对。如果键已存在，其值将被更新。
get(key: K) ?*V: 根据键查找值。如果找到，返回一个指向值的指针 (?*V)；否则返回null。
fetch(key: K) ?V: 与get类似，但返回值本身而不是指针。
remove(key: K) ?V: 删除一个键值对并返回它的值。如果键不存在，返回null。
contains(key: K) bool: 检查一个键是否存在。

const std = @import("std");

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

    var word_counts = std.HashMap([]const u8, u32, std.hash_map.DefaultContext).init(allocator);
    defer word_counts.deinit();

    try word_counts.put("hello", 1);
    try word_counts.put("world", 2);

    // 更新值
    try word_counts.put("hello", word_counts.get("hello").?.* + 1);

    if (word_counts.get("hello")) |count_ptr| {
        std.debug.print("Count of 'hello': {d}\n", .{count_ptr.*});
    }

    _ = word_counts.remove("world");
    std.debug.print("Contains 'world': {}\n", .{word_counts.contains("world")});
}

4. 迭代：`iterator`

你可以通过iterator()方法获取一个迭代器来遍历HashMap中的所有键值对。迭代器返回一个?*Entry，其中Entry包含key和value字段。

var it = word_counts.iterator();
while (it.next()) |entry| {
    std.debug.print("'{s}' -> {d}\n", .{entry.key, entry.value});
}

5. 示例：缓存实现

HashMap是实现缓存的理想选择。下面的例子演示了一个简单的字符串到其长度的缓存。

const std = @import("std");

var cache: std.HashMap([]const u8, usize, std.hash_map.DefaultContext) = undefined;
var gpa: std.heap.GeneralPurposeAllocator(.{}) = undefined;

fn getAndCacheLength(allocator: std.mem.Allocator, s: []const u8) !usize {
    if (cache.get(s)) |len_ptr| {
        std.debug.print("Cache hit for '{s}'\n", .{s});
        return len_ptr.*
    }

    std.debug.print("Cache miss for '{s}'\n", .{s});
    const len = s.len;
    try cache.put(s, len);
    return len;
}

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

    cache = std.HashMap([]const u8, usize, std.hash_map.DefaultContext).init(allocator);
    defer cache.deinit();

    _ = try getAndCacheLength(allocator, "Zig");
    _ = try getAndCacheLength(allocator, "rocks");
    _ = try getAndCacheLength(allocator, "Zig");
}

6. 实践练习：LRU缓存

结合std.HashMap和std.DoublyLinkedList（将在后续章节介绍）来实现一个简单的LRU（最近最少使用）缓存。HashMap用于快速查找，而链表用于维护访问顺序。

挑战：设计一个LruCache结构体，包含put和get方法。当缓存满时，put操作应移除最近最少使用的项。

7. 常见问题

哈希碰撞如何处理？ std.HashMap使用开放寻址法（Open Addressing）和线性探测（Linear Probing）来解决哈希碰撞。这意味着所有条目都存储在同一个数组中，当发生碰撞时，它会线性地寻找下一个可用的槽位。
负载因子和扩容 当HashMap中的元素数量超过其容量的一定比例（负载因子）时，它会自动扩容以保持性能。默认的负载因子约为85%。扩容会创建一个更大的新表，并重新哈希所有现有元素，这是一个昂贵的操作。

8. 总结：`std.HashContext`

std.HashMap的强大之处在于其通过Context参数实现的可定制性。std.hash_map.DefaultContext可以很好地处理字符串和整数，但对于自定义结构体，你需要提供自己的hash和eql函数。这使得HashMap既能提供高级的易用性，又能满足底层性能优化的需求，完美体现了Zig的设计理念。

Day 53: std.hash_map模块：哈希映射

1. 引言：高效键值存储

2. HashMap(K, V, Context)

3. 操作：put, get, delete

4. 迭代：iterator