C++深入探究哈希表如何封裝出unordered

第C++深入探究哈希表如何封裝出unordered目錄封裝前的哈希代碼泛型獲取key自定義哈希規(guī)則哈希表模板參數(shù)解釋迭代器結(jié)構(gòu)operator++()構(gòu)造函數(shù)重載運(yùn)算符小問(wèn)題代碼匯總Hash.hMyUnordered_map.hMyUnordered_set.h默認(rèn)你已經(jīng)實(shí)現(xiàn)了哈希表（開(kāi)散列）

封裝前的哈希代碼

namespaceHashBucket

templateclassK,classV

structHashNode

pairK,V_kv;

HashNode*_next;

HashNode(constpairK,Vkv)

:_kv(kv)

,_next(nullptr)

templateclassK,classV,classHash=HashFuncK

classHashTable

typedefHashNodeK,VNode;

public:

Node*Find(constKkey)//Find函數(shù)返回值一般都是指針，通過(guò)指針訪問(wèn)這個(gè)自定義類(lèi)型的成員

Hashhash;

if(_tables.size()==0)//表的大小為0，防止取余0

returnnullptr;

size_tindex=hash(key)%_tables.size();//找到桶號(hào)

Node*cur=_tables[index];

while(cur)

if(cur-_kv.first==key)

returncur;

else

cur=cur-_next;

returnnullptr;

size_tGetNextPrime(size_tprime)

constintPRIMECOUNT=28;

staticconstsize_tprimeList[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表示unsignedlong

size_ti=0;

for(;iPRIMECOUNT;++i)

if(primeList[i]prime)

returnprimeList[i];

returnprimeList[i];

boolInsert(constpairK,Vkv)

if(Find(kv.first))//有相同的key直接返回false

returnfalse;

//if(_n==0||_n==_tables.size())

Hashhash;

if(_n==_tables.size())//最開(kāi)始_n為0，而_tables.size()也為0所以可以簡(jiǎn)化為一行代碼

//增容

//size_tnewSize=_tables.size()==010:_tables.size()*2;

size_tnewSize=GetNextPrime(_tables.size());

vectorNode*newTables;

newTables.resize(newSize,nullptr);

for(inti=0;i_tables.size();i++)

Node*cur=_tables[i];

while(cur)

Node*next=cur-_next;//記錄下一個(gè)位置

size_tindex=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_tindex=hash(kv.first)%_tables.size();//算出桶號(hào)

//頭插

Node*newNode=newNode(kv);

newNode-_next=_tables[index];

_tables[index]=newNode;

++_n;//別忘記更新有效數(shù)據(jù)的個(gè)數(shù)

returntrue;

boolErase(constKkey)

//if(!Find(key))//找不到這個(gè)元素

//這么寫(xiě)也可以，但是后面刪除的過(guò)程中會(huì)順帶遍歷整個(gè)桶

//returnfalse;

if(_tables.size()==0)//哈希表為空

returnfalse;

Hashhash;

size_tindex=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;

deletecur;

cur=nullptr;

_n--;

returntrue;

else

prev=cur;

cur=cur-_next;

returnfalse;

~HashTable()//哈希桶采用的鏈表結(jié)構(gòu)需要釋放每個(gè)鏈表

for(inti=0;i_tables.size();i++)

Node*cur=_tables[i];

if(cur==nullptr)

continue;

else

cur=cur-_next;

while(cur)

Node*next=cur-_next;

deletecur;

cur=next;

_tables[i]=nullptr;

_n=0;

HashTable(){};

private:

vectorNode*_tables;//存的是鏈表首元素的指針

size_t_n=0;//有效數(shù)據(jù)

};

泛型

封裝時(shí)想直接搭出unordered_set/unordered_map的結(jié)構(gòu),發(fā)現(xiàn)行不通

于是從哈希表的結(jié)構(gòu)入手，先把一些類(lèi)型改成泛型

templateclassT

structHashNode

T_data;

HashNode*_next;

HashNode(constTdata)

:_data(data)

,_next(nullptr)

結(jié)點(diǎn)的KV結(jié)構(gòu)改成T,改變結(jié)點(diǎn)的類(lèi)型后HashTable里的結(jié)點(diǎn)類(lèi)型也需要更改

typedefHashNodeK,V的模板也需要改為typedefHashNodeNode;

獲取key

明確unordered_map是KV結(jié)構(gòu)，unordered_set是K模型的結(jié)構(gòu)。

獲取key后可以做很多事情，比如查找和算出桶號(hào)

封裝前哈希結(jié)點(diǎn)的類(lèi)型是pairK,V，現(xiàn)在的類(lèi)型是T。

pairK,Vkv,可以通過(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ī)則

封裝前的哈希表

templateclassK,classV,classHash=HashFuncK

classHashTable{};

現(xiàn)在的哈希表

templateclassK,classT,classKeyOfT,classHash

//去掉哈希表的默認(rèn)值，哈希函數(shù)由unordered_map傳入

classHashTable{};

templateclassK,classV,classHash=HashFuncK

classunordered_map{

private:

HashBucket::HashTableK,pairK,V,MapKeyOfT,Hash_ht;

解釋?zhuān)簩?shí)例化對(duì)象時(shí)便可以傳入模板參數(shù)達(dá)到自自定義哈希規(guī)則的效果。

哈希表模板參數(shù)解釋

templateclassK,classT,classKeyOfT,classHash

看完上面的對(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ù)

templateclassK

structHashFunc

constKoperator()(constKkey)

returnkey;

template//針對(duì)string的模板特化

structHashFuncstring

size_toperator()(conststringkey)

size_tvalue=0;

for(autoe:key)

value=value*13+(size_t)e;//*131是BKDR發(fā)明的字符串哈希算法，*131等數(shù)效率更高

returnvalue;

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)找到，就返回空

Selfoperator++()//找到桶的下一個(gè)元素

Hashhash;

KeyOfTkot;

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_tindex=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-()//autoit=m.begin()*it可以拿到數(shù)據(jù),所以返回值是T*

return(_node-_data);

Toperator*()

return_node-_data;

booloperator!=(constSelfs)const

returns._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)的聲明。

templateclassK,classT,classKeyOfT,classHash

classHashTable;//模板需要也需要進(jìn)行聲明

templateclassK,classT,classKeyOfT,classHash

structHTIterator{};

templateclassK,classT,classKeyOfT,classHash

classHashTable{};//具體實(shí)現(xiàn)

迭代器里借助一個(gè)指針訪問(wèn)了哈希表的數(shù)據(jù)。但是哈希表的數(shù)據(jù)被private修飾，所以在類(lèi)外不能訪問(wèn)，用友元解決。

在哈希表里面聲明迭代器友元類(lèi)（表示迭代器是哈希表的朋友，可以訪問(wèn)哈希表所有的數(shù)據(jù)）

constpairconstK,V!=constpairK,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解決。

typedeftypenameHashBucket::HashTableK,K,SetKeyOfT,Hash::iteratoriterator;

typename是告訴編譯器這是一個(gè)類(lèi)型等這個(gè)類(lèi)實(shí)例化了再去找里面的東西

代碼匯總

github代碼匯總

Hash.h

namespaceck

templateclassK

structHashFunc

constKoperator()(constKkey)

returnkey;

template

structHashFuncstring

size_toperator()(conststringkey)

size_tvalue=0;

for(autoe:key)

value=value*13+(size_t)e;//*131是BKDR發(fā)明的字符串哈希算法，*131等數(shù)效率更高

returnvalue;

namespaceHashBucket

templateclassT

structHashNode

T_data;

HashNode*_next;

HashNode(constTdata)

:_data(data)

,_next(nullptr)

templateclassK,classT,classKeyOfT,classHash

classHashTable;

templateclassK,classT,classKeyOfT,classHash

structHTIterator

typedefHTIteratorK,T,KeyOfT,HashSelf;//自身

typedefHashNodeTNode;

typedefHashTableK,T,KeyOfT,Hash

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)

Selfoperator++()//找到桶的下一個(gè)元素

Hashhash;

KeyOfTkot;

//constKkey=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_tindex=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-()//autoit=m.begin()‘it-'去訪問(wèn)數(shù)據(jù)成員所以返回值是T*

return(_node-_data);

Toperator*()

return_node-_data;

booloperator!=(constSelfs)const

returns._node!=_node;

templateclassK,classT,classKeyOfT,classHash

classHashTable

typedefHashNodeTNode;

public:

templateclassK,classT,classKeyOfT,classHash

friendstructHTIterator;

Node*Find(constKkey)//Find函數(shù)返回值一般都是指針，通過(guò)指針訪問(wèn)這個(gè)自定義類(lèi)型的成員

Hashhash;

KeyOfTkot;

if(_tables.size()==0)//表的大小為0，防止取余0

returnnullptr;

size_tindex=hash(key)%_tables.size();//找到桶號(hào)

Node*cur=_tables[index];

while(cur)

if(kot(cur-_data)==key)

returncur;

else

cur=cur-_next;

returnnullptr;

size_tGetNextPrime(size_tprime)

constintPRIMECOUNT=28;

staticconstsize_tprimeList[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表示unsignedlong

size_ti=0;

for(;iPRIMECOUNT;++i)

if(primeList[i]prime)

returnprimeList[i];

returnprimeList[i];

typedefHTIteratorK,T,KeyOfT,Hashiterator;

iteratorbegin()

for(size_ti=0;i_tables.size();i++)

if(_tables[i])

returniterator(_tables[i],this);

returniterator(nullptr,this);

iteratorend()

returniterator(nullptr,this);//第二個(gè)指針就是自己

pairiterator,boolInsert(constTdata)

KeyOfTkot;

Node*tmp=Find(kot(data));

if(tmp)//有相同的key直接返回false

returnmake_pair(iterator(tmp,this),false);

//if(_n==0||_n==_tables.size())

Hashhash;

if(_n==_tables.size())//最開(kāi)始_n為0，而_tables.size()也為0所以可以簡(jiǎn)化為一行代碼

//增容

//size_tnewSize=_tables.size()==010:_tables.size()*2;

size_tnewSize=GetNextPrime(_tables.size());

vectorNode*newTables;

newTables.resize(newSize,nullptr);

for(inti=0;i_tables.size();i++)

Node*cur=_tables[i];

while(cur)

Node*next=cur-_next;//記錄下一個(gè)位置

size_tindex=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_tindex=hash(kot(data))%_tables.size();//算出桶號(hào)

//頭插

Node*newNode=newNode(data);

newNode-_next=_tables[index];

_tables[index]=newNode;

++_n;//別忘記更新有效數(shù)據(jù)的個(gè)數(shù)

returnmake_pair(iterator(newNode,this),true);

boolErase(constKkey)

//if(!Find(key))//找不到這個(gè)元素

//這么寫(xiě)也可以，但是后面刪除的過(guò)程中會(huì)順帶遍歷整個(gè)桶

//returnfalse;

if(_tables.size()==0)//哈希表為空

returnfalse;

Hashhash;

KeyOfTkot;

size_tindex=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;

deletecur;

cur=nullptr;

_n--;

returntrue;

else

prev=cur;

cur=cur-_next;

returnfalse;

~HashTable()//哈希桶采用的鏈表結(jié)構(gòu)需要釋放每個(gè)鏈表

for(inti=0;i_tables.size();i++)

Node*cur=_tables[i];

if(cur==nullptr)

continue;

else

cur=cur-_next;

while(cur)

Node*next=cur-_next;

deletecur;

cur=next;

_tables[i]=nullptr;

_n=0;

HashTable(){};

private:

vectorNode*_tables;//存的是鏈表首元素的指針

size_t_n=0;//有效數(shù)據(jù)

}

MyUnordered_map.h

#include"Hash.h"

namespaceck

templateclassK,classV