目錄
一、哈希表的修改
1.1、哈希表節點結構
1.2、迭代器
1.3、哈希表結構
1.4、完整代碼
二、unordered_map的實現
二、unordered_set的實現
一、哈希表的修改
注意:這里我們使用哈希桶來封裝unordered_map和unordered_set。
1.1、哈希表節點結構
template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};
因為我們要復用哈希表,即使用同一份哈希表代碼來封裝unordered_map和unordered_set,所以這里將模版參數改為T,T即要存儲的數據類型,對于unordered_set而言,T直接就是要存儲的數據類型;對于unordered_map而言,T是pair類型的。
在插入方法中,我們使用有參構造,在創建節點時直接將數據通過構造函數賦值進去,所以這里還實現了一個構造函數。
1.2、迭代器
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_OPERATORpointer 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_map的iterator不?持修改key但是可以修改value,我們把unordered_map的第?個模板參數pair的第?個參數改成const K即可,HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;(不允許修改Key是因為數據在哈希表中存儲的地址是通過Key映射的,如果修改Key,破壞了哈希表的結構)。
- unordered_set的iterator也不?持修改,我們把unordered_set的第?個模板參數改成const K即可,HashTable<K, const K, SetKeyOfT, Hash> _ht;(和unordered_map同理)。
具體代碼:
// 前置聲明template<class K, class T, class KeyOfT, class Hash>class HashTable;template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>struct HTIterator{typedef HashNode<T> Node;typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;Node* _node;const HashTable<K, T, KeyOfT, Hash>* _pht;HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}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;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}};
注意:這里需要對哈希表進行前置聲明,因為在迭代器中用到了哈希表,但是編譯器編譯時是向上查找,而哈希表在下面,會因為找不到而報錯,將哈希表放到上面也不行,因為哈希表里也會封裝迭代器,如果哈希表在上面向上查找時就會找不到迭代器,總之必須有一個進行前置聲明。另外,迭代器中重載++運算符時為了確定當前節點的位置訪問了哈希表的私有成員,所以后面在哈希表中還需要進行友元聲明。
1.3、哈希表結構
template<class K, class T, class KeyOfT, class Hash>class HashTable{// 友元聲明template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>friend struct HTIterator;typedef HashNode<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);}HashTable(){_tables.resize(10, nullptr);}~HashTable(){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){KeyOfT kot;Iterator it = Find(kot(data));//去重if (it != End()){return make_pair(it,false);}Hash hs;size_t hashi = hs(kot(data)) % _tables.size();//負載因子==1 擴容if (_n == _tables.size()){// 需要新建節點和釋放舊節點,效率較低// HashTable<K, V, Hash> newHT;// for (size_t i = 0; i < _tables.size(); i++)// {// Node* cur = _tables[i];// while (cur)// {// newHT.Insert(cur->_kv);// cur = cur->_next;// }// }// _tables.swap(newHT._tables);vector<Node*> newtables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//舊表中的節點重新映射在新表中的位置size_t hashi = hs(kot(cur->_data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}//節點都挪到新表上了,舊表置空_tables[i] = nullptr;}_tables.swap(newtables);}//頭插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){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return Iterator(cur,this);}cur = cur->_next;}return End();}bool Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; //指針數組size_t _n; //表中存儲數據個數};}
為什么需要KeyOfT模版參數:
跟map和set相???unordered_map和unordered_set的模擬實現類結構更復雜?點,但是?框架和思路是完全類似的。因為HashTable實現了泛型不知道T參數是K,還是pair, 那么insert內部進?插?時要?K對象轉換成整形取模和K?較相等(去重),因為pair的value不需要參與計算取模,且pair默認?持的是key和value?起?較相等,但實際上我們需要的是任何時候只需要?較K對象,所以我們在unordered_map和unordered_set層分別實現?個MapKeyOfT和SetKeyOfT的仿函數傳給 HashTable的KeyOfT,然后HashTable中通過KeyOfT仿函數取出T類型對象中的K對象,再轉換成整形取模和K?較相等。
返回值的修改:
這里為了符合unordered_map和unordered_set的使用將Find方法的返回值改為迭代器,為了實現unordered_map的 [ ] 運算符重載,將Insert方法的返回值該為pair類型,其中返回的pair對象的first屬性的值是新插入節點/原有節點的迭代器,second屬性的值是bool類型,代表是否插入成功。
1.4、完整代碼
namespace hash_bucket
{template<class T>struct HashNode{T _data;HashNode<T>* _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 Ptr, class Ref, class KeyOfT, class Hash>struct HTIterator{typedef HashNode<T> Node;typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;Node* _node;const HashTable<K, T, KeyOfT, Hash>* _pht;HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}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;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}};template<class K, class T, class KeyOfT, class Hash>class HashTable{// 友元聲明template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>friend struct HTIterator;typedef HashNode<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);}HashTable(){_tables.resize(10, nullptr);}~HashTable(){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){KeyOfT kot;Iterator it = Find(kot(data));//去重if (it != End()){return make_pair(it,false);}Hash hs;size_t hashi = hs(kot(data)) % _tables.size();//負載因子==1 擴容if (_n == _tables.size()){// 需要新建節點和釋放舊節點,效率較低// HashTable<K, V, Hash> newHT;// for (size_t i = 0; i < _tables.size(); i++)// {// Node* cur = _tables[i];// while (cur)// {// newHT.Insert(cur->_kv);// cur = cur->_next;// }// }// _tables.swap(newHT._tables);vector<Node*> newtables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//舊表中的節點重新映射在新表中的位置size_t hashi = hs(kot(cur->_data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}//節點都挪到新表上了,舊表置空_tables[i] = nullptr;}_tables.swap(newtables);}//頭插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){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return Iterator(cur,this);}cur = cur->_next;}return End();}bool Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; //指針數組size_t _n; //表中存儲數據個數};}
二、unordered_map的實現
這里的實現沒有什么困難,就是直接套一層殼,所有的調用最終還是去調哈希表的方法,所以這里就不在贅述了,直接上代碼。
#include"HashTable.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:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, 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();}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_map(){unordered_map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左邊" });dict.insert({ "right", "右邊" });dict["left"] = "左邊,剩余";dict["insert"] = "插入";dict["string"];unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first,可以修改second//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;++it;}cout << endl;}
}
二、unordered_set的實現
這里和unordered_map一樣,就是直接套一層殼,所有的調用最終還是去調哈希表的方法,所以這里就不在贅述了,直接上代碼。
#include"HashTable.h"namespace bit
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, 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);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, 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;}struct Date{int _year;int _month;int _day;bool operator==(const Date& d) const{return _year == d._year&& _month == d._month&& _day == d._day;}};struct HashDate{size_t operator()(const Date& key){// 112// 121return (key._year * 31 + key._month) * 31 + key._day;}};void test_set(){unordered_set<int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };for (auto e : a){s.insert(e);}for (auto e : s){cout << e << " ";}cout << endl;unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it += 1;cout << *it << " ";++it;}cout << endl;unordered_set<Date, HashDate> us;us.insert({ 2024, 7, 25 });us.insert({ 2024, 7, 26 });Print(s);}
}