深入剖析：C++ 手写实现 unordered_map 与 unordered_set 全流程指南

用户11289931

发布于 2025-08-18 08:31:02

18600

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

一、前言：STL 容器的魔法揭示

在现代 C++ 开发中，unordered_map 和 unordered_set 是开发者高频使用的数据结构。它们底层使用哈希表（hash table）实现，提供O(1) 平均复杂度的插入和查找，性能极高。

但作为工程师，不能只做容器的使用者，更要理解其背后的实现机制。

本文将从底层原理、SGI STL 源码出发，手动模拟并完整实现一套泛型、可扩展、支持迭代器的 unordered_map 与 unordered_set 容器。

二、STL 哈希容器的历史与演进

2.1 SGI STL 的哈希家族

早期 C++ 标准未引入哈希表类容器，SGI STL 率先推出 hash_map 与 hash_set，底层封装自定义 hashtable 类，广受欢迎。

但它们并非 C++ 标准的一部分，也不具备跨平台稳定性。

2.2 C++11 引入 unordered 容器

C++11 正式将 unordered_map、unordered_set 纳入 STL，头文件分别是：

#include <unordered_map>
#include <unordered_set>

标准库中 unordered_* 使用开放寻址或拉链法实现，底层逻辑与 SGI STL 类似。

三、深入源码：SGI STL 的 hashtable 架构

SGI STL 的 hash_map 与 hash_set 都建立在 hashtable 基础上。

// hash_map
class hash_map {
    typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht;
    ht rep;
};

核心结构体 __hashtable_node：

struct __hashtable_node {
    __hashtable_node* next; // 链表结构
    Value val;
};

hashtable 用链式结构（拉链法）处理哈希冲突，使用 vector<node*> 作为桶数组。

3.1 冲突解决方式

拉链法：每个桶中是一个链表，冲突项插入链表头部。
开放寻址法：若冲突则探测下一个空桶。

我们本次采用拉链法实现。

四、手写哈希表核心结构

4.1 HashNode：链表节点

template<class T>
struct HashNode {
    T _data;
    HashNode<T>* _next;
    HashNode(const T& data) : _data(data), _next(nullptr) {}
};

4.2 HashFunc：泛型哈希函数

template<class K>
struct HashFunc {
    size_t operator()(const K& key) const {
        return static_cast<size_t>(key); // 针对整数类型
    }
};

// string 特化
template<>
struct HashFunc<std::string> {
    size_t operator()(const std::string& key) const {
        size_t hash = 0;
        for (auto ch : key) hash = hash * 131 + ch;
        return hash;
    }
};

4.3 HashTable 模板定义

template<class K, class T, class KeyOfT, class Hash>
class HashTable {
    std::vector<HashNode<T>*> _tables;
    size_t _n; // 元素个数

public:
    bool Insert(const T& data);
    bool Erase(const K& key);
    Iterator Begin();
    Iterator End();
    void Expand();
};

五、Insert 插入函数 + 自动扩容

插入操作步骤：

使用哈希函数计算桶索引
遍历该桶链表判断是否已存在
若不存在则头插节点

template<class K, class T, class KeyOfT, class Hash>
bool HashTable<K, T, KeyOfT, Hash>::Insert(const T& data) {
    KeyOfT kot;
    Hash hs;
    size_t index = hs(kot(data)) % _tables.size();

    for (HashNode<T>* cur = _tables[index]; cur; cur = cur->_next) {
        if (kot(cur->_data) == kot(data)) return false;
    }

    if (_n >= _tables.size()) Expand();

    HashNode<T>* node = new HashNode<T>(data);
    node->_next = _tables[index];
    _tables[index] = node;
    ++_n;
    return true;
}

扩容策略：

void Expand() {
    static const size_t primes[] = {53, 97, 193, 389, 769, 1543, 3079, ...};
    size_t newSize = NextPrime(_tables.size() * 2);
    std::vector<HashNode<T>*> new_table(newSize, nullptr);

    for (auto head : _tables) {
        for (HashNode<T>* cur = head; cur; ) {
            HashNode<T>* next = cur->_next;
            size_t newIdx = hs(kot(cur->_data)) % newSize;
            cur->_next = new_table[newIdx];
            new_table[newIdx] = cur;
            cur = next;
        }
    }
    _tables.swap(new_table);
}

六、自定义 unordered_set 封装

namespace bit {
    template<class K, class Hash = HashFunc<K>>
    class unordered_set {
        struct SetKeyOfT {
            const K& operator()(const K& key) const { return key; }
        };

        hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;

    public:
        bool insert(const K& key) { return _ht.Insert(key); }
    };
}

测试用例：

bit::unordered_set<int> uset;
uset.insert(3);
uset.insert(7);

七、自定义 unordered_map 封装

namespace bit {
    template<class K, class V, class Hash = HashFunc<K>>
    class unordered_map {
        struct MapKeyOfT {
            const K& operator()(const std::pair<K, V>& kv) const { return kv.first; }
        };

        hash_bucket::HashTable<K, std::pair<K, V>, MapKeyOfT, Hash> _ht;

    public:
        bool insert(const std::pair<K, V>& kv) { return _ht.Insert(kv); }

        V& operator[](const K& key) {
            std::pair<K, V> kv(key, V());
            auto ret = _ht.Insert(kv);
            return const_cast<V&>(ret.first->_data.second);
        }
    };
}

用法示例：

bit::unordered_map<std::string, int> umap;
umap["apple"] = 5;

八、自定义迭代器支持

迭代器功能：

支持 for(auto it = begin(); it != end(); ++it)
封装当前节点和哈希表指针

template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator {
    HashNode<T>* _node;
    const HashTable<K, T, KeyOfT, Hash>* _pht;

    Ref operator*() const { return _node->_data; }
    Self& operator++() {
        if (_node->_next) _node = _node->_next;
        else 查找下一个桶...
        return *this;
    }
};

九、operator[] 与 key const 限定

9.1 为什么 key 不可修改？

key 决定元素的哈希位置，修改后会导致元素定位混乱。STL 使用 pair<const K, V> 来防止 key 被误改。

9.2 operator[] 实现

V& operator[](const K& key) {
    pair<K, V> kv(key, V());
    auto ret = _ht.Insert(kv);
    return const_cast<V&>(ret.first->_data.second);
}

十、总结与建议

本文从 STL 历史入手，完整实现了通用哈希表，并基于此分别封装了 unordered_map 和 unordered_set。

通过本项目，你掌握了：

哈希表的链式冲突处理
泛型模板 + 仿函数提取 key
插入、查找、扩容的底层实现
迭代器与 const 设计的注意事项

推荐练习：实现 erase()、支持 load_factor、自定义 load 控制、支持迭代器 range-for 等

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-18，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度