C++ 手写实现 unordered_map 和 unordered_set：深入解析与源码实战

用户11289931

发布于 2025-06-11 11:13:06

20000

代码可运行

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

运行总次数：0

代码可运行

一、前言

在 C++ 的标准模板库（STL）中，unordered_map 和 unordered_set 是两个常用的哈希容器，它们在底层以哈希表作为数据结构实现，拥有常数时间复杂度的插入和查找性能。然而，这些强大容器的底层是如何构建的？本博客将带你从源码出发，亲手实现一套 unordered_map 和 unordered_set，并解析每一行背后的设计思考。

通过本博客你将掌握：

哈希表的基本实现原理
unordered_map 与 unordered_set 的区别与联系
如何自定义哈希函数与迭代器
STL 源码设计的灵活性与泛型思想

博文全长预计超过 10,000 字，建议收藏学习。

二、STL 哈希容器的演进

2.1 SGI STL 与 C++11

早期的 SGI STL 中并没有 unordered_map 和 unordered_set，而是提供了 hash_map 和 hash_set 作为扩展容器。它们并不属于 C++ 标准委员会制定的 STL 标准库，而是由 SGI 组织实现并广泛流传。

随着 C++11 的到来，unordered_map 和 unordered_set 正式成为标准容器，被纳入 <unordered_map> 与 <unordered_set> 头文件中。

2.2 `hash_map` 和 `unordered_map` 对比

虽然名字不同，但结构设计和使用方式高度类似，都依赖底层的哈希表实现。不过由于 unordered_map 是 C++11 正式标准的一部分，因此更具可移植性和规范性。

三、SGI STL 哈希容器源码结构分析

SGI STL 的 hash_map 和 hash_set 都基于通用模板类 hashtable 实现，示例如下：

// hash_set
class hash_set {
    typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
    ht rep;
};

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

底层哈希表结构：

struct __hashtable_node {
    __hashtable_node* next;
    Value val;
};

class hashtable {
    vector<node*> buckets;
    size_t num_elements;
};

SGI STL 使用链表处理冲突，即“拉链法”。

四、从零构建哈希表框架

4.1 哈希节点结构

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

4.2 哈希函数定义

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 (char ch : key) hash = hash * 131 + ch;
        return hash;
    }
};

4.3 哈希表接口结构

template<class K, class T, class KeyOfT, class Hash>
class HashTable {
    vector<HashNode<T>*> _tables;
    size_t _n;

public:
    bool Insert(const T& data);
    Iterator Begin();
    Iterator End();
};

五、实现插入逻辑与扩容机制

插入的基本步骤如下：

用哈希函数求出索引
查找是否已存在该 key
若不存在则头插法插入
若负载因子达到阈值，执行扩容

扩容逻辑采用“下一个质数原则”，以尽可能减少冲突。

六、封装 unordered_set 与 unordered_map

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); }
    };
}

namespace bit {
    template<class K, class V, class Hash = HashFunc<K>>
    class unordered_map {
        struct MapKeyOfT {
            const K& operator()(const pair<K, V>& kv) const { return kv.first; }
        };
        hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
    public:
        bool insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
        V& operator[](const K& key) {
            pair<K, V> kv(key, V());
            auto ret = _ht.Insert(kv);
            return const_cast<V&>(ret.first->_data.second);
        }
    };
}

七、自定义迭代器的设计与实现

unordered_* 的迭代器是单向的（ForwardIterator）。其逻辑包括：

遍历链表节点 _next
若当前桶走完，跳到下一个非空桶

定义如下：

template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator {
    Node* _node;
    const HashTable<K, T, KeyOfT, Hash>* _pht;
    HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht);
    Ref operator*() const;
    Ptr operator->() const;
    Self& operator++();
    bool operator!=(const Self& s) const;
};

配合 Begin() 和 End() 实现遍历：

for (auto it = s.begin(); it != s.end(); ++it)
    cout << *it << endl;

八、operator[] 的支持与 Key 不可修改约束

8.1 为什么 key 不可修改？

哈希表中 key 决定了数据的桶位置，如果允许修改 key，可能导致哈希结构紊乱。因此标准库中使用 pair<const K, V>。

8.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);
}

8.3 对比 insert 与 []

特性	insert(kv)	operator[]
功能	插入（存在返回 false）	查找或插入
返回值	pair<it, bool>	value 引用
修改 key	否	否
修改 value	需要迭代器访问 second	支持

九、扩容机制与性能调优建议

9.1 扩容策略：质数数组

采用质数作为哈希桶数量有助于减少哈希冲突。

static const size_t prime_list[] = {
  53, 97, 193, 389, 769, 1543, 3079,
  6151, 12289, 24593, 49157, 98317, 196613
};

9.2 负载因子 (load factor)

常设阈值为 1.0，当元素个数达到桶总数时扩容，可动态调整：

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

9.3 哈希冲突优化

自定义哈希函数（如 BKDRHash）
增加桶数量，减少冲突链长度
使用链表以外的冲突解决（如开放定址）

十、总结

本博客从 STL 哈希容器的历史出发，逐步带你实现 unordered_map 和 unordered_set，涵盖了：

哈希表的构建逻辑
模板泛型与仿函数提取 key
insert、[] 和迭代器的完整支持
key 不可修改原则与性能优化建议

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

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

源码

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

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

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

登录后参与评论

0 条评论

热度