C++算法
C++ 哈希表封装：模拟实现 unordered_map 和 unordered_set
C++ 哈希表封装技术详解，通过源码分析讲解 unordered_map 和 unordered_set 的模拟实现。内容涵盖哈希表框架复用、迭代器单向遍历逻辑、KeyOfT 仿函数设计以支持 Key 提取、扩容机制及重载 [] 运算符。提供完整的 HashTable、unordered_set 和 unordered_map 头文件代码及测试用例，展示插入、查找、删除功能。
C++ 哈希表封装技术详解，通过源码分析讲解 unordered_map 和 unordered_set 的模拟实现。内容涵盖哈希表框架复用、迭代器单向遍历逻辑、KeyOfT 仿函数设计以支持 Key 提取、扩容机制及重载 [] 运算符。提供完整的 HashTable、unordered_set 和 unordered_map 头文件代码及测试用例，展示插入、查找、删除功能。
非官方文档：cplusplus
官方文档（同步更新）：C++ 官方参考文档
set 和 multiset 的参考文档：set、multiset
map 和 multimap 的参考文档：map、multimap
unordered_set 和 unordered_multiset 的参考文档：unordered_set、unordered_multiset
unordered_map 和 unordered_multimap 的参考文档：unordered_map、unordered_multimap
SGI-STL30 版本源代码中没有 unordered_map 和 unordered_set，这两个容器是 C++11 之后才更新的。但是 SGI-STL30 实现了哈希表，容器的名字是 hash_map 和 hash_set，作为非标准的容器出现。
源代码在 hash_map/hash_set / stl_hash_map / stl_hash_set / stl_hashtable.h 中。hash_map 和 hash_set 的实现结构框架核心部分如下：
// stl_hash_set
template <class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, class Alloc = alloc>
class hash_set {
private:
typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::const_iterator iterator;
typedef typename ht::const_iterator const_iterator;
hasher hash_funct() const { return rep.hash_funct(); }
key_equal key_eq() const { return rep.key_eq(); }
};
// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc>
class hash_map {
private:
typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef T data_type;
typedef T mapped_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::iterator iterator;
typedef typename ht::const_iterator const_iterator;
};
// stl_hashtable.h
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
class hashtable {
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher;
typedef EqualKey key_equal;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node;
vector<node*, Alloc> buckets;
size_type num_elements;
public:
typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
pair<iterator, bool> insert_unique(const value_type& obj);
const_iterator find(const key_type& key) const;
};
template <class Value> struct __hashtable_node {
__hashtable_node* next;
Value val;
};
通过源码可以看到，结构上 hash_map 和 hash_set 跟 map 和 set 完全类似，复用同一个 hashtable 实现 key 和 key/value 结构。hash_set 传给 hash_table 的是两个 key，hash_map 传给 hash_table 的是 pair<const key, value>。
需要注意的是源码里面跟 map/set 源码类似，命名风格比较乱。下面我们会自己实现一下，统一按自己的风格来。
参考源码框架，unordered_map 和 unordered_set 复用之前实现的哈希表。这里相比源码调整一下，key 参数就用 K，value 参数就用 V，哈希表中的数据类型使用 T。
因为 HashTable 实现了泛型不知道 T 参数导致是 K，还是 pair<K,V>，那么 insert 内部进行插入时要用 K 对象转换成整形取模和 K 比较相等。因为 pair 的 value 不参与计算取模，且默认支持的是 key 和 value 一起比较相等，我们需要的是任何时候只需要比较 K 对象。所以我们在 unordered_map 和 unordered_set 层分别实现一个 MapKeyOfT 和 SetKeyOfT 的仿函数传给 HashTable 的 KeyOfT，然后 HashTable 中通过 KeyOfT 仿函数取出 T 类型对象中的 K 对象，再转换成整形取模和 K 比较相等。
iterator 实现的大框架跟 list 的 iterator 思路一致，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为。要注意的是哈希表的迭代器是单向迭代器。
难点在于 operator++ 的实现。iterator 中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点是结构设计的问题，参考上面的源码，我们可以看到 iterator 中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用 key 值计算出当前桶位置，依次往后找下一个不为空的桶。
begin() 返回第一个桶中第一个节点指针构造的迭代器，end() 返回迭代器可以用空表示。
unordered_set 的迭代器不支持修改，把 unordered_set 的第二个模板参数改成 const K 即可：
HashTable<K, const K, SetKeyOfT, Hash>_ht;
unordered_map 的 iterator 不支持修改 key 但是可以修改 value，我们把 unordered_map 的第二个模板参数 pair 的第一个参数改成 const K 即可：
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
当然，支持完整的迭代器还有很多细节需要修改。
unordered_map 要支持 [] 主要需要修改 insert 返回值支持，修改 HashTable 中的 insert 返回值为：
pair<Iterator, bool> Insert(const T& data);
有了 insert，支持 [] 实现就很简单了。
#pragma once
#include<vector>
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 };
inline unsigned long __stl_next_prime(unsigned long n) {
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
// >= n
const unsigned long* pos = (first, last, n);
pos == last ? *(last - ) : *pos;
}
< > {
{
()key;
}
};
<> <string> {
{
hash = ;
( ch : key) {
hash += ch;
hash *= ;
}
hash;
}
};
Hash_bucket {
< > {
T _data;
HashNode<T>* _next;
( T& data) :_data(data), _next() {}
};
< , , , > ;
< , , , , , >
{
HashNode<T> Node;
HashTable<K, T, KeyOfT, Hash> HT;
HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
HT* _pht;
(Node* node, HT* pht) :_node(node), _pht(pht) {}
Ref *() { _node->_data; }
Ptr ->() { &_node->_data; }
Self& ++() {
(_node->_next)
{
_node = _node->_next;
}
{
KeyOfT kot;
Hash hs;
hashi = ((_node->_data)) % _pht->_tables.();
++hashi;
(hashi < _pht->_tables.()) {
(_pht->_tables[hashi])
{
_node = _pht->_tables[hashi];
;
}
{
++hashi;
}
}
(hashi == _pht->_tables.())
{
_node = ;
}
}
*;
}
!=( Self & s) { _node != s._node; }
==( Self & s) { _node == s._node; }
};
< , , , > {
< , , , , , >
;
HashNode<T> Node;
:
HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
HTIterator<K, T, T&, T*, KeyOfT, Hash> ConstIterator;
{
(_n == ) { (); }
( i = ; i < _tables.(); i++) {
(_tables[i]) { (_tables[i], ); }
}
();
}
{ (, ); }
{
(_n == ) { (); }
( i = ; i < _tables.(); i++) {
(_tables[i]) { (_tables[i], ); }
}
();
}
{ (, ); }
() :_tables(__stl_next_prime(),),_n() {}
~() {
( i = ; i < _tables.(); i++) {
Node* cur = _tables[i];
(cur) {
Node* next = cur->_next;
cur;
cur = next;
}
_tables[i] = ;
}
_n = ;
}
{
KeyOfT kot;
( it = ((data)); it != ()) { it, };
Hash hs;
(_n == _tables.()) {
;
( i = ; i < _tables.(); i++) {
Node* cur = _tables[i];
(cur) {
Node* next = cur->_next;
hashi = ((cur->_data)) % newtables.();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = ;
}
_tables.(newtables);
}
hashi = ((data)) % _tables.();
Node* newnode = (data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
{ (newnode,), };
}
{
KeyOfT kot;
Hash hs;
hashi = (key) % _tables.();
Node* cur = _tables[hashi];
(cur) {
((cur->_data) == key) { { cur, }; }
cur = cur->_next;
}
{ , };
}
{
KeyOfT kot;
Hash hs;
hashi = (key) % _tables.();
Node* prev = ;
Node* cur = _tables[hashi];
(cur) {
((cur->_data) == key) {
(prev == ) {
_tables[hashi] = cur->_next;
}
{
prev->_next = cur->_next;
}
--_n;
cur;
;
}
prev = cur;
cur = cur->_next;
}
;
}
:
std::vector<Node*> _tables;
_n;
};
}
#pragma once
#include"HashTable.h"
namespace jqj {
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, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename Hash_bucket::HashTable<K, const 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) { return _ht.Insert(key); }
{ _ht.(key); }
{ _ht.(key); }
:
Hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}
#pragma once
#include"HashTable.h"
namespace jqj {
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<const K,V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename Hash_bucket::HashTable<K, pair<const 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) { _ht.(kv); }
V& []( K& key) {
pair<iterator, > ret = _ht.((key, ()));
ret.first->second;
}
{ _ht.(key); }
{ _ht.(key); }
:
Hash_bucket::HashTable<K, pair< K, V>, MapKeyOfT, Hash> _ht;
};
}
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
using namespace std;
#include"unordered_map.h"
#include"unordered_set.h"
void Print(const jqj::unordered_set<int>& s) {
jqj::unordered_set<int>::const_iterator it = s.begin();
while (it != s.end()) {
// it* = 1; // 迭代器不能被修改
cout << *it << " ";
++it;
}
cout << endl;
}
int main() {
jqj::unordered_set<int> us;
us.insert(3);
us.insert(1000);
us.insert(2);
us.insert(102);
us.insert(2111);
us.insert(22);
jqj::unordered_set<int>::iterator it = us.begin();
while (it != us.end()) {
//*it = 1; // 不能被修改
cout << *it << " ";
++it;
}
cout << endl;
Print(us);
jqj::unordered_map<string, string> dict;
dict.({ , });
dict.({ , });
dict.({ , });
dict.({ , });
dict[] = ;
dict[];
dict[] = ;
(& [k, v] : dict) {
cout << k << << v << endl;
}
;
}
运行结果正常输出插入和查找的数据。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online