跳到主要内容C++ unordered_set/map 底层封装与模拟实现 | 极客日志C++算法
C++ unordered_set/map 底层封装与模拟实现
C++ unordered_set 和 unordered_map 基于哈希表实现。文章分析了 SGI-STL 中 hash_map/hash_set 的源码结构，对比了 map/set 的差异。通过模拟实现展示了哈希表的框架搭建、insert 操作、迭代器支持（单向迭代器）、重载 [] 运算符以及扩容机制。重点讲解了 KeyOfT 仿函数的使用、链地址法处理冲突、负载因子控制以及桶数组扩容逻辑。
DataScient0 浏览 unordered_set/map 封装实现
1. 源码及框架分析
SGI-STL30 版本源代码中没有 unordered_map 和 unordered_set，SGI-STL30 版本是 C++11 之前的 STL 版本，这两个容器是 C++11 之后才更新的。但是 SGI-STL30 实现了哈希表，只容器的名字是 hash_map 和 hash_set，他是作为非标准的容器出现的，非标准是指非 C++ 标准规定必须实现的。
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(); }
};
template<class Key, class T, = hash<Key>, EqualKey = equal_to<Key>, Alloc = alloc>
hash_map {
:
hashtable<pair< Key, T>, Key, HashFcn, select1st<pair< Key, T>>, EqualKey, Alloc> ht;
ht rep;
:
ht::key_type key_type;
T data_type;
T mapped_type;
ht::value_type value_type;
ht::hasher hasher;
ht::key_equal key_equal;
ht::iterator iterator;
ht::const_iterator const_iterator;
};
< , , , , , >
{
:
Key key_type;
Value value_type;
HashFcn hasher;
EqualKey key_equal;
:
hasher hash;
key_equal equals;
ExtractKey get_key;
__hashtable_node<Value> node;
vector<node*, Alloc> buckets;
size_type num_elements;
:
__hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
;
;
};
< >
{
__hashtable_node* next;
Value val;
};
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
class
HashFcn
class
class
class
private
typedef
const
const
public
typedef
typename
typedef
typedef
typedef
typename
typedef
typename
typedef
typename
typedef
typename
typedef
typename
template
class
Value
class
Key
class
HashFcn
class
ExtractKey
class
EqualKey
class
Alloc
class
hashtable
public
typedef
typedef
typedef
typedef
private
typedef
public
typedef
pair<iterator, bool> insert_unique(const value_type& obj)
const_iterator find(const key_type& key) const
template
class
Value
struct
__hashtable_node
• 通过源码可以看到，结构上 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 源码类似，命名风格比较乱，这里比 map 和 set 还乱，hash_set 模板参数居然用的 Value 命名，hash_map 用的是 Key 和 T 命名。
2. 模拟实现 unordered_map 和 unordered_set
2.1 实现出复用哈希表的框架，并支持 insert
• 参考源码框架，unordered_map 和 unordered_set 复用之前我们实现的哈希表。
• 我们这里相比源码调整一下，key 参数就用 K，value 参数就用 V，哈希表中的数据类型，我们使用 T。
• 其次跟 map 和 set 相⽐⽽⾔ unordered_map 和 unordered_set 的模拟实现类结构更复杂一点，但是大框架和思路是完全类似的。因为 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 比较相等，具体细节参考如下代码实现。
template<class K, class T, class Hashturn = Hashturn<K>>
class unordered_map {
struct KeyofT {
const K& operator()(const pair<K, T>& kv) { return kv.first; }
};
public:
bool insert(const pair<K, T>& kv) { return _ht.insert(kv); }
private:
hash_bucket<K, pair<const K, T>, KeyofT, Hashturn> _ht;
};
template<class K, class Hashturn = Hashturn<K>>
class unordered_set {
struct KeyofT {
const K& operator()(const K& kv) { return kv; }
};
public:
bool insert(const K& kv) { return _ht.insert(kv); }
private:
hash_bucket<K, const K, KeyofT, Hashturn> _ht;
};
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
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class T>
struct Bucket_Node {
T _data;
Bucket_Node<T>* _next;
Bucket_Node(const T& data) : _data(data), _next(nullptr) {}
};
template<class K>
struct Hashturn {
size_t operator()(const K& key) { return (size_t)key; }
};
template<>
struct Hashturn<string> {
size_t operator()(const string& key) {
size_t m = 0;
for (auto& e : key) {
m += e;
}
return m;
}
};
template<class K, class T, class KeyofT, class Hashturn>
class hash_bucket;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct Hash_Iterator {
typedef Bucket_Node<T> Node;
typedef hash_bucket<K, T, KeyOfT, Hash> HT;
typedef Hash_Iterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HT* _ht;
Hash_Iterator(Node* node, const HT* ht) : _node(node), _ht(ht) {}
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
bool operator!=(const Self& s) { 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()) {
_node = _ht->_tables[hashi];
if (_node) break;
else ++hashi;
}
if (hashi == _ht->_tables.size()) {
_node = nullptr;
}
}
return *this;
}
};
template<class K, class T, class KeyofT, class Hashturn>
class hash_bucket {
template<class K, class T, class ref, class ptr, class KeyofT, class Hashturn>
friend struct Hash_Iterator;
typedef Bucket_Node<T> Node;
public:
typedef Hash_Iterator<K, T, T&, T*, KeyofT, Hashturn> Iterator;
typedef Hash_Iterator<K, T, const T&, const T*, KeyofT, Hashturn> Const_Iterator;
hash_bucket() : _n(0), _tables(__stl_next_prime(0)) {}
Iterator begin() {
if (_n == 0) return Iterator(nullptr, this);
for (int i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
if (cur) return Iterator(cur, this);
}
}
Iterator end() { return Iterator(nullptr, this); }
Const_Iterator end() const { return Const_Iterator(nullptr, this); }
Const_Iterator begin() const {
if (_n == 0) return Const_Iterator(nullptr, this);
for (int i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
if (cur) return Const_Iterator(cur, this);
}
}
pair<Iterator, bool> insert(const T& data) {
KeyofT kot;
Hashturn hash;
if (1 == (_n / _tables.size())) {
Iterator it = Find(kot(data));
if (it != end()) return { it, false };
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
for (int i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hash(kot(data)) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return { Iterator(newnode, this), false };
}
Iterator Find(const K& key) {
KeyofT kot;
Hashturn hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) return Iterator(cur, this);
}
return Iterator(nullptr, this);
}
bool erase(const K& key) {
KeyofT kot;
Hashturn hash;
Node* prev = nullptr;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) {
if (prev) {
prev->_next = cur->_next;
} else {
_tables[hashi] = prev;
}
delete cur;
_n--;
return true;
} else {
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
size_t _n = 0;
vector<Node*> _tables;
};
3. 支持 iterator 的实现
template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
node* cur;
hashtable* ht;
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};
template<class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>& __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++() {
const node* old = cur;
cur = cur->next;
if (!cur) {
size_type bucket = ht->bkt_num(old->val);
while (!cur && ++bucket < ht->buckets.size()) cur = ht->buckets[bucket];
}
return *this;
}
• iterator 实现的大框架跟 list 的 iterator 思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。
• 这里的难点是 operator++ 的实现。iterator 中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点反而是结构设计的问题，参考上面的源码，我们可以看到 iterator 中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用 key 值计算出当前桶位置，依次往后找下一个不为空的桶即可。
• begin() 返回第一个桶中第一个节点指针构造的迭代器，这里 end() 返回迭代器可以用空表示。
• unordered_set 的 iterator 也不支持修改，我们把 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;
• 支持完整的迭代器还有很多细节需要修改，具体参考下面的题的代码。
模拟代码实现：
要点 1：哈希的迭代器与 list 迭代器相似
要点 2：哈希表的迭代器是单向迭代器
要点 3：哈希表的迭代器的成员有哈希结点、和哈希表。
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct Hash_Iterator {
typedef Bucket_Node<T> Node;
typedef hash_bucket<K, T, KeyOfT, Hash> HT;
typedef Hash_Iterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HT* _ht;
Hash_Iterator(Node* node, const HT* ht) : _node(node), _ht(ht) {}
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
bool operator!=(const Self& s) { 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()) {
_node = _ht->_tables[hashi];
if (_node) break;
else ++hashi;
}
if (hashi == _ht->_tables.size()) {
_node = nullptr;
}
}
return *this;
}
};
4. map 支持 []
• unordered_map 要支持 [] 主要需要修改 insert 返回值支持，修改 HashTable 中的 insert 返回值为 pair<Iterator, bool> Insert(const T& data)
• 有了 insert 支持 [] 实现就很简单了，具体参考下面代码实现
T& operator[](const K& key) {
pair<iterator, bool> ret = insert({ key, T() });
return ret.first->second;
}
5. unordered_set/map 模拟实现
template<class K, class Hashturn = Hashturn<K>>
class unordered_set {
struct KeyofT {
const K& operator()(const K& kv) { return kv; }
};
public:
typedef typename hash_bucket<K, const K, KeyofT, Hashturn>::Iterator iterator;
typedef typename hash_bucket<K, const K, KeyofT, Hashturn>::Const_Iterator 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& kv) { return _ht.insert(kv); }
iterator Find(const K& key) { return _ht.Find(key); }
bool Erase(const K& key) { return _ht.erase(key); }
private:
hash_bucket<K, const K, KeyofT, Hashturn> _ht;
};
template<class K, class T, class Hashturn = Hashturn<K>>
class unordered_map {
struct KeyofT {
const K& operator()(const pair<K, T>& kv) { return kv.first; }
};
public:
typedef typename hash_bucket<K, pair<const K, T>, KeyofT, Hashturn>::Iterator iterator;
typedef typename hash_bucket<K, pair<const K, T>, KeyofT, Hashturn>::Const_Iterator 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(); }
T& operator[](const K& key) {
pair<iterator, bool> ret = insert({ key, T() });
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, T>& kv) { return _ht.insert(kv); }
iterator Find(const K& key) { return _ht.Find(key); }
bool Erase(const K& key) { return _ht.erase(key); }
private:
hash_bucket<K, pair<const K, T>, KeyofT, Hashturn> _ht;
};
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
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class T>
struct Bucket_Node {
T _data;
Bucket_Node<T>* _next;
Bucket_Node(const T& data) : _data(data), _next(nullptr) {}
};
template<class K>
struct Hashturn {
size_t operator()(const K& key) { return (size_t)key; }
};
template<>
struct Hashturn<string> {
size_t operator()(const string& key) {
size_t m = 0;
for (auto& e : key) {
m += e;
}
return m;
}
};
template<class K, class T, class KeyofT, class Hashturn>
class hash_bucket {
template<class K, class T, class ref, class ptr, class KeyofT, class Hashturn>
friend struct Hash_Iterator;
typedef Bucket_Node<T> Node;
public:
typedef Hash_Iterator<K, T, T&, T*, KeyofT, Hashturn> Iterator;
typedef Hash_Iterator<K, T, const T&, const T*, KeyOfT, Hashturn> Const_Iterator;
hash_bucket() : _n(0), _tables(__stl_next_prime(0)) {}
Iterator begin() {
if (_n == 0) return Iterator(nullptr, this);
for (int i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
if (cur) return Iterator(cur, this);
}
}
Iterator end() { return Iterator(nullptr, this); }
Const_Iterator end() const { return Const_Iterator(nullptr, this); }
Const_Iterator begin() const {
if (_n == 0) return Const_Iterator(nullptr, this);
for (int i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
if (cur) return Const_Iterator(cur, this);
}
}
pair<Iterator, bool> insert(const T& data) {
KeyofT kot;
Hashturn hash;
if (1 == (_n / _tables.size())) {
Iterator it = Find(kot(data));
if (it != end()) return { it, false };
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
for (int i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hash(kot(data)) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return { Iterator(newnode, this), false };
}
Iterator Find(const K& key) {
KeyofT kot;
Hashturn hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) return Iterator(cur, this);
}
return Iterator(nullptr, this);
}
bool erase(const K& key) {
KeyofT kot;
Hashturn hash;
Node* prev = nullptr;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) {
if (prev) {
prev->_next = cur->_next;
} else {
_tables[hashi] = prev;
}
delete cur;
_n--;
return true;
} else {
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
size_t _n = 0;
vector<Node*> _tables;
};
