C++深入探究哈希表如何封裝出unordered_set和unordered_map
默認你已經實現瞭哈希表（開散列）
封裝前的哈希代碼
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函數返回值一般都是指針，通過指針訪問這個自定義類型的成員
{
Hash hash;
if (_tables.size() == 0)//表的大小為0，防止取餘0
{
return nullptr;
}
size_t index = hash(key) % _tables.size();//找到桶號
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())//最開始_n為0，而_tables.size()也為0所以可以簡化為一行代碼
{
//增容
//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;//記錄下一個位置
size_t index = hash(cur->_kv.first) % newTables.size();
cur->_next = newTables[index];//cur當頭
newTables[index] = cur;//更新vector裡的頭
cur = next;
}
}
_tables.swap(newTables);//把新表的數據放入舊表中
}
size_t index = hash(kv.first) % _tables.size();//算出桶號
//頭插
Node* newNode = new Node(kv);
newNode->_next = _tables[index];
_tables[index]=newNode;
++_n;//別忘記更新有效數據的個數
return true;
}
bool Erase(const K& key)
{
//if (!Find(key))//找不到這個元素
// 這麼寫也可以，但是後面刪除的過程中會順帶遍歷整個桶
//{
// return false;
//}
if (_tables.size() == 0)//哈希表為空
{
return false;
}
Hash hash;
size_t index = hash(key) % _tables.size();
Node* cur = _tables[index];
Node* prev = nullptr;//記錄前一個位置
while (cur)
{
if (cur->_kv.first == key)//找到這個元素瞭
{
if(cur==_tables[index])//元素是頭結點
{
_tables[index] = cur->_next;
}
else//不是頭結點
{
prev->_next = cur->_next;
}
delete cur;
cur = nullptr;
_n--;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
~HashTable()//哈希桶采用的鏈表結構 需要釋放每個鏈表
{
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;//有效數據
};
泛型
封裝時想直接搭出unordered_set/unordered_map的結構,發現行不通
於是從哈希表的結構入手，先把一些類型改成泛型
template<class T>
struct HashNode
{
T _data;
HashNode* _next;
HashNode(const T&data)
:_data(data)
, _next(nullptr)
{}
};
結點的KV結構改成T ,改變結點的類型後HashTable裡的結點類型也需要更改
typedef HashNode<K,V>的模板也需要改為typedef HashNode Node;
獲取key
明確unordered_map是KV結構，unordered_set是K模型的結構。
獲取key後可以做很多事情，比如查找和算出桶號
封裝前哈希結點的類型是pair<K,V>，現在的類型是T。
pair<K,V>kv , 可以通過kv.first來獲取key。
默認int、double、string等類型的key就是本身。（也可以自定義）
類型T既可能是pair也可能是一個int類型等等，那應該怎麼得到類型T的key？借助模板+仿函數。
以unordered_map為例
unordered_map類中實現仿函數
哈希表中增加一個模板參數KeyOfT來獲取T類型的Key
同理unordered_set裡仿函數的實現
之後把所有與.first有關的都用模板實例化的kot來獲取key
自定義哈希規則
去掉哈希表模板參數裡哈希函數的默認值 在unordered_set/unordered_map加上第三個模板參數Hash自定義哈希規則
封裝前的哈希表
template<class K,class V,class Hash=HashFunc<K>>
class HashTable{};
現在的哈希表
template<class K, class T, class KeyOfT, class Hash>
//去掉哈希表的默認值，哈希函數由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;
};
解釋：實例化對象時便可以傳入模板參數達到自自定義哈希規則的效果。
哈希表模板參數解釋
template<class K, class T, class KeyOfT, class Hash>
看完上面的對這四個參數應該有大概的瞭解瞭。這裡一齊解釋一下為什麼這麼寫。
第一個參數K：key的類型就是K。查找函數是根據key來查找的，所以需要K。
第二個參數T：哈希表結點存儲的數據類型。比如int，double，pair,string等。
第三個參數KeyOfT：拿到T類型(結點數據類型)的key。
第四個參數Hash：表示使用的哈希函數
//哈希函數
template<class K>
struct HashFunc
{
const K& operator()(const K& key)
{
return key;
}
};
template<>//針對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發明的字符串哈希算法，*131等數效率更高
}
return value;
}
};
HashFunc（kot(T)） 取出這個類型的key的映射值
迭代器
unordered_set/unordered_map的迭代器是單向迭代器
迭代器隻能++，不能 –
結構
Self表示自己
operator++()
前置++
實現思路：如果當前結點的下一個不為空 直接訪問即可
如果下一個結點為空，就得找下一個桶 怎麼找？根據當前指向的數據算出桶號，再把桶號+1，一直往後面找，直到找到一個桶不為空，或者找完瞭整個容器都沒找到，就返回空
Self& operator++()//找到桶的下一個元素
{
Hash hash;
KeyOfT kot;
Node* tmp = _node;//記錄當前位置，用來計算當前桶號
_node = _node->_next;//當前元素肯定不為空 所以不會有空指針引用的問題
//如果下一個為空，就找下一個不為空的桶
if (_node == nullptr)//下一個元素為空
{
//找下一個不為空的桶，所以需要傳入這張表
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())//找到最後一個元素瞭仍然沒找到，說明當前已經是最後一個元素瞭
{
_node = nullptr;
}
else
{
_node = _ht->_tables[index];
}
return *this;
}
else//下一個元素不為空
{
return *this;
}
}
構造函數
構造函數得到結點所在的哈希表
HTIterator(Node* node, HT* ht)//不僅需要知道指向的結點，由於++需要找下一個桶，所以需要哈希結點所在的哈希表
:_node(node)
, _ht(ht)
{}
重載運算符
重載除瞭++以外的一些運算符
T* operator->()//auto it=m.begin() *it可以拿到數據,所以返回值是T*
{
return &(_node->_data);
}
T& operator*()
{
return _node->_data;
}
bool operator!= (const Self& s)const
{
return s._node != _node;
}
T為pair時可以通過it->first拿到key。
小問題
你會發現這樣一個現象，迭代器裡面用瞭哈希表，哈希表裡用瞭迭代器，也即兩個類互相引用
如果迭代器寫在哈希表前面，那麼編譯時編譯器就會發現哈希表是無定義的（編譯器隻會往前/上找標識符）。
如果哈希表寫在迭代器前面，那麼編譯時編譯器就會發現迭代器是無定義的。
為瞭解決這個問題，得用一個前置聲明解決，即在迭代器和哈希表的定義前加一個類的聲明。
template<class K, class T, class KeyOfT, class Hash>
class HashTable;//模板需要也需要進行聲明
template<class K, class T, class KeyOfT, class Hash>
struct HTIterator{};
...
template<class K, class T, class KeyOfT, class Hash>
class HashTable{};//具體實現
迭代器裡借助一個指針訪問瞭哈希表的數據。但是哈希表的數據被private修飾，所以在類外不能訪問，用友元解決。
在哈希表裡面聲明迭代器友元類（表示迭代器是哈希表的朋友，可以訪問哈希表所有的數據）
const pair<const K,V>!=const pair<K,V>
寫代碼時的一個bug
相關的例子
解釋：調試看瞭一下地址，傳進仿函數的時候參數用的引用接收，但是因為類型不同，所以仿函數參數接收時進行瞭一次拷貝才拿到瞭sort和排序兩個字符串，但也因此那個參數成臨時變量瞭，所以返回瞭一塊被銷毀的空間的引用 為什麼變成空串？因為string析構後那塊空間成空串瞭
簡單來說 仿函數沒有拿到真實的那塊空間 而是拷貝後形參的空間
不能識別迭代器是類型還是成員導致模板報錯，加上typename解決。
typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::iterator iterator;
typename是告訴編譯器這是一個類型 等這個類實例化瞭再去找裡面的東西
代碼匯總
github代碼匯總
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發明的字符串哈希算法，*131等數效率更高
}
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;//通過Node*去訪問數據 不過自定義類型++不能訪問到下一個元素，所以需要封裝
HT* _ht;
HTIterator(Node* node, HT* ht)//不僅需要知道指向的結點，由於++需要找下一個桶，所以需要哈希結點所在的哈希表
:_node(node)
, _ht(ht)
{}
Self& operator++()//找到桶的下一個元素
{
Hash hash;
KeyOfT kot;
//const K& key = kot(_node->_data);//記錄這個不為空元素的key 有問題類型不匹配導致接收到的key是空串
Node* tmp = _node;
_node = _node->_next;//當前元素肯定不為空 所以不會有空指針引用的問題
//如果下一個為空，就找下一個不為空的桶
if (_node == nullptr)//下一個元素為空
{
//找下一個不為空的桶，所以需要傳入這張表
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())//找到最後一個元素瞭仍然沒找到，說明當前已經是最後一個元素瞭
{
_node = nullptr;
}
else
{
_node = _ht->_tables[index];
}
return *this;
}
else//下一個元素不為空
{
return *this;
}
}
T* operator->()//auto it=m.begin() ‘it->' 去訪問數據成員所以返回值是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函數返回值一般都是指針，通過指針訪問這個自定義類型的成員
{
Hash hash;
KeyOfT kot;
if (_tables.size() == 0)//表的大小為0，防止取餘0
{
return nullptr;
}
size_t index = hash(key) % _tables.size();//找到桶號
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);//第二個指針就是自己
}
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())//最開始_n為0，而_tables.size()也為0所以可以簡化為一行代碼
{
//增容
//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;//記錄下一個位置
size_t index = hash(kot(cur->_data)) % newTables.size();
cur->_next = newTables[index];//cur當頭
newTables[index] = cur;//更新vector裡的頭
cur = next;
}
}
_tables.swap(newTables);//把新表的數據放入舊表中
}
size_t index = hash(kot(data)) % _tables.size();//算出桶號
//頭插
Node* newNode = new Node(data);
newNode->_next = _tables[index];
_tables[index] = newNode;
++_n;//別忘記更新有效數據的個數
return make_pair(iterator(newNode, this), true);
}
bool Erase(const K& key)
{
//if (!Find(key))//找不到這個元素
// 這麼寫也可以，但是後面刪除的過程中會順帶遍歷整個桶
//{
// 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;//記錄前一個位置
while (cur)
{
if (kot(cur->_data) == key)//找到這個元素瞭
{
if (cur == _tables[index])//元素是頭結點
{
_tables[index] = cur->_next;
}
else//不是頭結點
{
prev->_next = cur->_next;
}
delete cur;
cur = nullptr;
_n--;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
~HashTable()//哈希桶采用的鏈表結構 需要釋放每個鏈表
{
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;//有效數據
};
}
}
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;
};
}
到此這篇關於C++深入探究哈希表如何封裝出unordered_set和unordered_map的文章就介紹到這瞭,更多相關C++哈希表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！