当前位置：首页 > news >正文

C++ 手写哈希表（开放定址法 + 链地址法）+ 封装 unordered_map/unordered_set，从原理到工程级实现

news 2026/4/27 7:55:20

前言

哈希表（Hash Table）是计算机世界中平均 O (1) 查找、插入、删除的最强数据结构。C++ 标准库中的unordered_map/unordered_set底层正是基于哈希表实现。但绝大多数同学只会用，不懂原理；只会调库，不会手写。

本文带你从零搭建：

哈希表核心理论（哈希函数、冲突、负载因子、扩容）
开放定址法（线性探测、二次探测）完整实现
链地址法（哈希桶）完整实现（最接近 STL 标准）
迭代器封装、const 正确性、模板泛型
基于哈希桶封装unordered_map/unordered_set
性能对比、踩坑总结、面试高频考点

全文代码均在 VS2022 下测试通过，可直接复制使用。

一、哈希表基础概念（必须吃透）

1.1 什么是哈希表

哈希表通过哈希函数将关键字key映射到数组下标，从而实现直接寻址。映射关系：

下标 = hash(key) % 表大小

理想情况下：

插入：O (1)
查找：O (1)
删除：O (1)

这就是哈希表 “无敌” 的原因。

1.2 哈希冲突（不可避免）

不同 key 可能算出相同下标，称为哈希冲突 / 哈希碰撞。任何哈希函数都无法彻底避免冲突，只能减少冲突。

冲突两大解决方案：

开放定址法（闭散列）：数据存在表内，冲突向后找空位
链地址法（开散列 / 哈希桶）：每个位置挂链表，冲突往链上放

1.3 负载因子（性能命脉）

负载因子α = 已存元素个数 / 哈希表总长度

α 越大 → 冲突越多 → 效率越低
α 越小 → 冲突越少 → 空间浪费越多

常规控制：

开放定址法：α ≤ 0.7
链地址法：α ≤ 1.0（STL 默认）

1.4 哈希函数设计（均匀散列是关键）

常见哈希函数：

直接定址法：hash(key)=key
除留余数法：hash(key) = key % capacity（最常用）
平方取中法、折叠法、随机数法
字符串哈希（BKDR、FNV、MurmurHash）

二、开放定址法（闭散列）实现

2.1 原理

所有数据存在同一张数组中。冲突时向后寻找空位：

线性探测：hash_i = (hash0 + i) % cap
二次探测：hash_i = (hash0 ± i²) % cap

必须给每个位置加状态标记：

EMPTY 空
EXIST 存在
DELETE 已删除（解决删除后查找断链问题）

2.2 结构定义

enum State { EXIST, EMPTY, DELETE }; template<class K, class V> struct HashData { pair<K, V> _kv; State _state = EMPTY; };

2.3 素数表（扩容用）

哈希表容量必须用质数，能显著降低冲突率。

inline unsigned long _stl_next_prime(unsigned long n) { static const int __stl_num_primes = 28; static const unsigned long __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; for (int i = 0; i < __stl_num_primes; ++i) { if (__stl_prime_list[i] > n) return __stl_prime_list[i]; } return __stl_prime_list[__stl_num_primes - 1]; }

2.4 哈希函数（支持 string）

template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct HashFunc<string> { size_t operator()(const string& s) { size_t hash = 0; for (auto ch : s) { hash = hash * 131 + ch; } return hash; } };

2.5 开放定址法完整实现

namespace open_address { template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable() { _tables.resize(_stl_next_prime(0)); } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; if (_n * 10 / _tables.size() >= 7) { HashTable newHT; newHT._tables.resize(_stl_next_prime(_tables.size())); for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]._state == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } Hash hash; size_t hash0 = hash(kv.first) % _tables.size(); size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state == EXIST) { hashi = (hash0 + i) % _tables.size(); ++i; } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return true; } HashData<K, V>* Find(const K& key) { Hash hash; size_t hash0 = hash(key) % _tables.size(); size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } hashi = (hash0 + i) % _tables.size(); ++i; } return nullptr; } bool Erase(const K& key) { auto ret = Find(key); if (ret == nullptr) return false; ret->_state = DELETE; --_n; return true; } private: vector<HashData<K, V>> _tables; size_t _n = 0; }; }

2.6 优点与缺陷

✅ 优点：连续内存、缓存友好、无指针开销❌ 缺陷：冲突堆积明显、删除复杂、负载因子不能太高

三、链地址法（哈希桶）—— STL 标准实现

3.1 原理（最常用、最稳定）

哈希表 =指针数组每个位置是一条链表（桶）冲突 → 直接插入桶中

负载因子可以到 1.0 才扩容。

3.2 节点结构

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

3.3 迭代器设计（核心难点）

3.3.1 为什么要用迭代器

封装内部节点，不暴露实现
统一 STL 风格接口
支持范围 for、STL 算法
支持 const 迭代器

3.3.2 迭代器结构

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct HTIterator { typedef HashNode<T> Node; typedef HashTable<K, T, KeyOfT, Hash> HT; typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self; Node* _node; const HT* _ht; HTIterator(Node* node, const HT* ht) :_node(node) ,_ht(ht) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) const { return _node != s._node; } Self& operator++() { if (_node->_next) { _node = _node->_next; } else { KeyOfT kot; Hash hash; size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size(); ++hashi; while (hashi < _ht->_tables.size() && _ht->_tables[hashi] == nullptr) { ++hashi; } if (hashi == _ht->_tables.size()) { _node = nullptr; } else { _node = _ht->_tables[hashi]; } } return *this; } };

3.3.3 为什么迭代器必须存`this`（哈希表指针）

因为++要跨桶遍历，必须知道桶数组的位置。不传 this，迭代器无法实现！

3.4 哈希表完整实现

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> class HashTable { template<class K1, class T1, class Ref, class Ptr, class KeyOfT1, class Hash1> friend struct HTIterator; typedef HashNode<T> Node; public: typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator; typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator; Iterator Begin() { for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) return Iterator(_tables[i], this); } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin() const { for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) return ConstIterator(_tables[i], this); } return End(); } ConstIterator End() const { return ConstIterator(nullptr, this); } HashTable() :_tables(_stl_next_prime(0)) ,_n(0) {} ~HashTable() { for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } bool Insert(const T& data) { KeyOfT kot; Hash hash; if (Find(kot(data))) return false; if (_n == _tables.size()) { vector<Node*> newTable(_stl_next_prime(_tables.size())); for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = hash(kot(cur->_data)) % newTable.size(); cur->_next = newTable[hashi]; newTable[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTable); } size_t hashi = hash(kot(data)) % _tables.size(); Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; } Node* Find(const K& key) { KeyOfT kot; Hash hash; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return cur; cur = cur->_next; } return nullptr; } bool Erase(const K& key) { KeyOfT kot; Hash hash; size_t hashi = hash(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { if (prev == nullptr) { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; size_t _n = 0; }; }

四、封装 unordered_map（最接近 STL）

4.1 核心设计：KeyOfT 仿函数

用于从pair<K,V>中提取 key。

namespace hiro { template<class K, class V, class Hash = HashFunc<K>> class unordered_map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: typedef typename hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash>::Iterator iterator; typedef typename hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } pair<iterator, bool> insert(const pair<K, V>& kv) { bool ret = _ht.Insert(kv); return { iterator(_ht.Find(kv.first)), ret }; } private: hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht; }; }

4.2 为什么必须加`typename`

在模板中，编译器无法识别HashTable<...>::Iterator是类型还是变量。typename明确告诉编译器：这是一个类型。

五、封装 unordered_set（与 map 同理）

namespace hiro { template<class K, class Hash = HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::Iterator iterator; typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::ConstIterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } pair<iterator, bool> insert(const K& key) { bool ret = _ht.Insert(key); return { iterator(_ht.Find(key)), ret }; } private: hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht; }; }

六、测试代码

#include <iostream> #include <string> #include "unordered_map.h" #include "unordered_set.h" using namespace std; using namespace hiro; int main() { // unordered_map 测试 unordered_map<string, string> dict; dict.insert({ "apple", "苹果" }); dict.insert({ "hash", "哈希" }); dict.insert({ "map", "映射" }); for (auto& kv : dict) { cout << kv.first << " : " << kv.second << endl; } // unordered_set 测试 unordered_set<int> s; s.insert(1); s.insert(2); s.insert(3); for (auto x : s) { cout << x << " "; } cout << endl; return 0; }