手写 std::unordered_map

手写 std::unordered_map

在哈希内核上实现键值映射、try_emplace、operator[] 和可控 rehash。

本系列代码使用 C++20 和 oc::handmade 命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。

---

一、学习目标

• 实现唯一键哈希映射
• 避免命中时无谓构造 mapped value
• 理解 rehash 对迭代器与引用的不同影响

---

二、前置条件

完成 unordered_set 与 map 篇。

Linux/macOS：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure

Windows PowerShell：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

---

三、问题与设计选择

节点保存 Key 和 T；查找先计算一次哈希并在节点中缓存。try_emplace 只在确认缺失后构造 T。

这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。

---

四、内存布局与核心不变量

KeyEqual 等价键唯一；修改 T 不改变桶归属；rehash 只重连节点。

每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。

---

五、核心实现

template<class... Args>
std::pair<T*, bool> try_emplace(Key key, Args&&... args) {
    const auto hash = hash_(key);
    if (auto* old = table_.find(hash, key, equal_))
        return {&old->mapped, false};
    auto* fresh = table_.emplace(
        hash, std::move(key), T(std::forward<Args>(args)...));
    return {&fresh->mapped, true};
}

上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。

---

六、完整教学实现

下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。

namespace oc::handmade {

template<class Key, class T, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>>
class unordered_map {
    struct node {
        std::size_t hash;
        Key key;
        T value;
        std::unique_ptr<node> next;
        node(std::size_t hash_value, Key key_value, T mapped)
            : hash(hash_value), key(std::move(key_value)), value(std::move(mapped)) {}
    };
    std::vector<std::unique_ptr<node>> buckets_;
    std::size_t size_{};
    float max_load_{1.0F};
    Hash hash_{};
    Equal equal_{};

    std::size_t bucket(std::size_t hash) const noexcept { return hash % buckets_.size(); }
    void maybe_rehash() {
        const long double projected = static_cast<long double>(size_ + 1);
        const long double threshold =
            static_cast<long double>(buckets_.size()) *
            static_cast<long double>(max_load_);
        if (projected > threshold)
            rehash(buckets_.size() * 2);
    }

public:
    explicit unordered_map(std::size_t buckets = 8)
        : buckets_(std::max<std::size_t>(1, buckets)) {}
    unordered_map(unordered_map&&) noexcept = default;
    unordered_map& operator=(unordered_map&&) noexcept = default;
    unordered_map(const unordered_map&) = delete;
    unordered_map& operator=(const unordered_map&) = delete;
    std::size_t size() const noexcept { return size_; }
    bool empty() const noexcept { return size_ == 0; }
    std::size_t bucket_count() const noexcept { return buckets_.size(); }
    float load_factor() const noexcept {
        return static_cast<float>(size_) / static_cast<float>(buckets_.size());
    }
    T* find(const Key& key) {
        const auto hashed = hash_(key);
        for (node* current = buckets_[bucket(hashed)].get(); current; current = current->next.get())
            if (current->hash == hashed && equal_(current->key, key)) return &current->value;
        return nullptr;
    }
    const T* find(const Key& key) const { return const_cast<unordered_map*>(this)->find(key); }
    bool contains(const Key& key) const { return find(key) != nullptr; }
    std::pair<T*, bool> insert(Key key, T value) {
        if (T* old = find(key)) return {old, false};
        maybe_rehash();
        const auto hashed = hash_(key);
        const auto index = bucket(hashed);
        auto fresh = std::make_unique<node>(hashed, std::move(key), std::move(value));
        T* result = &fresh->value;
        fresh->next = std::move(buckets_[index]);
        buckets_[index] = std::move(fresh);
        ++size_;
        return {result, true};
    }
    T& operator[](Key key) {
        if (T* old = find(key)) return *old;
        return *insert(std::move(key), T{}).first;
    }
    bool erase(const Key& key) {
        const auto hashed = hash_(key);
        auto* link = &buckets_[bucket(hashed)];
        while (*link) {
            if ((*link)->hash == hashed && equal_((*link)->key, key)) {
                *link = std::move((*link)->next);
                --size_;
                return true;
            }
            link = &(*link)->next;
        }
        return false;
    }
    void rehash(std::size_t requested) {
        std::vector<std::unique_ptr<node>> fresh(std::max<std::size_t>(1, requested));
        for (auto& chain : buckets_) {
            while (chain) {
                auto current = std::move(chain);
                chain = std::move(current->next);
                const auto index = current->hash % fresh.size();
                current->next = std::move(fresh[index]);
                fresh[index] = std::move(current);
            }
        }
        buckets_ = std::move(fresh);
    }
};

}  // namespace oc::handmade

生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。

---

七、使用示例与输出

预期输出或状态：

两次 try_emplace 同一键只构造一次值；命中时返回已有值和 false。

示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。

---

八、复杂度与失效规则

操作	复杂度	说明
operator[]/find	平均 O(1)	operator[] 可插入
try_emplace	平均 O(1)	延迟构造 T
erase	平均 O(1)	断开单链
reserve/rehash	O(n)	迭代器失效

复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。

---

九、异常安全与资源管理

• 获取资源后立即交给 RAII 对象或明确记录已构造数量。
• 用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
• 只有在所有后续步骤不会失败时才修改不可回滚的链接。
• 析构、释放和关闭路径不得抛异常。
• 并发包装通过回调在锁内访问，避免返回保护对象的裸引用。

---

十、常见错误

1. 先构造 T 再检查键是否存在

先构造 T 再检查键是否存在会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. erase 单链节点时丢失前驱

erase 单链节点时丢失前驱会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 认为 reserve 参数就是桶数

认为 reserve 参数就是桶数会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

---

十一、面试追问

1. 为什么 try_emplace 对昂贵值更友好？
2. 开放寻址能否保持引用稳定？
3. 缓存 hash 值的收益与成本是什么？

回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。

---

十二、练习与自测

1. 实现 insert_or_assign
2. 添加 node_handle 思路说明
3. 随机差分测试 std::unordered_map

自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。

---

十三、官方资料与延伸阅读

• C++20 工作草案 N4861
• C++ Core Guidelines

---

上一篇：手写 std::unordered_set ｜ 下一篇：手写 std::unique_ptr