用哈希表封装unordered_map与unordered_set

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;
};

• 这⾥我们就不再画图分析了，通过源码可以看到，结构上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⽐较相等，具体细节参考如下代码实现。

// MyUnorderedSet.h
namespace bit
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:bool insert(const K& key){return _ht.Insert(key);}
private:hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}// MyUnorderedMap.h
namespace bit
{
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:bool insert(const pair<K, V>& kv){return _ht.Insert(kv);}
private:
hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
};
}

//hashtable.h
namespace hash_bucket
{template<class T>struct HashData{T _data;HashData<T>* _next;HashData(const T& data) :_data(data), _next(nullptr){}};template<class k, class T, class KeyOfT, class Hash>class HashTable;template<class k, class T, class Ref, class Ptr, class KeyOfT, class Hash>struct HashIterator{typedef HashData<T> Node;typedef HashTable<k, T, KeyOfT, Hash> Table;typedef HashIterator<k, T, Ref, Ptr, KeyOfT, Hash> Self;Node* _node;const Table* _tb;HashIterator( Node* node,  Table* table) :_node(node), _tb(table){}Self operator++(){if (_node->_next){_node = _node->_next;}else{Hash hs;KeyOfT kot;size_t hashi = hs(kot(_node->_data)) % _tb->_table.size();hashi++;while (hashi < _tb->_table.size()){_node = _tb->_table[hashi];if (_node)break;elsehashi++;}if (hashi == _tb->_table.size()){_node = nullptr;}}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}};template<class k, class T, class KeyOfT, class Hash>class HashTable{typedef HashData<T> Node;public:template<class k, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct HashIterator;typedef HashIterator<k, T, T&, T*, KeyOfT, Hash> Iterator;typedef HashIterator<k, T, const T&, const T*, KeyOfT, Hash> ConstIterator;HashTable() :_table(__stl_next_prime(0)),_n(0){}Iterator Begin(){if (_n==_table.size()){return End();}for (size_t i = 0; i < _table.size(); i++){if (_table[i])return Iterator(_table[i], this);}return End();}Iterator End(){return Iterator(nullptr, this);}ConstIterator Begin()const{if (_n == _table.size()){return End();}for (size_t i = 0; i < _table.size(); i++){if (_table[i])return Iterator(_table[i], this);}return End();}ConstIterator End()const {return Iterator(nullptr, *this);}pair<Iterator,bool> Insert(const T& data){Hash hs;KeyOfT kot;Iterator it = Find(kot(data));if (it!=End())return { it,false };//不允许冗余if (_n / _table.size() == 1){//扩容vector<Node*> tmp;tmp.resize(__stl_next_prime(_table.size() + 1));for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t Hashi = hs(kot(cur->_data)) % tmp.size();cur->_next = tmp[Hashi];tmp[Hashi] = cur;cur = next;}_table[i] = nullptr;}swap(tmp, _table);}size_t hashi = hs(kot(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;_n++;return { Iterator(newnode,this),true };}Iterator Find(const k& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];while (cur){if (hs(key) == hs(kot(cur->_data)))return Iterator(cur, this);cur = cur->_next;}return End();}bool Erase(const k& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _table.size();Node* Prev = nullptr;Node* cur = _table[hashi];while (cur){if (hs(kot(cur->_data)) == key){if (Prev == nullptr){_table[hashi] = cur->_next;}else{Prev->_next = cur->_next;}delete cur;--_n;return true;}Prev = cur;cur = cur->_next;}return false;}private:vector< HashData<T>*> _table;size_t _n;};
}

2.2 ⽀持iterator的实现

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 /* __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;
}

iterator实现思路分析
• 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;

2.3 map⽀持[]

• unordered_map要⽀持[]主要需要修改insert返回值⽀持，修改HashTable中的insert返回值为
pair<Iterator, bool> Insert(const T& data)

2.4 TSY::unordered_map和TSY::unordered_set代码实现

unordered_map

#include"HashTable.h"namespace TSY
{template<class k, class T, class Hash = HashFunc<k>>class unordered_map{struct KeyOfMap{const k& operator()(const pair<k,T>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<k, pair<k, T>, KeyOfMap, Hash> ::Iterator iterator;typedef typename hash_bucket::HashTable<k, pair<k, T>, KeyOfMap, Hash>::Iterator const_iterator;pair<iterator, bool> insert(const pair<k, T>& kv){return _h.Insert(kv);}iterator begin(){return _h.Begin();}iterator end(){return _h.End();}const_iterator begin()const{return _h.Begin();}const_iterator end()const{return _h.End();}T& operator[](const k& key){pair<iterator, bool > ret = insert({key,T()});return ret.first->second;}private:hash_bucket::HashTable<k, pair<k, T>, KeyOfMap, Hash> _h;};
}

unordered_set

#include"HashTable.h"namespace TSY
{template<class k, class Hash = HashFunc<k>>class unordered_set{struct KeyOfSet{const k& operator()(const k& key){return key;}};public:typedef typename hash_bucket::HashTable<k, k, KeyOfSet, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<k, k, KeyOfSet, Hash>::Iterator const_iterator;void insert(const k& key){_h.Insert(key);}iterator begin(){return _h.Begin();}iterator end(){return _h.End();}const_iterator begin()const{return _h.Begin();}const_iterator end()const{return _h.End();}private:hash_bucket::HashTable<k, k, KeyOfSet, Hash> _h;};
}

test.cpp

#include"HashTable.h"
#include"unordered_map.h"
#include"unordered_set.h"void test1()
{TSY::unordered_map<string, int> Map;Map.insert({ "apple",1 });Map.insert({ "banana",1 });Map.insert({ "penapple",1 });Map.insert({ "bucket",1 });/*for (auto& e : Map){cout << e.first << " " << e.second << endl;}*/Map["apple"] = { 4 };Map["tsy"] = { 20 };for (auto& e : Map){cout << e.first << " " << e.second << endl;}
}void test2()
{TSY::unordered_set<string> set;set.insert("apple");set.insert("wanxi");set.insert("songxueyu");set.insert("maishuiguo");for (auto& e : set){cout << e << " " << endl;}cout << endl;
}int main()
{test1();return 0;
}