unordered_map/set的哈希封装

【C++笔记】unordered_map/set的哈希封装

🔥个人主页：大白的编程日记

🔥专栏：C++笔记

---

前言

哈喽，各位小伙伴大家好!上期我们讲了哈希表的底层实现。今天我们来讲一下unordered_map/set的哈希封装。话不多说，我们进入正题！向大厂冲锋

一. 源码及框架分析

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结构，通过一个参数T来封装map和set,hash_set传给hash_table的是key，hash_map传给hash_table的是pair<const key, value>。通过仿函数取出T中的key。同时哈希表还要多传一个哈希函数的仿函数。
  

二.迭代器

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

三.operator[]

unoredered_map实现operator[]主要是通过insert支持。
通过insert返回的pair中的迭代器，再返回迭代器中数据即可

v& operator[](const k& key)
{pair<iterator, bool> ret = insert({ key,v()});return ret.first._node->_data.second;
}

四.使用哈希表封装unordered_map/set

• 其次跟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 T>struct HashData{HashData<T>* _next;T _data;HashData(const T& key):_next(nullptr),_data(key){}};template<class k, class T, class KeyofT, class HashFun>class HashTable;//前置声明,解决相互依赖template<class k, class T, class Ref, class Ptr, class KeyofT, class HashFun>struct HashIterator{using node = HashData<T>;using self = HashIterator<k, T, Ref, Ptr, KeyofT, HashFun>;using ht = HashTable<k, T, KeyofT, HashFun>;const ht* _ht;node* _node;HashIterator(const ht* const& HT,node* node):_ht(HT), _node(node){}Ref operator*(){return _node->_data;}Ptr operator&(){return &_node->_data;}bool operator==(const self& tmp) const{return _node == tmp._node;}bool operator!=(const self& tmp) const{return _node != tmp._node;}self& operator++(){KeyofT kot;HashFun hash;if (_node->_next){_node = _node->_next;}else{size_t hash0 = hash(kot(_node->_data)) % _ht->_table.size();hash0++;while (hash0<_ht->_table.size()){if (_ht->_table[hash0]){break;}else{hash0++;}}if (hash0 == _ht->_table.size()){_node = nullptr;}else{_node = _ht->_table[hash0];}}return *this;}};template<class k, class T, class KeyofT, class HashFun>class HashTable{template<class k, class T, class Ref, class Ptr, class KeyofT, class HashFun>friend struct HashIterator;//友元声明public:HashTable():_table(__stl_next_prime(0)), _n(0){}using node = HashData<T>;using Iterator = HashIterator<k, T, T&, T*, KeyofT, HashFun>;using Const_Iterator=HashIterator<k, T, const T&, const T*, KeyofT, HashFun>;Iterator  End(){return Iterator(this, nullptr);}Iterator  Begin(){for (int i = 0; i < _table.size(); i++){if (_table[i]){return Iterator(this, _table[i]);}}return End();}Const_Iterator End() const{return Const_Iterator(this, nullptr);}Const_Iterator Begin() const{for (int i = 0; i < _table.size(); i++){if (_table[i]){return Const_Iterator(this, _table[i]);}}return End();}pair<Iterator,bool> Insert(const T& kv){HashFun hash;KeyofT kot;Iterator it = Find(kot(kv));if (it!=End()){return { it,false };}if (_n * 10 / _table.size() >= 7){vector<node*> newtable;newtable.resize(__stl_next_prime(newtable.size() + 1));for (auto& x : _table){node* cur = x;x = nullptr;while (cur){size_t hash0 = hash(kot(cur->_data)) % newtable.size();node* next = cur->_next;cur->_next=newtable[hash0];newtable[hash0] = cur;cur = next;}}_table.swap(newtable);}size_t hash0 = hash(kot(kv)) % _table.size();node* cur = new node(kv);cur->_next = _table[hash0];_table[hash0] = cur;_n++;return { Iterator(this,cur),true};}Iterator Find(const k& key){HashFun hash;KeyofT kot;size_t hash0 = hash(key) % _table.size();node* cur = _table[hash0];while (cur){if (kot(cur->_data) == key){return Iterator(this, cur);}cur = cur->_next;}return End();}bool Erase(const k& key){HashFun hash;KeyofT kot;size_t hash0 = hash(key) % _table.size();node* cur = _table[hash0];node* pre = nullptr;while (cur){if (kot(cur->_data) == key){if (cur == _table[hash0]){_table[hash0] = cur->_next;}else{pre->_next = cur->_next;}return true;}else{pre = cur;cur = cur->_next;}}return false;}private:vector<node*> _table;size_t _n;};

后言

这就是unordered_map/set的哈希封装。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~