Rust 从零实现哈希表：链地址与开放寻址，冲突、墓碑与扩容

HashMap 谁都会用，但如果要解释“为什么它在某些负载下会突然变慢”，很多人其实答不上来。

写业务的时候我们习惯了这样：

let mut map = HashMap::new();
map.insert("user:42", 1);
assert_eq!(map.get("user:42"), Some(&1));

能跑就行，又有多少人真正关心过它内部是什么结构呢？直到某天 QPS 涨了，一个哈希冲突特别多的 key 分布把延迟顶到几百毫秒，你才发现对它的内部机制一无所知。

这篇不是讲“怎么用 HashMap”，而是从零把它造出来。造的目的，是弄清楚三件事：冲突怎么解决、扩容什么时候发生、哈希函数为什么不能随便写。

先定义接口，再考虑实现

不管底层怎么设计，一个哈希表对外就这几个动作：

pub trait Table<K, V> {
    fn insert(&mut self, key: K, val: V) -> Option<V>;
    fn get(&self, key: &K) -> Option<&V>;
    fn remove(&mut self, key: &K) -> Option<V>;
    fn len(&self) -> usize;
}

接口先立住，后面的两种实现只是同一个契约的两种满足方式。这也是我写轮子的一贯顺序：接口稳定，实现随便换。

第一个版本：链地址法

链地址法的思路很直白：数组的每个槽不存单个元素，而是存一个桶（bucket）。哈希到同一个槽的 key，都挂到同一个桶里。

use std::collections::LinkedList;

pub struct ChainedMap<K, V> {
    buckets: Vec<LinkedList<(K, V)>>,
    len: usize,
}

impl<K: Eq + std::hash::Hash, V> ChainedMap<K, V> {
    pub fn with_capacity(cap: usize) -> Self {
        let mut buckets = Vec::with_capacity(cap);
        for _ in 0..cap {
            buckets.push(LinkedList::new());
        }
        Self { buckets, len: 0 }
    }
}

查找逻辑就是“先算槽，再在桶里线性扫”：

impl<K: Eq + std::hash::Hash, V> ChainedMap<K, V> {
    fn bucket_index(&self, key: &K) -> usize {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        (hasher.finish() as usize) % self.buckets.len()
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        let idx = self.bucket_index(key);
        self.buckets[idx]
            .iter()
            .find(|(k, _)| k == key)
            .map(|(_, v)| v)
    }

    pub fn insert(&mut self, key: K, val: V) -> Option<V> {
        let idx = self.bucket_index(&key);
        let bucket = &mut self.buckets[idx];
        for (k, v) in bucket.iter_mut() {
            if *k == key {
                return Some(std::mem::replace(v, val));
            }
        }
        bucket.push_back((key, val));
        self.len += 1;
        None
    }
}

链地址法的好处是简单，而且能扛较高的负载因子。负载因子（元素数 / 槽位数）即使到 2、3，也只是桶变长，查找退化成链表遍历，不会彻底崩掉。

代价也很明显：每个元素多一次指针跳转，缓存不友好。这也是它在常数项上比开放寻址慢的原因。

第二个版本：开放寻址法

开放寻址法不额外分配桶。所有元素都放在主数组里，冲突了就按某个探测序列去找下一个空位。

最常用的是线性探测：冲突了就往后挪一格。

pub struct OpenMap<K, V> {
    slots: Vec<Option<(K, V)>>,
    len: usize,
}

impl<K: Eq + std::hash::Hash, V> OpenMap<K, V> {
    pub fn with_capacity(cap: usize) -> Self {
        Self {
            slots: (0..cap).map(|_| None).collect(),
            len: 0,
        }
    }

    fn probe(&self, key: &K) -> impl Iterator<Item = usize> + '_ {
        let start = self.bucket_index(key);
        let cap = self.slots.len();
        (0..cap).map(move |i| (start + i) % cap)
    }

    fn bucket_index(&self, key: &K) -> usize {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        (hasher.finish() as usize) % self.slots.len()
    }
}

插入时沿着探测序列找第一个 None：

    pub fn insert(&mut self, key: K, val: V) -> Option<V> {
        for idx in self.probe(&key).collect::<Vec<_>>() {
            match &mut self.slots[idx] {
                Some((k, v)) if *k == key => {
                    return Some(std::mem::replace(v, val));
                }
                None => {
                    self.slots[idx] = Some((key, val));
                    self.len += 1;
                    return None;
                }
                _ => continue,
            }
        }
        panic!("表满了，需要扩容");
    }

查找则要一路扫到空槽为止，因为“空槽”意味着这个 key 从未插入过：

    pub fn get(&self, key: &K) -> Option<&V> {
        for idx in self.probe(key) {
            match &self.slots[idx] {
                Some((k, v)) if k == key => return Some(v),
                Some(_) => continue,
                None => return None,
            }
        }
        None
    }

开放寻址最致命的坑：墓碑

先看删除。最直觉的写法是把槽置空：

    // 错误示范
    pub fn bad_remove(&mut self, key: &K) -> Option<V> {
        for idx in self.probe(key) {
            if let Some((k, _)) = &self.slots[idx] {
                if k == key {
                    return self.slots[idx].take().map(|(_, v)| v);
                }
            }
        }
        None
    }

但这样会把探测链切断。假设 A 和 B 哈希到同一个槽，A 先插入，B 探测后落在下一个槽。现在删掉 A，A 的槽变成 None。再查 B 时，探测序列第一个位置就是 None，函数直接返回“不存在”——可 B 明明还在数组里。

正确做法是留一个墓碑标记：这个位置曾经被占用，查找不能停，但插入可以复用。

enum Slot<K, V> {
    Empty,
    Tombstone,
    Occupied(K, V),
}

删除时写 Tombstone，查找时 Tombstone 继续往后走，Empty 才停：

    pub fn get(&self, key: &K) -> Option<&V> {
        let slots = &self.slots;
        for idx in self.probe(key) {
            match &slots[idx] {
                Slot::Occupied(k, v) if k == key => return Some(v),
                Slot::Occupied(_) | Slot::Tombstone => continue,
                Slot::Empty => return None,
            }
        }
        None
    }

墓碑是开放寻址法的“删除代价”。链地址法删除只需要摘链，开放寻址法必须用墓碑保住探测链的连续性。

墓碑多了会污染数组：明明没几个有效元素，探测却要走很远。所以开放寻址表需要定期 rehash，把墓碑清掉——这又牵出扩容。

扩容：不扩会崩，扩早了白费

不管哪种实现，负载因子超过阈值就必须扩容。链地址法阈值可以宽松一点（0.75 ~ 1.0），开放寻址法必须更紧（0.5 ~ 0.7），因为它的探测长度对负载因子非常敏感。

const MAX_LOAD: f64 = 0.7;

fn should_grow(len: usize, cap: usize) -> bool {
    (len as f64) / (cap as f64) > MAX_LOAD
}

扩容不是把数组变大就完事，而是所有元素重新分配。因为槽位下标是 hash % cap 算出来的，cap 一变，所有元素的落点全变。

    fn resize(&mut self, new_cap: usize) {
        let old = std::mem::replace(&mut self.slots, (0..new_cap).map(|_| Slot::Empty).collect());
        self.len = 0;
        for slot in old {
            if let Slot::Occupied(k, v) = slot {
                self.insert(k, v);
            }
        }
    }

这就是为什么哈希表会“突然卡一下”：扩容那一次要遍历全部元素重新插入。扩容成本是 O(n)，但它摊销到每次插入上只有 O(1)。这也是哈希表均摊复杂度能是 O(1) 的原因。

工程上有个容易被忽略的点：扩容倍数别用 * 2 这种偶数倍。如果哈希函数低位不够随机，用 2 的幂做容量会让冲突集中。标准库里用的是“质数容量 + 一次振动哈希（murmur finalizer）”，就是为了打散低位。

两个实现怎么选

维度	链地址法	开放寻址法
缓存友好度	差（指针跳转）	好（连续数组）
高负载因子表现	稳定退化	急剧恶化
删除	摘链即可	需要墓碑
内存开销	每个元素一个节点	无额外节点
典型场景	通用哈希表、负载不可控	高性能只读/低频删除表

一句话：写通用容器选链地址，做极致性能且删除少选开放寻址。

结论

自己写一遍哈希表，最大的收获不是“我会造 HashMap 了”，而是搞懂了三件事：

冲突必须有明确的解决策略；删除在开放寻址里需要墓碑；扩容成本是 O(n) 但摊销后是 O(1)。

下次再遇到“这个 map 怎么这么慢”，你至少知道去看负载因子和 key 的分布，而不是对着一行 map.get() 发呆。