C++进阶——封装哈希表实现unordered_map/set

与红黑树封装map/set基本相似，只是unordered_map/set是单向迭代器，模板多传一个HashFunc。

目录

1、源码及框架分析

2、模拟实现unordered_map/set

2.1 复用的哈希表框架及Insert

2.2 iterator的实现

2.2.1 iteartor的核心源码

2.2.2 iterator的实现思路

2.3 map支持[ ]

2.4 UnorderedMap/Set的代码实现

2.4.1 UnorderedMap.h

2.4.2 UnorderedSet.h

2.4.3 HashTable.h

2.4.4 Test.cpp

---

1、源码及框架分析

SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，只是容器的名字是hash_map和hash_set，它们是作为非标准的容器出现的，非标准是指非C++标准规定必须实现的，源代码在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;
};

 template <class Value, class Key, class HashFcn,
          class ExtractKey, class EqualKey,
          class Alloc>
class hashtable {}；

插入用Value，删除查找用Key，ExtractKey是一个仿函数，取Value中的Key值。

2、模拟实现unordered_map/set

2.1 复用的哈希表框架及Insert

1. 这里相比源码调整一下，key参数就用K，value参数就用V，哈希表中的数据类型，我们使用T。

2. 哈希表只需要比较key，那么UnorderedMap和UnorderedSet各自传一个仿函数KfromT，UnorderedSet是为了兼容UnorderedMap，所以也要实现。

3. const保证了不能修改key。Hash是传给哈希表的哈希函数。

HashTable<K, pair<const K, V>, MapKfromT,Hash> _t;

HashTable<K, const K, SetKfromT,Hash> _t;

template<class K, class T, class KfromT,class Hash>

class HashTable{}；

#include "HashTable.h"namespace Lzc
{// class Hash = HashFunc<K>，要通过封装的一层去控制底层的逻辑，template<class K, class V, class Hash = HashFunc<K>>class UnorderedMap{struct MapKfromT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:private:HashTable<K, pair<const K, V>, MapKfromT, Hash> _ht;};
}#include "HashTable.h"namespace Lzc
{template<class K, class Hash = HashFunc<K>>class UnorderedSet{struct SetKfromT{const K& operator()(const K& key){return key;}};public:private:HashTable<K, const K, SetKfromT, Hash> _ht;};
}#include <iostream>
#include <vector>
#include <assert.h>using namespace std;// hash_bucket
namespace Lzc
{inline size_t __stl_next_prime(size_t n) {static const int __stl_num_primes = 28;static const size_t __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 size_t* first = __stl_prime_list;const size_t* last = __stl_prime_list + __stl_num_primes;const size_t* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}template<class K>struct HashFunc{size_t operator()(const K& key){return key;}};template<>struct HashFunc<string>{// 字符串转换成整形，可以把字符ASCII码相加即可// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的// 这里使用BKDR哈希，用上次的计算结果去乘以一个质数，// 这个质数一般取31, 131等效果会比较好size_t operator()(const string& key){size_t hash = 0;for (auto& ch : key){hash = hash * 131 + ch;}return hash;}};template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class KfromT, class Hash>class HashTable{typedef HashNode<T> Node;public:KfromT KfT;Hash hash;HashTable():_table(__stl_next_prime(0), nullptr), _n(0){}HashTable(const HashTable& ht):_table(ht._table.size(), nullptr), _n(0){for (int i = 0; i < ht._table.size(); ++i){Node* cur = ht._table[i];while (cur){Insert(cur->_data);cur = cur->_next;}}}HashTable& operator=(const HashTable& ht){if (this != &ht){HashTable tmp(ht);swap(_table, tmp._table);swap(_n, tmp._n);}return *this;}~HashTable(){for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}_n = 0;}bool Insert(const T& data){if (Find(KfT(data)))return false;// 负载因子>=1扩容if (_n >= _table.size()){vector<Node*> newtable(__stl_next_prime(_table.size() + 1), nullptr);for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hash0 = hash(KfT(cur->_data)) % newtable.size();cur->_next = newtable[hash0]; // 头插newtable[hash0] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t hashi = hash(KfT(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];// 头插_table[hashi] = newnode;++_n;return true;}Node* Find(const K& key){size_t hashi = hash(key) % _table.size();Node* cur = _table[hashi];while (cur){if (KfT(cur->_data) == key)return cur;cur = cur->_next;}return nullptr;}bool Erase(const K& key){size_t hashi = hash(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (KfT(cur->_data) == key){if (prev)prev->_next = cur->_next;else_table[hashi] = cur->_next;delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _table;size_t _n;};
}

2.2 iterator的实现

2.2.1 iteartor的核心源码

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_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */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;
}

2.2.2 iterator的实现思路

1. 整体思路与list的iterator一致，封装节点的指针，迭代器类模板多传Ref和Ptr两个参数，一份模板实现iterator和const_iterator。

2. iterator是一个单向迭代器，只能++(因为是哈希桶，桶中是单链表)，如果++，这个桶遍历完了，如何找到下一个桶呢？

源码是传一个HashTable的指针，可是，只用传vector<Node*>，继续向后找就行了，

所以我们传vector<Node*>。const vector<Node*>，是不允许改变vector中的指针。

3. begin()就是最左非空节点，end()是nullptr。

4. const 对象的const迭代器不能修改数据，所以

        typedef HTIterator<T, T&, T*, Node*, KfromT, Hash> Iterator;
        typedef HTIterator<T, const T&, const T*, const Node*, KfromT, Hash> ConstIterator;

template<class T, class Ref, class Ptr, class NodePtr, class KfromT, class Hash>struct HTIterator{typedef HashNode<T> Node;typedef HTIterator<T, Ref, Ptr, NodePtr, KfromT, Hash> Self;typedef HTIterator<T, T&, T*, Node*, KfromT, Hash> Iterator;KfromT KfT;Hash hash;HTIterator(NodePtr node, const vector<NodePtr>& table):_node(node), _table(table){}HTIterator(const Iterator& it):_node(it._node), _table(it._table){}Self& operator++(){if (_node->_next){_node = _node->_next;}else{// 找下一个不为空的桶size_t hashi = hash(KfT(_node->_data)) % _table.size();++hashi;while (hashi < _table.size() && _table[hashi] == nullptr){++hashi;}if (hashi == _table.size())_node = nullptr;else_node = _table[hashi];}return *this;}Ref operator*(){assert(_node);return _node->_data;}Ptr operator->(){assert(_node);return &(_node->_data);}bool operator==(const HTIterator& htit) const{return _node == htit._node;}bool operator!=(const HTIterator& htit) const{return _node != htit._node;}NodePtr _node;// 找下一个桶，普通迭代器可以修改元素值但不能修改容器结构(增删元素)。const vector<NodePtr>& _table;};

2.3 map支持[ ]

UnorderedMap要支持[ ]主要需要修改Insert返回值，

修改HashTable中的insert返回值为pair<Iterator,bool> Insert(const T& data)，

插入失败，就返回相同的key的value的引用。

插入成功，就返回key的value(默认值)的引用。

2.4 UnorderedMap/Set的代码实现

2.4.1 UnorderedMap.h

#pragma once#include "HashTable.h"namespace Lzc
{// class Hash = HashFunc<K>，要通过封装的一层去控制底层的逻辑，template<class K, class V, class Hash = HashFunc<K>>class UnorderedMap{struct MapKfromT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename HashTable<K, pair<const K, V>, MapKfromT, Hash>::Iterator iterator;typedef typename HashTable<K, pair<const K, V>, MapKfromT, Hash>::ConstIterator const_iterator;pair<iterator, bool> insert(const pair<const K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){iterator ret = _ht.Insert({ key, V() }).first;return ret->second;}bool erase(const K& key){return _ht.Erase(key);}iterator find(const K& key){return _ht.Find(key);}const_iterator find(const K& key) const{return _ht.Find(key);}iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}private:HashTable<K, pair<const K, V>, MapKfromT, Hash> _ht;};
}

2.4.2 UnorderedSet.h

#pragma once#include "HashTable.h"namespace Lzc
{template<class K, class Hash = HashFunc<K>>class UnorderedSet{struct SetKfromT{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, const K, SetKfromT, Hash>::Iterator iterator;typedef typename HashTable<K, const K, SetKfromT, Hash>::ConstIterator const_iterator;pair<iterator, bool> insert(const K& kv){return _ht.Insert(kv);}bool erase(const K& key){return _ht.Erase(key);}iterator find(const K& key){return _ht.Find(key);}const_iterator find(const K& key) const{return _ht.Find(key);}iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}private:HashTable<K, const K, SetKfromT, Hash> _ht;};
}

2.4.3 HashTable.h

#pragma once#include <iostream>
#include <vector>
#include <assert.h>using namespace std;// hash_bucket
namespace Lzc
{inline size_t __stl_next_prime(size_t n) {static const int __stl_num_primes = 28;static const size_t __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 size_t* first = __stl_prime_list;const size_t* last = __stl_prime_list + __stl_num_primes;const size_t* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}template<class K>struct HashFunc{size_t operator()(const K& key){return key;}};template<>struct HashFunc<string>{// 字符串转换成整形，可以把字符ASCII码相加即可// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的// 这里使用BKDR哈希，用上次的计算结果去乘以一个质数，// 这个质数一般取31, 131等效果会比较好size_t operator()(const string& key){size_t hash = 0;for (auto& ch : key){hash = hash * 131 + ch;}return hash;}};template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class T, class Ref, class Ptr, class NodePtr, class KfromT, class Hash>struct HTIterator{typedef HashNode<T> Node;typedef HTIterator<T, Ref, Ptr, NodePtr, KfromT, Hash> Self;typedef HTIterator<T, T&, T*, Node*, KfromT, Hash> Iterator;KfromT KfT;Hash hash;HTIterator(NodePtr node, const vector<NodePtr>& table):_node(node), _table(table){}HTIterator(const Iterator& it):_node(it._node), _table(it._table){}Self& operator++(){if (_node->_next){_node = _node->_next;}else{// 找下一个不为空的桶size_t hashi = hash(KfT(_node->_data)) % _table.size();++hashi;while (hashi < _table.size() && _table[hashi] == nullptr){++hashi;}if (hashi == _table.size())_node = nullptr;else_node = _table[hashi];}return *this;}Ref operator*(){assert(_node);return _node->_data;}Ptr operator->(){assert(_node);return &(_node->_data);}bool operator==(const HTIterator& htit) const{return _node == htit._node;}bool operator!=(const HTIterator& htit) const{return _node != htit._node;}NodePtr _node;// 找下一个桶，普通迭代器可以修改元素值但不能修改容器结构(增删元素)。const vector<NodePtr>& _table;};template<class K, class T, class KfromT, class Hash>class HashTable{typedef HashNode<T> Node;public:typedef HTIterator<T, T&, T*, Node*, KfromT, Hash> Iterator;typedef HTIterator<T, const T&, const T*, const Node*, KfromT, Hash> ConstIterator;KfromT KfT;Hash hash;HashTable():_table(__stl_next_prime(0), nullptr), _n(0){}HashTable(const HashTable& ht):_table(ht._table.size(), nullptr), _n(0){for (int i = 0; i < ht._table.size(); ++i){Node* cur = ht._table[i];while (cur){Insert(cur->_data);cur = cur->_next;}}}HashTable& operator=(const HashTable& ht){if (this != &ht){HashTable tmp(ht);swap(_table, tmp._table);swap(_n, tmp._n);}return *this;}~HashTable(){for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}_n = 0;}Iterator Begin(){for (int i = 0; i < _table.size(); ++i){Node* cur = _table[i];if (cur)return Iterator(cur, _table);}return Iterator(nullptr, _table);}Iterator End(){return Iterator(nullptr, _table);}ConstIterator Begin() const{for (int i = 0; i < _table.size(); ++i){const Node* cur = _table[i];if (cur)return ConstIterator(cur, _table);}return ConstIterator(nullptr, _table);}ConstIterator End() const{return ConstIterator(nullptr, _table);}pair<Iterator, bool> Insert(const T& data){Iterator it = Find(KfT(data));if (it != End())return { it,false };// 负载因子>=1扩容if (_n >= _table.size()){vector<Node*> newtable(__stl_next_prime(_table.size() + 1), nullptr);for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hash0 = hash(KfT(cur->_data)) % newtable.size();cur->_next = newtable[hash0]; // 头插newtable[hash0] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t hashi = hash(KfT(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];// 头插_table[hashi] = newnode;++_n;return { Iterator(newnode,_table),true };}Iterator Find(const K& key){size_t hashi = hash(key) % _table.size();Node* cur = _table[hashi];while (cur){if (KfT(cur->_data) == key)return Iterator(cur, _table);cur = cur->_next;}return Iterator(nullptr, _table);}ConstIterator Find(const K& key) const{size_t hashi = hash(key) % _table.size();const Node* cur = _table[hashi];while (cur){if (KfT(cur->_data) == key)return ConstIterator(cur, _table);cur = cur->_next;}return ConstIterator(nullptr, _table);}bool Erase(const K& key){size_t hashi = hash(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (KfT(cur->_data) == key){if (prev)prev->_next = cur->_next;else_table[hashi] = cur->_next;delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _table;size_t _n;};
}

2.4.4 Test.cpp

//#include "HashTable.h"
#include "UnorderedMap.h"
#include "UnorderedSet.h"struct SetKfromT
{const int& operator()(const int& key){return key;}
};void TestHashTableBasic() {Lzc::HashTable<int, int, SetKfromT, Lzc::HashFunc<int>> ht;// 插入测试assert(ht.Insert(1).second == true);  // 首次插入成功assert(ht.Insert(1).second == false); // 重复插入失败// 查找测试auto it = ht.Find(1);assert(it != ht.End() && *it == 1);   // 能找到已插入的值assert(ht.Find(2) == ht.End());       // 找不到未插入的值
}void TestHashTableRehash() {Lzc::HashTable<int, int, SetKfromT, Lzc::HashFunc<int>> ht;// 插入足够多的数据触发扩容for (int i = 0; i < 100; ++i) {ht.Insert(i);}// 验证所有数据仍可找到for (int i = 0; i < 100; ++i) {assert(ht.Find(i) != ht.End());}
}void TestHashTableErase() {Lzc::HashTable<int, int, SetKfromT, Lzc::HashFunc<int>> ht;ht.Insert(1);ht.Insert(2);assert(ht.Erase(1) == true);   // 删除存在的键assert(ht.Find(1) == ht.End()); // 确认删除成功assert(ht.Erase(3) == false);  // 删除不存在的键
}void TestUnorderedMapInsert() {Lzc::UnorderedMap<int, string> map;// 插入测试auto it1 = map.insert({ 1, "one" });assert(it1.second == true && (it1.first)->second == "one");auto it2 = map.insert({ 1, "uno" });assert(it2.second == false && (it2.first)->second == "one"); // 重复插入失败// operator[] 测试map[2] = "two";assert(map[2] == "two");       // 修改值assert(map[3] == "");          // 自动插入默认值
}void TestUnorderedMapIteration() {Lzc::UnorderedMap<int, string> map;map.insert({ 1, "one" });map.insert({ 2, "two" });// 范围for遍历for (const auto& e : map) {assert((e.first == 1 && e.second == "one") || (e.first == 2 && e.second == "two"));}
}void TestUnorderedMapCopy() {Lzc::UnorderedMap<int, string> map1;map1.insert({ 1, "one" });// 拷贝构造auto map2 = map1;assert(map2.find(1)->second == "one");// 赋值操作Lzc::UnorderedMap<int, string> map3;map3 = map1;assert(map3.find(1) != map3.end());
}void TestUnorderedSetInsert() {Lzc::UnorderedSet<int> set;assert(set.insert(1).second == true);  // 首次插入成功assert(set.insert(1).second == false); // 重复插入失败assert(set.find(1) != set.end());
}void TestUnorderedSetErase() {Lzc::UnorderedSet<int> set;set.insert(1);set.insert(2);assert(set.erase(1) == true);   // 删除存在的键assert(set.find(1) == set.end());assert(set.erase(3) == false);  // 删除不存在的键
}void TestUnorderedSetEdgeCases() {Lzc::UnorderedSet<int> empty_set;// 空表测试assert(empty_set.find(1) == empty_set.end());assert(empty_set.erase(1) == false);// 插入大量数据for (int i = 0; i < 1000; ++i) {empty_set.insert(i);}assert(empty_set.find(999) != empty_set.end());
}int main() {TestHashTableBasic();TestHashTableRehash();TestHashTableErase();TestUnorderedMapInsert();TestUnorderedMapIteration();TestUnorderedMapCopy();TestUnorderedSetInsert();TestUnorderedSetErase();TestUnorderedSetEdgeCases();cout << "All tests passed!" << endl;return 0;
}