网站导航
> 技术文档 > 深入剖析：C++ 手写实现 unordered_map 与 unordered_set 全流程指南_C++ STL哈希容器源码解析

深入剖析：C++ 手写实现 unordered_map 与 unordered_set 全流程指南_C++ STL哈希容器源码解析

网友: 技术文档 2025-09-02 23:17:24

目录

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

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

2.1 SGI STL 的哈希家族

2.2 C++11 引入 unordered 容器

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

3.1 冲突解决方式

四、手写哈希表核心结构

4.1 HashNode：链表节点

4.2 HashFunc：泛型哈希函数

4.3 HashTable 模板定义

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

六、自定义 unordered_set 封装

七、自定义 unordered_map 封装

八、自定义迭代器支持

九、operator[] 与 key const 限定

9.1 为什么 key 不可修改？

9.2 operator[] 实现

十、总结与建议

一、前言：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 #include

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

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

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

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

核心结构体 __hashtable_node：

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

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

3.1 冲突解决方式

  • 拉链法：每个桶中是一个链表，冲突项插入链表头部。

  • 开放寻址法：若冲突则探测下一个空桶。

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

四、手写哈希表核心结构

4.1 HashNode：链表节点

templatestruct HashNode { T _data; HashNode* _next; HashNode(const T& data) : _data(data), _next(nullptr) {}};

4.2 HashFunc：泛型哈希函数

templatestruct HashFunc { size_t operator()(const K& key) const { return static_cast(key); // 针对整数类型 }};// string 特化templatestruct HashFunc { 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 模板定义

templateclass HashTable { std::vector<HashNode*> _tables; size_t _n; // 元素个数public: bool Insert(const T& data); bool Erase(const K& key); Iterator Begin(); Iterator End(); void Expand();};

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

插入操作步骤：

  1. 使用哈希函数计算桶索引

  2. 遍历该桶链表判断是否已存在

  3. 若不存在则头插节点

templatebool HashTable::Insert(const T& data) { KeyOfT kot; Hash hs; size_t index = hs(kot(data)) % _tables.size(); for (HashNode* cur = _tables[index]; cur; cur = cur->_next) { if (kot(cur->_data) == kot(data)) return false; } if (_n >= _tables.size()) Expand(); HashNode* node = new HashNode(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*> new_table(newSize, nullptr); for (auto head : _tables) { for (HashNode* cur = head; cur; ) { HashNode* 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> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) const { return key; } }; hash_bucket::HashTable _ht; public: bool insert(const K& key) { return _ht.Insert(key); } };}

测试用例：

bit::unordered_set uset;uset.insert(3);uset.insert(7);

七、自定义 unordered_map 封装

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

用法示例：

bit::unordered_map umap;umap[\"apple\"] = 5;

八、自定义迭代器支持

迭代器功能：

  • 支持 for(auto it = begin(); it != end(); ++it)

  • 封装当前节点和哈希表指针

templatestruct HTIterator { HashNode* _node; const HashTable* _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 来防止 key 被误改。

9.2 operator[] 实现

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

十、总结与建议

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

通过本项目，你掌握了：

  • 哈希表的链式冲突处理

  • 泛型模板 + 仿函数提取 key

  • 插入、查找、扩容的底层实现

  • 迭代器与 const 设计的注意事项

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

欢迎评论区与我交流！

清水丽人化妆品

网络标签：

相关问题