C++深入探究哈希表如何封裝出unordered_set和unordered_map
默認(rèn)你已經(jīng)實(shí)現(xiàn)了哈希表(開(kāi)散列)
封裝前的哈希代碼
namespace HashBucket { template<class K,class V> struct HashNode { pair<K, V> _kv; HashNode* _next; HashNode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) {} }; template<class K,class V,class Hash=HashFunc<K>> class HashTable { typedef HashNode<K,V> Node; public: Node* Find(const K& key)//Find函數(shù)返回值一般都是指針,通過(guò)指針訪問(wèn)這個(gè)自定義類(lèi)型的成員 { Hash hash; if (_tables.size() == 0)//表的大小為0,防止取余0 { return nullptr; } size_t index = hash(key) % _tables.size();//找到桶號(hào) Node* cur = _tables[index]; while (cur) { if (cur->_kv.first == key) { return cur; } else { cur = cur->_next; } } return nullptr; } size_t GetNextPrime(size_t prime) { const int PRIMECOUNT = 28; static const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; //ul表示unsigned long size_t i = 0; for (; i < PRIMECOUNT; ++i) { if (primeList[i] > prime) return primeList[i]; } return primeList[i]; } bool Insert(const pair<K, V>& kv) { if (Find(kv.first))//有相同的key直接返回false { return false; } //if(_n==0||_n==_tables.size()) Hash hash; if (_n == _tables.size())//最開(kāi)始_n為0,而_tables.size()也為0所以可以簡(jiǎn)化為一行代碼 { //增容 //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; size_t newSize = GetNextPrime(_tables.size()); vector<Node*>newTables; newTables.resize(newSize, nullptr); for (int i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next;//記錄下一個(gè)位置 size_t index = hash(cur->_kv.first) % newTables.size(); cur->_next = newTables[index];//cur當(dāng)頭 newTables[index] = cur;//更新vector里的頭 cur = next; } } _tables.swap(newTables);//把新表的數(shù)據(jù)放入舊表中 } size_t index = hash(kv.first) % _tables.size();//算出桶號(hào) //頭插 Node* newNode = new Node(kv); newNode->_next = _tables[index]; _tables[index]=newNode; ++_n;//別忘記更新有效數(shù)據(jù)的個(gè)數(shù) return true; } bool Erase(const K& key) { //if (!Find(key))//找不到這個(gè)元素 // 這么寫(xiě)也可以,但是后面刪除的過(guò)程中會(huì)順帶遍歷整個(gè)桶 //{ // return false; //} if (_tables.size() == 0)//哈希表為空 { return false; } Hash hash; size_t index = hash(key) % _tables.size(); Node* cur = _tables[index]; Node* prev = nullptr;//記錄前一個(gè)位置 while (cur) { if (cur->_kv.first == key)//找到這個(gè)元素了 { if(cur==_tables[index])//元素是頭結(jié)點(diǎn) { _tables[index] = cur->_next; } else//不是頭結(jié)點(diǎn) { prev->_next = cur->_next; } delete cur; cur = nullptr; _n--; return true; } else { prev = cur; cur = cur->_next; } } return false; } ~HashTable()//哈希桶采用的鏈表結(jié)構(gòu) 需要釋放每個(gè)鏈表 { for (int i=0;i<_tables.size();i++) { Node* cur = _tables[i]; if (cur == nullptr) { continue; } else { cur = cur->_next; } while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } _n = 0; } HashTable() {}; private: vector<Node*>_tables;//存的是鏈表首元素的指針 size_t _n=0;//有效數(shù)據(jù) };
泛型
封裝時(shí)想直接搭出unordered_set/unordered_map的結(jié)構(gòu),發(fā)現(xiàn)行不通
于是從哈希表的結(jié)構(gòu)入手,先把一些類(lèi)型改成泛型
template<class T> struct HashNode { T _data; HashNode* _next; HashNode(const T&data) :_data(data) , _next(nullptr) {} };
結(jié)點(diǎn)的KV結(jié)構(gòu)改成T ,改變結(jié)點(diǎn)的類(lèi)型后HashTable里的結(jié)點(diǎn)類(lèi)型也需要更改
typedef HashNode<K,V>的模板也需要改為typedef HashNode Node;
獲取key
明確unordered_map是KV結(jié)構(gòu),unordered_set是K模型的結(jié)構(gòu)。
獲取key后可以做很多事情,比如查找和算出桶號(hào)
封裝前哈希結(jié)點(diǎn)的類(lèi)型是pair<K,V>,現(xiàn)在的類(lèi)型是T。
pair<K,V>kv , 可以通過(guò)kv.first來(lái)獲取key。
默認(rèn)int、double、string等類(lèi)型的key就是本身。(也可以自定義)
類(lèi)型T既可能是pair也可能是一個(gè)int類(lèi)型等等,那應(yīng)該怎么得到類(lèi)型T的key?借助模板+仿函數(shù)。
以u(píng)nordered_map為例
unordered_map類(lèi)中實(shí)現(xiàn)仿函數(shù)
哈希表中增加一個(gè)模板參數(shù)KeyOfT來(lái)獲取T類(lèi)型的Key
同理unordered_set里仿函數(shù)的實(shí)現(xiàn)
之后把所有與.first有關(guān)的都用模板實(shí)例化的kot來(lái)獲取key
自定義哈希規(guī)則
去掉哈希表模板參數(shù)里哈希函數(shù)的默認(rèn)值 在unordered_set/unordered_map加上第三個(gè)模板參數(shù)Hash自定義哈希規(guī)則
封裝前的哈希表
template<class K,class V,class Hash=HashFunc<K>> class HashTable{};
現(xiàn)在的哈希表
template<class K, class T, class KeyOfT, class Hash> //去掉哈希表的默認(rèn)值,哈希函數(shù)由unordered_map傳入 class HashTable{}; template<class K,class V,class Hash=HashFunc<K>> class unordered_map{ private: HashBucket::HashTable<K, pair<K, V>, MapKeyOfT,Hash> _ht; };
解釋?zhuān)簩?shí)例化對(duì)象時(shí)便可以傳入模板參數(shù)達(dá)到自自定義哈希規(guī)則的效果。
哈希表模板參數(shù)解釋
template<class K, class T, class KeyOfT, class Hash>
看完上面的對(duì)這四個(gè)參數(shù)應(yīng)該有大概的了解了。這里一齊解釋一下為什么這么寫(xiě)。
第一個(gè)參數(shù)K:key的類(lèi)型就是K。查找函數(shù)是根據(jù)key來(lái)查找的,所以需要K。
第二個(gè)參數(shù)T:哈希表結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)類(lèi)型。比如int,double,pair,string等。
第三個(gè)參數(shù)KeyOfT:拿到T類(lèi)型(結(jié)點(diǎn)數(shù)據(jù)類(lèi)型)的key。
第四個(gè)參數(shù)Hash:表示使用的哈希函數(shù)
//哈希函數(shù) template<class K> struct HashFunc { const K& operator()(const K& key) { return key; } }; template<>//針對(duì)string的模板特化 struct HashFunc <string> { size_t operator()(const string& key) { size_t value = 0; for (auto e : key) { value = value * 13 + (size_t)e;//*131是BKDR發(fā)明的字符串哈希算法,*131等數(shù)效率更高 } return value; } };
HashFunc(kot(T)) 取出這個(gè)類(lèi)型的key的映射值
迭代器
unordered_set/unordered_map的迭代器是單向迭代器
迭代器只能++,不能 –
結(jié)構(gòu)
Self表示自己
operator++()
前置++
實(shí)現(xiàn)思路:如果當(dāng)前結(jié)點(diǎn)的下一個(gè)不為空 直接訪問(wèn)即可
如果下一個(gè)結(jié)點(diǎn)為空,就得找下一個(gè)桶 怎么找?根據(jù)當(dāng)前指向的數(shù)據(jù)算出桶號(hào),再把桶號(hào)+1,一直往后面找,直到找到一個(gè)桶不為空,或者找完了整個(gè)容器都沒(méi)找到,就返回空
Self& operator++()//找到桶的下一個(gè)元素 { Hash hash; KeyOfT kot; Node* tmp = _node;//記錄當(dāng)前位置,用來(lái)計(jì)算當(dāng)前桶號(hào) _node = _node->_next;//當(dāng)前元素肯定不為空 所以不會(huì)有空指針引用的問(wèn)題 //如果下一個(gè)為空,就找下一個(gè)不為空的桶 if (_node == nullptr)//下一個(gè)元素為空 { //找下一個(gè)不為空的桶,所以需要傳入這張表 size_t index = hash(kot(tmp->_data)) % (_ht->_tables.size()); index++; while (index < _ht->_tables.size() && _ht->_tables[index] == nullptr)//一直往后找 { index++; } if (index == _ht->_tables.size())//找到最后一個(gè)元素了仍然沒(méi)找到,說(shuō)明當(dāng)前已經(jīng)是最后一個(gè)元素了 { _node = nullptr; } else { _node = _ht->_tables[index]; } return *this; } else//下一個(gè)元素不為空 { return *this; } }
構(gòu)造函數(shù)
構(gòu)造函數(shù)得到結(jié)點(diǎn)所在的哈希表
HTIterator(Node* node, HT* ht)//不僅需要知道指向的結(jié)點(diǎn),由于++需要找下一個(gè)桶,所以需要哈希結(jié)點(diǎn)所在的哈希表 :_node(node) , _ht(ht) {}
重載運(yùn)算符
重載除了++以外的一些運(yùn)算符
T* operator->()//auto it=m.begin() *it可以拿到數(shù)據(jù),所以返回值是T* { return &(_node->_data); } T& operator*() { return _node->_data; } bool operator!= (const Self& s)const { return s._node != _node; }
T為pair時(shí)可以通過(guò)it->first拿到key。
小問(wèn)題
你會(huì)發(fā)現(xiàn)這樣一個(gè)現(xiàn)象,迭代器里面用了哈希表,哈希表里用了迭代器,也即兩個(gè)類(lèi)互相引用
如果迭代器寫(xiě)在哈希表前面,那么編譯時(shí)編譯器就會(huì)發(fā)現(xiàn)哈希表是無(wú)定義的(編譯器只會(huì)往前/上找標(biāo)識(shí)符)。
如果哈希表寫(xiě)在迭代器前面,那么編譯時(shí)編譯器就會(huì)發(fā)現(xiàn)迭代器是無(wú)定義的。
為了解決這個(gè)問(wèn)題,得用一個(gè)前置聲明解決,即在迭代器和哈希表的定義前加一個(gè)類(lèi)的聲明。
template<class K, class T, class KeyOfT, class Hash> class HashTable;//模板需要也需要進(jìn)行聲明 template<class K, class T, class KeyOfT, class Hash> struct HTIterator{}; ... template<class K, class T, class KeyOfT, class Hash> class HashTable{};//具體實(shí)現(xiàn)
迭代器里借助一個(gè)指針訪問(wèn)了哈希表的數(shù)據(jù)。但是哈希表的數(shù)據(jù)被private修飾,所以在類(lèi)外不能訪問(wèn),用友元解決。
在哈希表里面聲明迭代器友元類(lèi)(表示迭代器是哈希表的朋友,可以訪問(wèn)哈希表所有的數(shù)據(jù))
const pair<const K,V>!=const pair<K,V>
寫(xiě)代碼時(shí)的一個(gè)bug
相關(guān)的例子
解釋?zhuān)赫{(diào)試看了一下地址,傳進(jìn)仿函數(shù)的時(shí)候參數(shù)用的引用接收,但是因?yàn)轭?lèi)型不同,所以仿函數(shù)參數(shù)接收時(shí)進(jìn)行了一次拷貝才拿到了sort和排序兩個(gè)字符串,但也因此那個(gè)參數(shù)成臨時(shí)變量了,所以返回了一塊被銷(xiāo)毀的空間的引用 為什么變成空串?因?yàn)閟tring析構(gòu)后那塊空間成空串了
簡(jiǎn)單來(lái)說(shuō) 仿函數(shù)沒(méi)有拿到真實(shí)的那塊空間 而是拷貝后形參的空間
不能識(shí)別迭代器是類(lèi)型還是成員導(dǎo)致模板報(bào)錯(cuò),加上typename解決。
typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::iterator iterator;
typename是告訴編譯器這是一個(gè)類(lèi)型 等這個(gè)類(lèi)實(shí)例化了再去找里面的東西
代碼匯總
Hash.h
namespace ck { template<class K> struct HashFunc { const K& operator()(const K& key) { return key; } }; template<> struct HashFunc <string> { size_t operator()(const string& key) { size_t value = 0; for (auto e : key) { value = value * 13 + (size_t)e;//*131是BKDR發(fā)明的字符串哈希算法,*131等數(shù)效率更高 } return value; } }; namespace HashBucket { template<class T> struct HashNode { T _data; HashNode* _next; HashNode(const T&data) :_data(data) , _next(nullptr) {} }; template<class K, class T, class KeyOfT, class Hash> class HashTable; template<class K, class T, class KeyOfT, class Hash> struct HTIterator { typedef HTIterator<K, T, KeyOfT, Hash> Self;//自身 typedef HashNode<T> Node; typedef HashTable<K, T, KeyOfT, Hash> HT; Node* _node;//通過(guò)Node*去訪問(wèn)數(shù)據(jù) 不過(guò)自定義類(lèi)型++不能訪問(wèn)到下一個(gè)元素,所以需要封裝 HT* _ht; HTIterator(Node* node, HT* ht)//不僅需要知道指向的結(jié)點(diǎn),由于++需要找下一個(gè)桶,所以需要哈希結(jié)點(diǎn)所在的哈希表 :_node(node) , _ht(ht) {} Self& operator++()//找到桶的下一個(gè)元素 { Hash hash; KeyOfT kot; //const K& key = kot(_node->_data);//記錄這個(gè)不為空元素的key 有問(wèn)題類(lèi)型不匹配導(dǎo)致接收到的key是空串 Node* tmp = _node; _node = _node->_next;//當(dāng)前元素肯定不為空 所以不會(huì)有空指針引用的問(wèn)題 //如果下一個(gè)為空,就找下一個(gè)不為空的桶 if (_node == nullptr)//下一個(gè)元素為空 { //找下一個(gè)不為空的桶,所以需要傳入這張表 size_t index = hash(kot(tmp->_data)) % (_ht->_tables.size()); index++; while (index < _ht->_tables.size() && _ht->_tables[index] == nullptr)//一直往后找 { index++; } if (index == _ht->_tables.size())//找到最后一個(gè)元素了仍然沒(méi)找到,說(shuō)明當(dāng)前已經(jīng)是最后一個(gè)元素了 { _node = nullptr; } else { _node = _ht->_tables[index]; } return *this; } else//下一個(gè)元素不為空 { return *this; } } T* operator->()//auto it=m.begin() ‘it->' 去訪問(wèn)數(shù)據(jù)成員所以返回值是T* { return &(_node->_data); } T& operator*() { return _node->_data; } bool operator!= (const Self& s)const { return s._node != _node; } }; template<class K, class T, class KeyOfT, class Hash> class HashTable { typedef HashNode<T> Node; public: template<class K, class T, class KeyOfT, class Hash> friend struct HTIterator; Node* Find(const K& key)//Find函數(shù)返回值一般都是指針,通過(guò)指針訪問(wèn)這個(gè)自定義類(lèi)型的成員 { Hash hash; KeyOfT kot; if (_tables.size() == 0)//表的大小為0,防止取余0 { return nullptr; } size_t index = hash(key) % _tables.size();//找到桶號(hào) Node* cur = _tables[index]; while (cur) { if (kot(cur->_data) == key) { return cur; } else { cur = cur->_next; } } return nullptr; } size_t GetNextPrime(size_t prime) { const int PRIMECOUNT = 28; static const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; //ul表示unsigned long size_t i = 0; for (; i < PRIMECOUNT; ++i) { if (primeList[i] > prime) return primeList[i]; } return primeList[i]; } typedef HTIterator<K,T,KeyOfT,Hash> iterator; iterator begin() { for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]) { return iterator(_tables[i], this); } } return iterator(nullptr, this); } iterator end() { return iterator(nullptr, this);//第二個(gè)指針就是自己 } pair<iterator,bool> Insert(const T& data) { KeyOfT kot; Node* tmp = Find(kot(data)); if (tmp)//有相同的key直接返回false { return make_pair(iterator(tmp, this), false); } //if(_n==0||_n==_tables.size()) Hash hash; if (_n == _tables.size())//最開(kāi)始_n為0,而_tables.size()也為0所以可以簡(jiǎn)化為一行代碼 { //增容 //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; size_t newSize = GetNextPrime(_tables.size()); vector<Node*>newTables; newTables.resize(newSize, nullptr); for (int i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next;//記錄下一個(gè)位置 size_t index = hash(kot(cur->_data)) % newTables.size(); cur->_next = newTables[index];//cur當(dāng)頭 newTables[index] = cur;//更新vector里的頭 cur = next; } } _tables.swap(newTables);//把新表的數(shù)據(jù)放入舊表中 } size_t index = hash(kot(data)) % _tables.size();//算出桶號(hào) //頭插 Node* newNode = new Node(data); newNode->_next = _tables[index]; _tables[index] = newNode; ++_n;//別忘記更新有效數(shù)據(jù)的個(gè)數(shù) return make_pair(iterator(newNode, this), true); } bool Erase(const K& key) { //if (!Find(key))//找不到這個(gè)元素 // 這么寫(xiě)也可以,但是后面刪除的過(guò)程中會(huì)順帶遍歷整個(gè)桶 //{ // return false; //} if (_tables.size() == 0)//哈希表為空 { return false; } Hash hash; KeyOfT kot; size_t index = hash(key) % _tables.size(); Node* cur = _tables[index]; Node* prev = nullptr;//記錄前一個(gè)位置 while (cur) { if (kot(cur->_data) == key)//找到這個(gè)元素了 { if (cur == _tables[index])//元素是頭結(jié)點(diǎn) { _tables[index] = cur->_next; } else//不是頭結(jié)點(diǎn) { prev->_next = cur->_next; } delete cur; cur = nullptr; _n--; return true; } else { prev = cur; cur = cur->_next; } } return false; } ~HashTable()//哈希桶采用的鏈表結(jié)構(gòu) 需要釋放每個(gè)鏈表 { for (int i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur == nullptr) { continue; } else { cur = cur->_next; } while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } _n = 0; } HashTable() {}; private: vector<Node*>_tables;//存的是鏈表首元素的指針 size_t _n = 0;//有效數(shù)據(jù) }; } }
MyUnordered_map.h
#include "Hash.h" namespace ck { template<class K,class V,class Hash=HashFunc<K>> class unordered_map { struct MapKeyOfT { const K& operator()(const pair< K, V>& kv) const { return kv.first; } }; typedef typename HashBucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash>::iterator iterator; public: iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } pair<iterator, bool> insert(const pair<const K,V>& kv) { return _ht.Insert(kv); } bool erase(const K& key) { return _ht.Erase(key); } bool find(const K& key) { return _ht.Find(key); } V& operator[](const K& key) { auto it = insert(make_pair(key, V())); return (it.first)->second; } private: HashBucket::HashTable<K, pair<K, V>, MapKeyOfT,Hash> _ht; }; }
MyUnordered_set.h
#include "Hash.h" namespace ck { template<class K,class Hash=HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::iterator iterator; public: iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } pair<iterator, bool> insert(const K& kv) { return _ht.Insert(kv); } bool erase(const K& key) { return _ht.Erase(key); } bool find(const K& key) { return _ht.Find(key); } private: HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht; }; private: HashBucket::HashTable<K, pair<K, V>, MapKeyOfT,Hash> _ht; }; }
到此這篇關(guān)于C++深入探究哈希表如何封裝出unordered_set和unordered_map的文章就介紹到這了,更多相關(guān)C++哈希表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的計(jì)算器功能
這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的計(jì)算器功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-01-01C程序函數(shù)調(diào)用&系統(tǒng)調(diào)用
這篇文章主要介紹了C程序函數(shù)調(diào)用&系統(tǒng)調(diào)用,需要的朋友可以參考下2016-09-09C 語(yǔ)言基礎(chǔ)教程(我的C之旅開(kāi)始了)[八]
C 語(yǔ)言基礎(chǔ)教程(我的C之旅開(kāi)始了)[八]...2007-02-02C++鏈表實(shí)現(xiàn)通訊錄設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C++鏈表實(shí)現(xiàn)通訊錄設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06C++實(shí)現(xiàn)String與UF8互轉(zhuǎn)
這篇文章介紹了C++實(shí)現(xiàn)String與UF8互轉(zhuǎn)的方法,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-05-05C語(yǔ)言中sizeof()與strlen()的區(qū)別詳解
這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中sizeof()與strlen()區(qū)別的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12C++ Boost Algorithm算法超詳細(xì)精講
Boost.Algorithm 提供了補(bǔ)充標(biāo)準(zhǔn)庫(kù)算法的算法。與 Boost.Range 不同,Boost.Algorithm 沒(méi)有引入新概念。 Boost.Algorithm 定義的算法類(lèi)似于標(biāo)準(zhǔn)庫(kù)中的算法2022-10-10