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

第C++深入探究哈希表如何封装出unordered目录封装前的哈希代码泛型获取key自定义哈希规则哈希表模板参数解释迭代器结构operator++()构造函数重载运算符小问题代码汇总Hash.hMyUnordered_map.hMyUnordered_set.h默认你已经实现了哈希表（开散列）

封装前的哈希代码

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函数返回值一般都是指针，通过指针访问这个自定义类型的成员

Hashhash;

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

returnnullptr;

size_tindex=hash(key)%_tables.size();//找到桶号

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())//最开始_n为0，而_tables.size()也为0所以可以简化为一行代码

//增容

//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;//记录下一个位置

size_tindex=hash(cur-_kv.first)%newTables.size();

cur-_next=newTables[index];//cur当头

newTables[index]=cur;//更新vector里的头

cur=next;

_tables.swap(newTables);//把新表的数据放入旧表中

size_tindex=hash(kv.first)%_tables.size();//算出桶号

//头插

Node*newNode=newNode(kv);

newNode-_next=_tables[index];

_tables[index]=newNode;

++_n;//别忘记更新有效数据的个数

returntrue;

boolErase(constKkey)

//if(!Find(key))//找不到这个元素

//这么写也可以，但是后面删除的过程中会顺带遍历整个桶

//returnfalse;

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

returnfalse;

Hashhash;

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

deletecur;

cur=nullptr;

_n--;

returntrue;

else

prev=cur;

cur=cur-_next;

returnfalse;

~HashTable()//哈希桶采用的链表结构需要释放每个链表

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;//有效数据

};

泛型

封装时想直接搭出unordered_set/unordered_map的结构,发现行不通

于是从哈希表的结构入手，先把一些类型改成泛型

templateclassT

structHashNode

T_data;

HashNode*_next;

HashNode(constTdata)

:_data(data)

,_next(nullptr)

结点的KV结构改成T,改变结点的类型后HashTable里的结点类型也需要更改

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

获取key

明确unordered_map是KV结构，unordered_set是K模型的结构。

获取key后可以做很多事情，比如查找和算出桶号

封装前哈希结点的类型是pairK,V，现在的类型是T。

pairK,Vkv,可以通过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自定义哈希规则

封装前的哈希表

templateclassK,classV,classHash=HashFuncK

classHashTable{};

现在的哈希表

templateclassK,classT,classKeyOfT,classHash

//去掉哈希表的默认值，哈希函数由unordered_map传入

classHashTable{};

templateclassK,classV,classHash=HashFuncK

classunordered_map{

private:

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

解释：实例化对象时便可以传入模板参数达到自自定义哈希规则的效果。

哈希表模板参数解释

templateclassK,classT,classKeyOfT,classHash

看完上面的对这四个参数应该有大概的了解了。这里一齐解释一下为什么这么写。

第一个参数K：key的类型就是K。查找函数是根据key来查找的，所以需要K。

第二个参数T：哈希表结点存储的数据类型。比如int，double，pair,string等。

第三个参数KeyOfT：拿到T类型(结点数据类型)的key。

第四个参数Hash：表示使用的哈希函数

//哈希函数

templateclassK

structHashFunc

constKoperator()(constKkey)

returnkey;

template//针对string的模板特化

structHashFuncstring

size_toperator()(conststringkey)

size_tvalue=0;

for(autoe:key)

value=value*13+(size_t)e;//*131是BKDR发明的字符串哈希算法，*131等数效率更高

returnvalue;

HashFunc（kot(T)）取出这个类型的key的映射值

迭代器

unordered_set/unordered_map的迭代器是单向迭代器

迭代器只能++，不能

结构

Self表示自己

operator++()

前置++

实现思路：如果当前结点的下一个不为空直接访问即可

如果下一个结点为空，就得找下一个桶怎么找？根据当前指向的数据算出桶号，再把桶号+1，一直往后面找，直到找到一个桶不为空，或者找完了整个容器都没找到，就返回空

Selfoperator++()//找到桶的下一个元素

Hashhash;

KeyOfTkot;

Node*tmp=_node;//记录当前位置，用来计算当前桶号

_node=_node-_next;//当前元素肯定不为空所以不会有空指针引用的问题

//如果下一个为空，就找下一个不为空的桶

if(_node==nullptr)//下一个元素为空

//找下一个不为空的桶，所以需要传入这张表

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())//找到最后一个元素了仍然没找到，说明当前已经是最后一个元素了

_node=nullptr;

else

_node=_ht-_tables[index];

return*this;

else//下一个元素不为空

return*this;

构造函数

构造函数得到结点所在的哈希表

HTIterator(Node*node,HT*ht)//不仅需要知道指向的结点，由于++需要找下一个桶，所以需要哈希结点所在的哈希表

:_node(node)

,_ht(ht)

重载运算符

重载除了++以外的一些运算符

T*operator-()//autoit=m.begin()*it可以拿到数据,所以返回值是T*

return(_node-_data);

Toperator*()

return_node-_data;

booloperator!=(constSelfs)const

returns._node!=_node;

T为pair时可以通过it-first拿到key。

小问题

你会发现这样一个现象，迭代器里面用了哈希表，哈希表里用了迭代器，也即两个类互相引用

如果迭代器写在哈希表前面，那么编译时编译器就会发现哈希表是无定义的（编译器只会往前/上找标识符）。

如果哈希表写在迭代器前面，那么编译时编译器就会发现迭代器是无定义的。

为了解决这个问题，得用一个前置声明解决，即在迭代器和哈希表的定义前加一个类的声明。

templateclassK,classT,classKeyOfT,classHash

classHashTable;//模板需要也需要进行声明

templateclassK,classT,classKeyOfT,classHash

structHTIterator{};

templateclassK,classT,classKeyOfT,classHash

classHashTable{};//具体实现

迭代器里借助一个指针访问了哈希表的数据。但是哈希表的数据被private修饰，所以在类外不能访问，用友元解决。

在哈希表里面声明迭代器友元类（表示迭代器是哈希表的朋友，可以访问哈希表所有的数据）

constpairconstK,V!=constpairK,V

写代码时的一个bug

相关的例子

解释：调试看了一下地址，传进仿函数的时候参数用的引用接收，但是因为类型不同，所以仿函数参数接收时进行了一次拷贝才拿到了sort和排序两个字符串，但也因此那个参数成临时变量了，所以返回了一块被销毁的空间的引用为什么变成空串？因为string析构后那块空间成空串了

简单来说仿函数没有拿到真实的那块空间而是拷贝后形参的空间

不能识别迭代器是类型还是成员导致模板报错，加上typename解决。

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

typename是告诉编译器这是一个类型等这个类实例化了再去找里面的东西

代码汇总

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发明的字符串哈希算法，*131等数效率更高

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;//通过Node*去访问数据不过自定义类型++不能访问到下一个元素，所以需要封装

HT*_ht;

HTIterator(Node*node,HT*ht)//不仅需要知道指向的结点，由于++需要找下一个桶，所以需要哈希结点所在的哈希表

:_node(node)

,_ht(ht)

Selfoperator++()//找到桶的下一个元素

Hashhash;

KeyOfTkot;

//constKkey=kot(_node-_data);//记录这个不为空元素的key有问题类型不匹配导致接收到的key是空串

Node*tmp=_node;

_node=_node-_next;//当前元素肯定不为空所以不会有空指针引用的问题

//如果下一个为空，就找下一个不为空的桶

if(_node==nullptr)//下一个元素为空

//找下一个不为空的桶，所以需要传入这张表

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())//找到最后一个元素了仍然没找到，说明当前已经是最后一个元素了

_node=nullptr;

else

_node=_ht-_tables[index];

return*this;

else//下一个元素不为空

return*this;

T*operator-()//autoit=m.begin()‘it-'去访问数据成员所以返回值是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函数返回值一般都是指针，通过指针访问这个自定义类型的成员

Hashhash;

KeyOfTkot;

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

returnnullptr;

size_tindex=hash(key)%_tables.size();//找到桶号

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);//第二个指针就是自己

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())//最开始_n为0，而_tables.size()也为0所以可以简化为一行代码

//增容

//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;//记录下一个位置

size_tindex=hash(kot(cur-_data))%newTables.size();

cur-_next=newTables[index];//cur当头

newTables[index]=cur;//更新vector里的头

cur=next;

_tables.swap(newTables);//把新表的数据放入旧表中

size_tindex=hash(kot(data))%_tables.size();//算出桶号

//头插

Node*newNode=newNode(data);

newNode-_next=_tables[index];

_tables[index]=newNode;

++_n;//别忘记更新有效数据的个数

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

boolErase(constKkey)

//if(!Find(key))//找不到这个元素

//这么写也可以，但是后面删除的过程中会顺带遍历整个桶

//returnfalse;

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

returnfalse;

Hashhash;

KeyOfTkot;

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

deletecur;

cur=nullptr;

_n--;

returntrue;

else

prev=cur;

cur=cur-_next;

returnfalse;

~HashTable()//哈希桶采用的链表结构需要释放每个链表

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;//有效数据

}

MyUnordered_map.h

#include"Hash.h"

namespaceck

templateclassK,classV