哈希表

  • 1.unorderd系列关联式容器
    • 1.1unordered_map+unordered_set介绍
  • 2.哈希表
    • 2.1闭散列 — 开放地址法
      • 2.1.1线性探测
        • 插入
        • 查找
        • 删除
        • 针对插入查找做的修改
        • 线性探测完整代码
      • 2.1.2二次探测
    • 2.2开散列 — 拉链法(哈希桶)
      • 插入
      • 查找
      • 删除
      • 除留余数法取质数
      • 拷贝构造
      • 赋值重载
      • 哈希桶完整代码

喜欢的点赞，收藏，关注一下把！

1.unorderd系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g2Nlog_2 Nlog2​N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍。

1.1unordered_map+unordered_set介绍

unordered_map在线文档说明
unordered_set在线文档说明

从功能上来说unordered_map和unordered_set和map和set基本上是一样的，只不过unorder_map和unordered_set底层是哈希表。map和set底层是搜索树，所以迭代器在走的时候map和set是有序的，unordered_map和unordered_set是无序的。

因为底层不同，所以给它们一个Hash的仿函数，这个是什么我们学了底层就知道了。

并且还是因为底层不同，它们只有单向迭代器。只支持++，不支持- –

哈希表有多种实现方式，库选择桶的实现方式封装unordered_map和unordered_set，因此它们的底层也可以叫做哈希桶。

下面是对桶操作，不过这些接口我们平常很少用，了解即可。

size_t bucket_count()const返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数
size_t bucket(const K& key)返回元素key所在的桶号

这是有关负载因子的操作，也不用管。

这些东西等我们学过它们的底层之后我们就懂了。

剩下的接口就和map和set几乎差不多，这样的好处也是减轻我们的学习成本。既然unordered_map，unordered_set和map，set接口这么相似，那封装出它们有什么用呢，我们从各自的效率对比来看一看。

以unordered_set和set对比为例，注意对比性能走Release

插入

int main(){size_t N = 1000000;unordered_set<int> us;set<int> s;vector<int> v;v.reserve(N);srand((unsigned int)time(nullptr));for (size_t i = 0; i < N; ++i){v.push_back(rand());}size_t begin1 = clock();for (auto e : v){s.insert(e);}size_t end1 = clock();cout << "set insert: " << end1 - begin1 << endl;size_t begin2 = clock();for (auto e : v){us.insert(e);}size_t end2 = clock();cout << "unordered_set insert: " << end2 - begin2 << endl;return 0;}


好像unordered快不少，说明它还是有点东西的。
那在用用有序的数据对比一下看一看

for (size_t i = 0; i < N; ++i){//v.push_back(rand());v.push_back(i);}


unordered_set又没有set行了，set一直都是单旋树的高度控制的很低


再换一组数据对比一下，因为rand随机数总共就是三万多个，我们生成一百万个肯定有很多重复的，所以我们让数据更随机一点

for (size_t i = 0; i < N; ++i){v.push_back(rand() + i);//v.push_back(rand());//v.push_back(i);}


不同值多一些，set好像更有优势一些。
先不着急，我们在对比find接口

int main(){size_t N = 1000000;unordered_set<int> us;set<int> s;vector<int> v;v.reserve(N);srand((unsigned int)time(nullptr));for (size_t i = 0; i < N; ++i){//v.push_back(rand() + i);v.push_back(rand());//v.push_back(i);}size_t begin1 = clock();for (auto e : v){s.insert(e);}size_t end1 = clock();cout << "set insert: " << end1 - begin1 << endl;size_t begin2 = clock();for (auto e : v){us.insert(e);}size_t end2 = clock();cout << "unordered_set insert: " << end2 - begin2 << endl;size_t begin3 = clock();for (auto e : v){s.find(e);}size_t end3 = clock();cout << "set find: " << end3 - begin3 << endl;size_t begin4 = clock();for (auto e : v){us.find(e);}size_t end4 = clock();cout << "unordered_set find: " << end4 - begin4 << endl;return 0;}

这个find在VS2019,release下没测出来，我们在debug下跑的才能看出区别


unordered_set底层是哈希，是一种映射关系，就比如书上有一段话，通过映射关系直接找到在那一页，然后再找。而搜索树是比它大往右走比它小往左走。


不管是有序set最好的情况下，还是无序，unordered_set的find都比set的要快。
最后在看一看删除。

size_t begin5 = clock();for (auto e : v){s.erase(e);}size_t end5 = clock();cout << "set erase: " << end5 - begin5 << endl;size_t begin6 = clock();for (auto e : v){us.erase(e);}size_t end6 = clock();cout << "set erase: " << end6 - begin6 << endl;



对比这些插入，删除，查找就说明一个事情：不同场景不一定unordered_map和unordered_set比map和set好，也不一定就比map和set差，各有优势，但在任何场景下find，unordered_map和unordered_set一定比map和set好。

2.哈希表

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(lo g 2Nlog_2 N log2​N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

哈希就是一种映射。
哈希映射：key值跟存储位置建立关联关系
也就是说知道key值就可以找到存储位置，知道存储位置也可以再去判断在不在，并且K模型，KV模型都可以搞定。

那如果有一堆整型值来了，哈希映射到表中，会存在什么问题？

是不是值太分散，空间消费太大了。

如果就像数据结构初阶学过的计数排序那样直接就相对映射了，虽然也可以但是太浪费空间，这种方法也就是我们常用的直接定址法，只适合整型+范围集中。

  1. 直接定址法–(常用)
    取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
    优点：简单、均匀
    缺点：需要事先知道关键字的分布情况
    使用场景：适合查找比较小且连续的情况

对于这种范围不集中的，我们更喜欢用另一种方法

  1. 除留余数法–(常用)
    设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

不管你给的我是什么值，假设就是图中的数，我就开10个空间，那一个值来了到底存那呢？我们用这个值去模，模出来余数是几，就存在那个位置。这个时候就和范围不相关了。不管范围是大还是小反正一定能给存到这个表中。

但是这种方法带来了一个新的问题，两个数模之后余数是一样的，3和13都映射到下标3的位置，那这个下标3到底存谁呢？

这就是哈希冲突(碰撞)：不同的值映射到了相同的位置。

直接定址法是不会有这个问题的。因为直接定址法每个值都有唯一的位置。

这个问题如何解决呢？
有两个解决方式:
1.闭散列 — 开放地址法
除模取余数是相同的key值，谁先来谁先占据这个位置，后来的往后找下一个空位，要是还被占据就继续往下找。只要这个表没满就找其他空位。

但是这样就影响了其他位置。就如同亮剑里整个晋西北都乱成粥了,那还有其他更好的办法吗” />2.开散列 — 拉链法(哈希桶)
每一个数组下标存一个单链表头指针，除模取余数是相同的key值来了之后我就把你挂到同一个链表中。这样就不会影响到其他位置了。

冲突的值用一个这样的单链表挂起来，这也是就一个方向的迭代器的原因。

如果冲突的值太多了，这挂的链表也太长了，也影响效率。这个我们在写代码的时候解决它。

2.1闭散列 – 开放地址法

闭散列 – 开放地址法

  1. 线性探测
  2. 二次探测

2.1.1线性探测

我们先把线性探测一说，二次探测也就没有问题了。


插入余数7和余数8你占我的，我占你的。这个我们已经知道了。

那如何查找呢？比如说查找38，28
38来了它的映射位置是8，8的位置不是38，继续往下找，最终在2的位置找到38，查找结束

28来了它的映射位置也是8，8的位置不是28，继续往下走，直到遇到空，也就是4的位置，查找结束，不能以值是否为0而结束，万一你找的值就是0呢？这个位置如何为空呢？下面说


删除呢？删除27
是不是和查找的方式一样啊，要不就找到然后删除，要不就遇到空结束。

这样直接把27删成空对吗？

那现在在想查找38，28还能找到吗？


是不是最终都在0下标空的位置结束了，结果都没找到，但是38本来是有的。

如何解决这个问题？
删除的时候把值置为0，-1？
这种想法不可行，万一你就是0，-1呢？
我们可以给每个位置加一个状态！空的位置标记成空，这个位置存了值就标记为存在，删除就标记为删除，但是值我不删还留在这个位置。

这样在查找38、28，38是一定能找到的。

解决删除影响查找的问题的方法：
每个位置加一个状态标识

这样查找就查找到空才能结束，遇到删除并不能停！

下面我们就实现了
以前我们没学STL，还需要手搓一个数组，现在我们直接用vector就行了。

#include#includeusing namespace std;//枚举 -- 状态enum State{EMPTY,//空EXIST,//存在DELETE,//删除};//表中存的数据template<class K,class V>struct HashData{pair<K, V> _kv;//值State _state;//状态标识};template<class K, class V>class HashTable{typedef HashDate<K, V> Date;public://...private:vector<Date> _tables;size_t _n;//哈希表中有效数据个数};
插入
bool Insert(const pair<K, V>& kv){size_t hashi = kv.first % _tables.capacity();size_t hashi = kv.first % _tables.size();}

模的时候是模capacity，还是size呢？
这里建议模size。因为下面我们要用vector的[ ]接口。
在vector的时候说过，使用[ ]要小心，可能会报错，在模拟实现的时候我们也模拟了这样的情况其中有一句assert(pos < size())；当前位置要小于size，否则就报错。
如果你模了capacity

使用[ ]，铁定报错。因此我们要模size。
并且构造的时候调用resize，调整vector的空间大小。

template<class K,class V>struct HashData{pair<K, V> _kv;State _state=EMPTY;//这里我们不用写HashDate构造，默认构造对内置类型不处理，自定义类型调用它的默认构造//所以我们直接给状态一个缺失值就行了};template<class K, class V>class HashTable{typedef HashData<K, V> Date;public:HashTable():_n(0)//这里没写vector的构造，系统会自动调用它的默认构造{_tables.resize(10);//先给10后面再说这个空间问题，并且会调用HashDate的默认构造}bool Insert(const pair<K, V>& kv){int hashi = kv.first % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测++hashi;hashi %= _tables.size();//防止出了边界}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}private:vector<Date> _tables;size_t _n;//哈希表中有效数据个数};

这里只是插入的一部分代码，接下来我们考虑扩容问题。

哈希表什么情况下进行扩容？如何扩容？

如果这个表是100，已经插入90了，在插入冲突的概率就极大了。所以闭散列的哈希表绝对不可能让它满的。
所以提出了这样一个概念：负载因子(载荷因子)

用来衡量表满的程度。

负载因子越小，冲突概率越小，消耗空间越多
负载因子越大，冲突概率越大，空间利用率约高

散列表的载荷因子定义为: α = 填入表中的元素个数/散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，表明填入表中的元素越多，产生冲突的可能性就越大﹔反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cachemissing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将扩容散列表。

bool Insert(const pair<K, V>& kv){//大于标定负载因子，就需要扩容if (_n / _tables.size() > 0.7)//这样写有没有什么问题{}//。。。}

_n和_tables.size()都是整型，它们俩个相除永远都是0，永远都阔不了容。

bool Insert(const pair<K, V>& kv){//大于标定负载因子，就需要扩容if (_n*10 / _tables.size() > 7){}//。。。}

现在问题是如何扩容？
能不能把数据直接拷贝下来？

不能，表的大小变了，映射关系也就变量，以前是模10，现在应该是模20，所有数据都应该重新映射！

并且也不建议直接vector.resize()，在当前位置扩容，

这个时候你在映射7，7原本就是下标7位置存着，只能往后走到下标10的位置。但是就不对了。

所以我们最终是异地扩容，并且在重新映射！
这里我们也不要重新申请一个vector，而是重新申请一个类，复用insert，最后再把两个vector交换一下就好了。这样就省得在扩容内部在写插入代码造成代码冗余了。

bool Insert(const pair<K, V>& kv){//大于标定负载因子，就需要扩容if (_n*10 / _tables.size() > 7){//旧表数据,重新计算,映射到新表//vector _newtable;//_newtable.resize(_tables.size() * 2);//for ()//{//这里重写插入的代码//}HashTable<K, V> newHt;newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST){newHt.Insert(_tables[i]._kv);//复用insert}}_tables.swap(newHt._tables);//交换哈希表}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行int hashi = kv.first % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测++hashi;hashi %= _tables.size();//防止出了边界}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}

插入还差最后一步，不允许插入相同的值，下面我先把查找写了之后，再把插入最后一点代码补充上。

查找
Date* Find(const K& key){size_t hashi = key % _tables.size();while (_tables[hashi]._state != EMPTY){//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)return &_tables[hashi];++hashi;hashi%= _tables.size();}return nullptr;}

如果是极端场景下，这个代码会不会有问题？假设表大小是10，存在的5个，删除的是5个，是不是查找一个不是插入的数，while这样判断就死循环了？
所以我们可以让查找一圈了就如果没找到就结束。

Date* Find(const K& key){size_t hashi = key % _tables.size();size_t start = hashi;while (_tables[hashi]._state != EMPTY){//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)return &_tables[hashi];++hashi;hashi%= _tables.size();if (start == hashi) //查找一圈就结束.防止极端条件下死循环break;}return nullptr;}

现在把插入代码补充完

bool Insert(const pair<K, V>& kv){//防止插入相同的值if (Find(kv.first))return false;//大于标定负载因子，就需要扩容if (_n*10 / _tables.size() > 7){//旧表数据,重新计算,映射到新表//vector _newtable;//_newtable.resize(_tables.size() * 2);//for ()//{//这里重写插入的代码//}HashTable<K, V> newHt;newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST){newHt.Insert(_tables[i]._kv);//复用insert}}_tables.swap(newHt._tables);//交换哈希表}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行int hashi = kv.first % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测++hashi;hashi %= _tables.size();//防止出了边界}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}
删除
bool Erase(const K& key){//找到就删除Date* ret = Find(key);if (ret){--_n;ret->_state = DELETE;return true;}else{return false;}}
针对插入查找做的修改

对于整型我们的代码是没有问题的，那字符串呢？

void TestHT2(){string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };HashTable<string, int> countHT;for (auto& e : arr){HashData<string, int>* ret = countHT.Find(e);if (ret){ret->_kv.second++;}else{countHT.Insert(make_pair(e, 1));}}}


以前是整数可以直接取模，现在是字符串还能取模吗？

如何解决？
有可能你会想到取字符串首字母转成整型再取模
那如果是下面这种汉字字符串还可以取首字母吗？

其实也可以取汉字的首字母了，汉字通常是由多个字母构成的，通过多个字母去查我们的编码表，它底层还是存的一个一个字符，只是说多个字符构成一个汉字，一般是两个字符。
注意stoi只能把”1234″这样字符数字的字符串转成1234。所以这里也不能用。
但是如果只取第一个字母（字母底层是char类型的也是整型家族的），那肯定第一个字母相同的串肯定就冲突，有没有更好的办法？

下面我们先把这个方法实现一下再说其他的。
这样直接去改可不可以？

答案是不行的，字符串可以这样用，整型不可以。

所以取整型我们写个仿函数。

template<class K>struct HashFunc{//凡是能转成整型的就转成整型 如负数,如指针,如浮点数//string不能转size_t operator()(const K& key){return (size_t)key;}};struct HashFuncString{//string取首字母转整型size_t operator()(const string& key){return key[0];}};

把取整数的地方都添上仿函数

template<class K, class V, class Hash=HashFunc<K>>class HashTable{//。。。bool Insert(const pair<K, V>& kv){//防止插入相同的值if (Find(kv.first))return false;//大于标定负载因子，就需要扩容if (_n*10 / _tables.size() > 7){HashTable<K, V, Hash> newHt;newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST){newHt.Insert(_tables[i]._kv);//复用insert}}_tables.swap(newHt._tables);//交换哈希表}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行//转成整型仿函数Hash hf;int hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测++hashi;hashi %= _tables.size();//防止出了边界}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}Date* Find(const K& key){//转成整型仿函数Hash hf;size_t hashi = hf(key) % _tables.size();size_t start = hashi;while (_tables[hashi]._state != EMPTY){//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)return &_tables[hashi];++hashi;hashi%= _tables.size();if (start == hashi) //查找一圈就结束.防止极端条件下死循环break;}return nullptr;}//。。。}
void TestHT2(){string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };//这里给一个把string转成整型的类，就没问题了HashTable<string, int, HashFuncString> countHT;for (auto& e : arr){HashData<string, int>* ret = countHT.Find(e);if (ret){ret->_kv.second++;}else{countHT.Insert(make_pair(e, 1));}}}

那万一我的K不是string，而是vector呢，这个时候怎么办？
只能针对这个类型写一个仿函数，想办法把这个类型转换成整型。
总之就是灵活的把你所给的自定义类型转换成整型！


所以unordered_map和unordered_set第二个模板参数给了一个hash，能返回整型就直接返回整型，不能就自己写一个仿函数传过去。

我们这里把字符串首字母返回，只要首字母相同就冲突。我们换一种写法。把字符串每个字符的ASCLL码加起来。这样会好一点。

struct HashFuncString{//string取全部字母转整型size_t operator()(const string& key){size_t num = 0;for (auto& ch : key){num += ch;}return num;}};

但是这样还是不太好，再继续说它之前，我们插入一个知识。

void TestHT2(){string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };//HashTable countHT;unordered_map<string, int> countHT;for (auto& e : arr){//HashData* ret = countHT.find(e);auto it = countHT.find(e);if (it != countHT.end()){it->second++;//ret->_kv.second++;}else{countHT.insert(make_pair(e, 1));}}}

为什么这里我们不用传自己写的把字符串转成整型的仿函数，直接用库里的就可以了，它怎么做的呢？

这里用我们以前学的一个知识模板特化
通常情况下，使用模板可以实现一些与类型无关的代码，但是对于一些特殊类型可能会得到一些错误的结果。此时，就需要对模板进行特化。即：在原模版类的基础上，针对特殊类型所进行特殊化的实现方式。
具体知识看这里模板进阶

template<class K>struct HashFunc{//凡是能转成整型的就转成整型 如负数,如指针,如浮点数//string不能转size_t operator()(const K& key){return (size_t)key;}};//模板特化template<>struct HashFunc<string>{size_t operator()(const string& key){size_t num = 0;for (auto& ch : key){num += ch;}return num;}}


这个知识说完，我们再回到上面的问题，不是直接加ASCLL码吗

虽然字符串不同，但是转换成整型都是一样的。
怎么办？
直接想加太简单了，给一个复杂的相加规则。
大佬给了一些办法字符串哈希算法

这里就给了一个常用的办法。
每次都把上一次的结果乘131在加每个字母的ASCLL码。

//模板特化template<>struct HashFunc<string>{size_t operator()(const string& key){size_t num = 0;for (auto& ch : key){num *= 131;num += ch;}return num;}};


这样就极大的减少了冲突。

问：
map和unordered_map有什么区别？从用的方式对key有没有什么要求？
答：
区别可以从底层回答。map底层是一颗搜索树，对key的要求是比较大小，遵守key大的往右比key小的往左的规则，unordered_map底层是哈希表。对key的要求是转成整型，如果不支持直接转成整型要给一个仿函数使它转成整型。

线性探测完整代码
template<class K>struct HashFunc{//凡是能转成整型的就转成整型 如负数,如指针,如浮点数//string不能转size_t operator()(const K& key){return (size_t)key;}};//模板特化template<>struct HashFunc<string>{//BKDRsize_t operator()(const string& key){size_t num = 0;for (auto& ch : key){num *= 131;num += ch;}return num;}};//状态enum State{EMPTY,EXIST,DELETE,};template<class K,class V>struct HashData{pair<K, V> _kv;State _state=EMPTY;};template<class K, class V, class Hash=HashFunc<K>>class HashTable{typedef HashData<K, V> Date;public:HashTable():_n(0){_tables.resize(10);//先给10后面再说这个空间问题}bool Insert(const pair<K, V>& kv){//防止插入相同的值if (Find(kv.first))return false;//大于标定负载因子，就需要扩容if (_n*10 / _tables.size() > 7){//旧表数据,重新计算,映射到新表//vector _newtable;//_newtable.resize(_tables.size() * 2);//for ()//{//这里重写插入的代码//}HashTable<K, V,Hash> newHt;newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST){newHt.Insert(_tables[i]._kv);//复用insert}}_tables.swap(newHt._tables);//交换哈希表}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行Hash hf;int hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测++hashi;hashi %= _tables.size();//防止出了边界}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}Date* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();size_t start = hashi;while (_tables[hashi]._state != EMPTY){//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)return &_tables[hashi];++hashi;hashi%= _tables.size();if (start == hashi) //查找一圈就结束.防止极端条件下死循环break;}return nullptr;}bool Erase(const K& key){Date* ret = Find(key);if (ret){--_n;ret->_state = DELETE;return true;}else{return false;}}private:vector<Date> _tables;size_t _n;//哈希表中有效数据个数};

闭散列不需要自己写析构，拷贝构造，赋值重载。
自定义类型自己会调，内置类型不管是析构对内置类型不处理，还是拷贝构造、赋值重载对内置类型值拷贝都能满足需求，因此不需要自己写。

2.1.2二次探测

二次探测是一个跳跃式的探测，往前一次，往后一次。
就比如一个取余为7的值，冲突之后再次探测7 + 1^2=8也冲突，再次探测 7 – 1^2=6不冲突直接就可以插入了。当然查找也要按照这种方式去查。

除了插入和查找代码修改一下，其他不用变。

bool Insert(const pair<K, V>& kv){//防止插入相同的值if (Find(kv.first))return false;//大于标定负载因子，就需要扩容if (_n*10 / _tables.size() > 7){//旧表数据,重新计算,映射到新表//vector _newtable;//_newtable.resize(_tables.size() * 2);//for ()//{//这里重写插入的代码//}HashTable<K, V,Hash> newHt;newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST){newHt.Insert(_tables[i]._kv);//复用insert}}_tables.swap(newHt._tables);//交换哈希表}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行Hash hf;int hashi = hf(kv.first) % _tables.size();//闭散列--二次探测 int start = hashi;int odd = 1;int even = 1;int oddeven = 1;//控制start每次加的是正的还是负的while (_tables[hashi]._state == EXIST){//二次探测 i=1,-1,2,-2,3,-3...if (oddeven % 2 != 0)//奇数start+i^2 (i=1,2,3,4...){hashi = start + (int)pow(odd++, 2);}else//偶数start-i^2 (i=1,2,3,4...) {hashi = start + ((int)pow(even++, 2) * -1);}++oddeven;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}Date* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();size_t start = hashi;//防止查找死循环int begin = hashi;//二次探测要用的int odd = 1;int even = 1;int oddeven = 1;while (_tables[hashi]._state != EMPTY){//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)return &_tables[hashi];//二次探测if (oddeven % 2 != 0){hashi = begin + (int)pow(odd++, 2);}else{hashi = begin + ((int)pow(even++, 2) * -1);}++oddeven;hashi %= _tables.size();if (start == hashi) //查找一圈就结束.防止极端条件下死循环break;}return nullptr;}

2.2开散列 – 拉链法(哈希桶)

相同余数的值来了再同一个链表中挂起来，原理我们都知道了，下面就来实现它。

template<class K>struct HashFunc{size_t operator()(const K& key){return (size_t)key;}};//模板特化template<>struct HashFunc<string>{//BKDRsize_t operator()(const string& key){size_t num = 0;for (auto& ch : key){num *= 131;num += ch;}return num;}};template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _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:HashTable():_n(0){_tables.resize(10);//resize也会调用HashNode的构造}private:vector<Node*> _tables;//数组中位置都存链表的头指针,相当于一个指针数组size_t _n;};

插入

余数相同的值来了，头插还是尾插？
建议头插，不然每次都要找链表尾部太麻烦了。同一个桶谁在前谁在后都可以。并且数组里存的是头指针的地址非常方便。
库里面的单向迭代器就是底层挂的是单链表的原因。当然你也可以改成双向链表那自然就有双向迭代器了。

bool Insert(const pair<K, V>& kv){//Hash匿名对象去调用仿函数,算在第几个桶int hashi = Hash()(kv.first) % _tables.size();//头插Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;

接下来就是扩容，什么时候扩容？

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行扩容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表扩容，也就说负载因子是1的时候扩容。

下面问题是怎么扩容呢？还想闭散列那样重新申请一个类？这样做有没有什么问题？

bool Insert(const pair<K, V>& kv){//负载因子控制在1,超过就扩容if (_n == _tables.size()){//重新申请一个类,复用InsertHashTable<K, V, Hash> newHT;newHT._tables.resize(_tables.size() * 2);for (auto cur : _tables){while (cur){newHT.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newHT._tables);//交换，有点像拷贝构造那种现代写法}//走到这里调用HashTable的析构//匿名对象去调用仿函数,算在第几个桶里面int hashi = Hash()(kv.first) % _tables.size();//头插Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}

哈希桶的析构要不要写？使用默认的析构能不能正确释放空间呢？
这个需要对vector底层有一点了解，vector的析构不会释放链表，所以造成空间浪费了，因此我们写哈希桶的析构，同样也需要自己写拷贝构造，赋值重载，因为默认生成的拷贝构造，赋值重载调用vector得，但是vector对Node*这个指针也是内置类型只完成了值拷贝(浅拷贝)。这个我们后面再补充。
先写析构。

HashTable():_n(0)//这里虽然没有明确写调用vector构造,但是编译器会按照声明顺序去调用的,所以会自动调用vecto的构造{_tables.resize(10);//调用HashNode的构造}~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;}}//走到这里会自动调用vector的析构

当前扩容还没有优化的空间？
按照目前写的，首先会调用构造，然后在insert把旧表的数据拿下来在new一个新的数据在插入，最后调用析构把旧表和旧数据释放，

这样效率是不是有点慢了。能不能不释放旧表节点，把旧表节点重新映射到新表。
因此我们在扩容时只需要申请一个vector就好了，把旧表节点重新映射到新表。

bool Insert(const pair<K, V>& kv){//负载因子控制在1,超过就扩容if (_n == _tables.size()){//重新申请一张表，把旧表节点重新映射到新表vector<Node*> newtable;newtable.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];//头插到新表while (cur){Node* next = cur->_next;size_t hashi = Hash()(cur->_kv.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtable);//旧表和新表交换一}//匿名对象去调用仿函数,算在第几个桶里面int hashi = Hash()(kv.first) % _tables.size();//头插Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}

接下来就是防止插入相同的值了，也是一样，先把查找写一下，然后再补充插入的。

查找

Node* Find(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;elsecur = cur->_next;}return nullptr;}

插入完整代码

bool Insert(const pair<K, V>& kv){//防止插入相同的值if (Find(kv.first))return false;//负载因子控制在1,超过就扩容if (_n == _tables.size()){vector<Node*> newtable;newtable.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];//头插到新表while (cur){Node* next = cur->_next;size_t hashi = Hash()(cur->_kv.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtable);//旧表和新表交换一下}//匿名对象去调用仿函数,算在第几个桶里面int hashi = Hash()(kv.first) % _tables.size();//头插Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}

删除

删除不能再直接查找了，然后就删除了。因为我们这是单链表，需要知道该节点前一个位置！也不能使用单链表那种O(1)那种覆盖删除法。

所以老老实实的去找，然后再删。

bool Erase(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;//记录被删节点前一个位置while (cur){if (cur->_kv.first == key){if (cur == _tables[hashi])//被删节点是头一个节点{_tables[hashi] = cur->_next;}else {prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}

除留余数法取质数

这里我们看看库是怎么取的

库里给我们定义了一个质数表，第一次是53扩容2倍是106肯定不是质数了，因此选了一个靠近106的质数97，也算是接近2倍空间扩容了。

在我们的代码哈希表也加上这个取质数的函数。

inline unsigned long __stl_next_prime(unsigned long n){static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151,12289, 24593,49157,98317,196613,393241,786433,1572869,3145739,6291469, 12582917,25165843,50331653, 100663319,201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};//最大质数取得是靠近整型最大数得质数for (size_t i = 0; i < __stl_num_primes; ++i){//找比当前空间大的质数if (__stl_prime_list[i] > n)return __stl_prime_list[i];}//不用担心会哈希表会扩到最大质数,因为这时对于整型来说都已经差不多48G了return __stl_prime_list[__stl_num_primes - 1];}

构造和插入扩容也都需要改一下
构造获取比0大的质数
插入扩容获取比当前空间大的质数

拷贝构造

HashTable(const HashTable<K,V,Hash>& ht):_n(ht._n){_tables.resize(ht._tables.size());for (size_t i = 0; i < ht._tables.size(); ++i){//遍历找头指针Node* cur = ht._tables[i];if (cur){//找到之后重新申请节点插入新哈希表Node* copy = new Node(cur->_kv);_tables[i] = copy;//如果该链表不止一个节点，把其他节点拿下来重新申请节点尾插while (cur->_next){cur = cur->_next;//尾插copy->_next = new Node(cur->_kv);copy = copy->_next;}}}}

赋值重载

//赋值重载现代写法 复用拷贝构造HashTable<K, V, Hash>& operator=(HashTable<K, V, Hash> ht){_n = ht._n;_tables.swap(ht._tables);return *this;//返回之前会自动调用HashTable的析构，释放对象ht}

哈希桶完整代码

template<class K>struct HashFunc{//凡是能转成整型的就转成整型 如负数,如指针,如浮点数//string不能转size_t operator()(const K& key){return (size_t)key;}};//模板特化template<>struct HashFunc<string>{//BKDRsize_t operator()(const string& key){size_t num = 0;for (auto& ch : key){num *= 131;num += ch;}return num;}};template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _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:HashTable():_n(0)//这里虽然没有明确写调用vector构造,但是编译器会按照声明顺序去调用的,所以会自动调用vecto的构造{//_tables.resize(10);//调用HashNode的构造_tables.resize(__stl_next_prime(0));}~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;}}//走到这里会自动调用vector的析构HashTable(const HashTable<K,V,Hash>& ht):_n(ht._n){_tables.resize(ht._tables.size());for (size_t i = 0; i < ht._tables.size(); ++i){Node* cur = ht._tables[i];if (cur){Node* copy = new Node(cur->_kv);_tables[i] = copy;while (cur->_next){cur = cur->_next;//尾插copy->_next = new Node(cur->_kv);copy = copy->_next;}}}}//赋值重载现代写法 复用拷贝构造HashTable<K, V, Hash>& operator=(HashTable<K, V, Hash> ht){_n = ht._n;_tables.swap(ht._tables);return *this;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//负载因子控制在1,超过就扩容if (_n == _tables.size()){vector<Node*> newtable;//newtable.resize(_tables.size() * 2);newtable.resize(__stl_next_prime(_tables.size()));for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];//头插到新表while (cur){Node* next = cur->_next;size_t hashi = Hash()(cur->_kv.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtable);//旧表和新表交换一下}//匿名对象去调用仿函数,算在第几个桶里面int hashi = Hash()(kv.first) % _tables.size();//头插Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}Node* Find(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;elsecur = cur->_next;}return nullptr;}bool Erase(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;//记录被删节点前一个位置while (cur){if (cur->_kv.first == key){if (cur == _tables[hashi])//被删节点是头一个节点{_tables[hashi] = cur->_next;}else {prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}inline unsigned long __stl_next_prime(unsigned long n){static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151,12289, 24593,49157,98317,196613,393241,786433,1572869,3145739,6291469, 12582917,25165843,50331653, 100663319,201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};//最大质数取得是靠近整型最大数得质数for (size_t i = 0; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > n)return __stl_prime_list[i];}//不用担心会哈希表会扩到最大质数,因为这时对于整型来说都已经差不多48G了return __stl_prime_list[__stl_num_primes - 1];}private:vector<Node*> _tables;size_t _n;};