点击跳转至文章： 【C++/STL】：哈希 – 线性探测&哈希桶

前言

与map/set的封装类似，unordered系列的底层本质上也是复用，通过对哈希表的改造，再分别套上一层 unordered_map 和 unordered_set 的 “壳子”，以达到 “一表二用” 的目的。

各个结构的改造不再详细说明，细节可参考文章：map和set的封装

unordered系列的底层哈希表是用哈希桶结构实现的。

一，哈希表的改造

1. 哈希表的基本框架

(1) K：关键码类型；

(2) V:：不同容器V的类型不同，如果unordered_map，V代表一个键值对，如果是unordered_set，V 为 K；

(3) KeyOfValue：因为V的类型不同，通过value取key的方式就不同，详细见unordered_map/set的实现；

(4) Hash：哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模。

template <class K, class T, class KeyOfT,class Hash = HashFunc<K>>
class HashBucket
{//友元template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >friend struct HTIterator;typedef BucketNode<T> Node;
public:typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;//其他核心操作……private:vector<Node*> _tables;  //指针数组size_t _n = 0;          //表中数据的个数
};
}

2. 对哈希桶节点结构的改造

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

3. 哈希表的迭代器

3.1 迭代器类

(1) 这里的迭代器需要：构造节点指针和哈希表对象指针。

(2) 这里的迭代器类需要用到哈希表类的结构，相互依存，要用前置声明。

//前置声明
template <class K, class T, class KeyOfT, class Hash >
class HashBucket;template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >
struct HTIterator
{//需要节点指针，哈希表对象指针typedef BucketNode<T> Node;typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;const HashBucket<K, T, KeyOfT, Hash>* _pht;Node* _node;HTIterator(Node* node, const HashBucket<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}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 hs;size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();hashi++;while (hashi < _pht->_tables.size()){if (_pht->_tables[hashi])break;hashi++;}if (hashi == _pht->_tables.size()) //走完了_node = nullptr; //End()else_node = _pht->_tables[hashi];}return *this;}
};

3.2 Begin() 和 End()

Iterator Begin()
{if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur)return Iterator(cur, this);}return End();
}Iterator End()
{return Iterator(nullptr, this);
}ConstIterator Begin()const
{if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur)return ConstIterator(cur, this);}return End();
}ConstIterator End()const
{return ConstIterator(nullptr, this);
}

四，哈希表相关接口的改造

4.1 Find 函数的改造

Iterator Find(const K& key)
{Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key)return Iterator(cur, this);elsecur = cur->_next;}return End();
}

4.2 Insert 函数的改造

pair<Iterator, bool> Insert(const T& data)
{Hash hs;KeyOfT kot;Iterator it = Find(kot(data));if (it != End())return make_pair(it, false);//扩容if (_n == _tables.size()){vector<Node*> newTables;newTables.resize(_tables.size() * 2, nullptr);//把旧表的节点挪到新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){size_t hashi = hs(kot(cur->_data)) % newTables.size();Node* newnode = new Node(cur->_data);//头插newnode->_next = newTables[hashi];newTables[hashi] = newnode;cur = cur->_next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);//头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return make_pair(Iterator(newnode, this), true);
}

五，哈希表改造的完整代码

HashTable.h

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//对string类型的特化
template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t n = 0;for (auto ch : s){n += ch;n *= 31;}return n;}
};template <class T>
struct BucketNode
{BucketNode<T>* _next;T _data;BucketNode(const T& data):_data(data), _next(nullptr){}
};//前置声明
template <class K, class T, class KeyOfT, class Hash >
class HashBucket;template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >
struct HTIterator
{//需要节点指针，哈希表对象指针typedef BucketNode<T> Node;//typedef HTIterator<K, T, KeyOfT, Hash> Self;typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;const HashBucket<K, T, KeyOfT, Hash>* _pht;Node* _node;HTIterator(Node* node, const HashBucket<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}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 hs;size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();hashi++;while (hashi < _pht->_tables.size()){if (_pht->_tables[hashi])break;hashi++;}if (hashi == _pht->_tables.size()) //走完了_node = nullptr; //End()else_node = _pht->_tables[hashi];}return *this;}
};template <class K, class T, class KeyOfT,class Hash = HashFunc<K>>
class HashBucket
{//友元template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >friend struct HTIterator;typedef BucketNode<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(){if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur)return Iterator(cur, this);}return End();}Iterator End(){return Iterator(nullptr, this);}ConstIterator Begin()const{if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur)return ConstIterator(cur, this);}return End();}ConstIterator End()const{return ConstIterator(nullptr, this);}HashBucket(){_tables.resize(10, nullptr);}//依次把每个桶释放~HashBucket(){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;}}pair<Iterator, bool> Insert(const T& data){Hash hs;KeyOfT kot;Iterator it = Find(kot(data));if (it != End())return make_pair(it, false);//扩容if (_n == _tables.size()){vector<Node*> newTables;newTables.resize(_tables.size() * 2, nullptr);//把旧表的节点挪到新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){size_t hashi = hs(kot(cur->_data)) % newTables.size();Node* newnode = new Node(cur->_data);//头插newnode->_next = newTables[hashi];newTables[hashi] = newnode;cur = cur->_next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);//头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return make_pair(Iterator(newnode, this), true);}Iterator Find(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key)return Iterator(cur, this);elsecur = cur->_next;}return End();}bool Erase(const T& data){Hash hs;KeyOfT kot;size_t hashi = hs(kot(data)) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (cur->_data == data){//第一个节点if (prev == nullptr){_tables[hashi] = nullptr;}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_set 的封装实现

unordered_set 的底层为哈希表，因此只需在unordered_set 内部封装哈希表，即可将该容器实现出来。

unordered_set .h

#include "HashTable.h"namespace bit
{template <class K, class Hash = HashFunc<K>>class unordered_set{struct SetOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashBucket<K, const K, SetOfT, Hash>::Iterator iterator;typedef typename HashBucket<K, const K, SetOfT, 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);}private:bit::HashBucket<K,const K, SetOfT, Hash> ht;};void Print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){// *it += 1;cout << *it << " ";++it;}cout << endl;}void Test_set(){//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 16,3,7,11,9,26,18,14,15 };unordered_set<int> s;for (auto e : a)s.insert(e);for (auto e : s)cout << e << " ";cout << endl;Print(s);}
}

七，unordered_map 的封装实现

unordered_map 的底层结构就是哈希表，因此在map中直接封装一个哈希表，然后将其接口包装下即可。

unordered_map.h

#include "HashTable.h"namespace bit
{template <class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashBucket<K, pair<const K, V>, MapOfT, Hash>::Iterator iterator;typedef typename HashBucket<K, pair<const K, V>, MapOfT, 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){return ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = ht.Insert(make_pair(key, V()));return ret.first->second;}private:bit::HashBucket<K, pair<const K, V>, MapOfT, Hash> ht;};void Test_map(){unordered_map<string, string> dict;dict.insert({ "left","左边" });dict.insert({ "right","右边" });dict.insert({ "insert","插入" });dict["left"] = "剩余，左边";bit::unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){//it->first += 'x'; //errit->second += 'y'; //okcout << it->first << ":" << it->second << endl;++it;}cout << endl;}
}