目錄

一、哈希表核心特性總結

1.開放地址法

2.鏈地址法

二、unordered_map/unordered_set實現要點分析

1. 哈希表核心實現(HashTable2.h)

(1) 哈希函數處理

(2) 鏈地址法實現

(3) 迭代器設計

(4) hashtable設計

2. unordered_map實現要點

3. unordered_map實現要點

---

一、哈希表核心特性總結

哈希表有兩種表 ：?一種是閉散列（開放地址法），一種是開散列（鏈地址法），我將用畫圖來帶大家理解這兩種方法的思路

1.開放地址法

線性探測

v

2.鏈地址法

二、unordered_map/unordered_set實現要點分析

1. 哈希表核心實現(HashTable2.h)

(1) 哈希函數處理

僅使用首字符會導致大量沖突（如所有以相同字母開頭的字符串），使用BKDR哈希，通過累乘質數和字符值獲得更好分布

// 默認哈希函數（直接類型轉換）
template<class K>
struct DefaultHashFunc {size_t operator()(const K& key) {return (size_t)key;}
};// 字符串特化版本
template<>
struct DefaultHashFunc<string> {size_t operator()(const string& str) {size_t hash = 0;for(auto ch : str) {hash += 131;hash += ch;}return hash;}
};

(2) 鏈地址法實現

template<class T>
struct HashNode
{T _data;HashNode<T>* next;HashNode(const T& data):_data(data), next(nullptr){}
};

(3) 迭代器設計

//前置申明，告訴Iterator,申明了哈希表
template<class K, class T, class KeyOfT, class HashFunc >
class HashTable;template<class K, class T,class Ptr,class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{typedef HashNode<T> Node; typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashFunc>  Self;//這是什么鬼？？typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc>  Iterator;Node* _node;//就是不能改*phtconst HashTable<K, T, KeyOfT, HashFunc>* _pht;//為什么需要節點的指針和哈希的指針/*HTIterator(Node * node,HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}*///這個_pht加了const的重載HTIterator(Node* node,const  HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node), _pht(pht){}//普通迭代器時，它是拷貝構造//const迭代器時，它是構造HTIterator(const Iterator & it):_node(it._node), _pht(it._pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->next){//當前桶還沒完_node = _node->next;}else{KeyOfT kot;HashFunc hf;size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();//從下一個位置，查找不為空的桶++hashi;while (hashi < _pht->_table.size()){if (_pht->_table[hashi]){//不為空就退出_node = _pht->_table[hashi];return (*this);}else{//為空繼續加 ++hashi;}}_node = nullptr;}return *this;}bool operator!=(const Self& s){return  _node != s._node;}bool operator==(const Self& s){return  _node == s._node;}
};

(4) hashtable設計

	template<class K, class T,class KeyOfT, class HashFunc = DefaultHashFunc<K>>class HashTable{typedef HashNode<T> Node;////友元聲明，類模版需要把模版參數帶上template<class K, class T,class Ptr,class Ref ,class KeyOfT, class HashFunc >friend struct HTIterator;		public:typedef HTIterator<K, T,T*,T&, KeyOfT, HashFunc>  iterator;typedef HTIterator<K, T,const T*,const  T&, KeyOfT, HashFunc>  const_iterator;iterator begin(){//找第一個桶for (size_t i =0 ;i < _table.size();i++){Node* cur = _table[i];if (cur){//這里為什么傳this ???  航哥說這里this是哈希表的指針return iterator(cur, this);}}//沒有找到return iterator(nullptr, this);}iterator end(){return iterator(nullptr,this);}const_iterator begin()const{//找第一個桶for (size_t i = 0;i < _table.size();i++){Node* cur = _table[i];if (cur){return const_iterator(cur, this);}}//沒有找到return const_iterator(nullptr, this);}const_iterator end()const{return const_iterator(nullptr, this);}HashTable(){//先把size開到10,然后把剩余的位置另存為空指針_table.resize(10, nullptr);}~HashTable(){for (size_t i = 0;i < _table.size();i++){Node* cur = _table[i];while (cur){Node* next = cur->next;delete cur;//	free cur;cur = next;}//因為cur是野指針，如果不置空，那么他有可能還會指向原來的節點cur = nullptr;}}pair<iterator,bool> insert(const T& data){KeyOfT kot;HashFunc hf;iterator it = Find(kot(data));//在這里是證明有相同的內容if (it!=end()){return make_pair(it,false);}//負載因子到一就擴容if (_n == _table.size()){size_t newSize = _table.size() * 2;//創建新表HashTable<K,T,KeyOfT,HashFunc> newht;//這個需要開新節點，而且銷毀也麻煩//for (size_t i = 0;i < _table.size();i++)//{//	//.......//	ht.insert();//}vector<Node*> newTable;newTable.resize(newSize, nullptr);//便利舊表，順手牽羊，把節點簽下來掛到新表for (size_t i = 0;i < _table.size();i++){Node* cur = _table[i];while (cur){Node* next = cur->next;//頭插新表size_t hashi = hf(kot(cur->_data)) % newSize;cur->next = newTable[hashi];newTable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTable);}size_t hashi = hf(kot(data)) % _table.size();//頭插,這個沒看懂Node* newnode = new Node(data);newnode->next = _table[hashi];_table[hashi] = newnode;++_n;return make_pair(iterator(newnode,this), true);}iterator Find(const K& key){HashFunc hf;KeyOfT kot;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur,this);}cur = cur->next;}return iterator(nullptr,this);}void Print(){for (size_t i = 0;i < _table.size();i++){printf("[%d]->", i);Node* cur = _table[i];while (cur){cout << cur->_kv.first << "->" << cur->_kv.second << "->";cur = cur->next;}printf("NULL\n");}}bool Erase(const K& key){HashFunc hf;KeyOfT kot;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_table[hashi] = cur->next;}else{prev->next = cur->next;}delete cur;return true;}prev = cur;cur = cur->next;}--_n;return false;}private:vector<Node*> _table;//指針數組size_t _n = 0;};

2. unordered_map實現要點

template<class K,class V>
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>::iterator  iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator  const_iterator;pair<iterator,bool> insert(const pair<K,V>& kv){return _ht.insert(kv);}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;}
private://這種const的特殊屬性，一般是自己設置hash_bucket::HashTable<K,pair<const K,V>,MapKeyOfT >  _ht;
};

3. unordered_map實現要點

template<class K>
class unordered_set
{struct SetKeyOfT{const K & operator()(const K & key){return key;}};public:typedef	typename hash_bucket::HashTable<K,K,SetKeyOfT>::const_iterator iterator;typedef	typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin()const
{return _ht.begin();
}iterator end()const
{return _ht.end();
}
pair<iterator,bool> insert(const K& key)
{//這樣寫是錯的，因為這里接受的是const_iterator,返回的是iteratorpair<hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.insert(key);return make_pair(ret.first, ret.second);
}private:hash_bucket::HashTable<K, K,SetKeyOfT>  _ht;
};