造轮子：手写简化版 HashMap

本章目标

这一章实现一个简化版哈希表，理解哈希函数、桶、冲突、扩容和键值查找。目标不是超过标准库，而是看清 HashMap 的基本机械结构。

它是什么

哈希表用键找到值。它会把 key 通过哈希函数转换成数字，再映射到数组下标。

key -> hash -> bucket index -> entries

因为不同 key 可能落到同一个桶，所以需要处理冲突。最简单的方式是每个桶放一个 Vec<(K, V)>。

为什么需要

HashMap 是工程里最常见的数据结构之一：请求头、路由表、缓存、索引、配置都可以用它表达。手写一遍后，你会明白为什么 key 要实现哈希和相等比较，为什么容量影响性能。

怎么使用

简化目标：

let mut map = SimpleMap::new();
map.insert("host".to_string(), "127.0.0.1".to_string());
assert_eq!(map.get("host"), Some(&"127.0.0.1".to_string()));

为了降低难度，可以先只支持 String 作为 key。等理解后再泛型化。

逐行解释

fn bucket_index(&self, key: &str) -> usize {
    let mut hash = 0usize;
    for byte in key.bytes() {
        hash = hash.wrapping_mul(31).wrapping_add(byte as usize);
    }
    hash % self.buckets.len()
}

fn bucket_index 根据 key 计算桶下标。
key: &str 借用字符串，不取得所有权。
let mut hash = 0usize; 初始化哈希值。
for byte in key.bytes() 遍历 UTF-8 字节。
wrapping_mul(31) 乘以 31，溢出时按整数环绕处理。
wrapping_add(byte as usize) 把当前字节混入哈希。
hash % self.buckets.len() 把大数字映射到桶数组范围。

这个哈希函数很简陋，但足够教学。真实标准库使用更安全的哈希器。

常见坑

哈希相同不代表 key 相同，所以桶里还要比较 key。
桶数量不能是 0，否则取模会 panic。
插入已有 key 时应该更新值，而不是重复插入。
哈希表扩容会移动元素，引用不能跨扩容长期保存。

练习

定义 SimpleMap { buckets: Vec<Vec<(String, String)>> }。
实现 new() 创建固定 16 个桶。
实现 insert，已有 key 时更新。
实现 get(&self, key: &str) -> Option<&String>。

造轮子任务

实现简化 SimpleMap 后，用它替换一个请求头解析示例中的 HashMap。观察 API 差异：标准库给了你哪些泛型能力、迭代能力和性能保障。

小结

哈希表的核心不是神秘魔法，而是“哈希到桶，桶内比较，必要时扩容”。理解这层结构后，你会更谨慎地选择 key 类型、容量和查找边界。