【C++筆記】unordered_map/set的哈希封裝
🔥個人主頁：大白的編程日記
🔥專欄：C++筆記
文章目錄
- 【C++筆記】unordered_map/set的哈希封裝
- 前言
- 一. 源碼及框架分析
- 二.迭代器
- 三.operator[]
- 四.使用哈希表封裝unordered_map/set
- 后言
前言
哈嘍，各位小伙伴大家好!上期我們講了哈希表的底層實現。今天我們來講一下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的哈希封裝。大家自己好好消化！今天就分享到這！感謝各位的耐心垂閱！咱們下期見！拜拜~
 -- 列表初始化，右值引用和移動語義)
