哈希【C++实现】

哈希

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$lo{g}_{2}N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到。

因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍，unordered_multimap和unordered_multiset可查看文档介绍。

2.unordered_map

2.1unordered_map的文档介绍

文档介绍

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。

2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。

4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。

5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。

6. 它的迭代器是前向迭代器。没有反向迭代器

2.2unordered_map的接口介绍

很多接口和map的使用基本是一样的。

下面是其基本使用的代码：

# include<iostream>
# include<unordered_map>
# include<map>
using namespace std;// 有关unordered_map的使用的学习
void test_unordered_map()
{// unordered_map的底层是哈希表，map的底层是红黑树// unordered_map的迭代器只有单向的，map是双向的unordered_map<int, int> _umap;int a[] = { 4, 2, 6, 1, 4, 5, 15, 2, 16, 14 };for (int e : a){_umap.insert(make_pair(e, e));}cout << "unordered_map的迭代器遍历结果：\n";// 和unordered_set一样只实现去重，不会排序unordered_map<int, int>::iterator uit = _umap.begin();while (uit != _umap.end()){cout << uit->first << " | " << uit->second << endl;uit++;}map<int, int> _map;for (int e : a){_map.insert(make_pair(e, e));}cout << "map的迭代器遍历结果：\n";map<int, int>::iterator it = _map.begin();while (it != _map.end()){cout << it->first << " | " << it->second << endl;it++;}// unordered_map其他接口的使用和map基本上都是一样的
}//使用unordered_map的[]重载
void test_unordered_map_2()
{// 统计次数//map<string, int> countMap;unordered_map<string, int> countMap;string strArr[] = { "苹果", "苹果", "苹果", "苹果", "苹果", "橘子", "橘子", "橘子", "香蕉" };for (auto& str : strArr){countMap[str]++;}// 输出统计好的次数for (auto& e : countMap){cout << e.first << "出现次数的" << ":" << e.second << "\n";}cout << endl;// 使用map和unordered_map的区别就是顺序不一样，因为map会排序。
}int main()
{test_unordered_map();test_unordered_map_2();return 0;
}

但是unordered_map有一个接口需要介绍一下：

• unordered_map的元素访问

注意：[]函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶

中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，

将key对应的value返回。

• unordered_map的桶操作

3.unordered_set

3.1unordered_set的文档介绍

文档介绍

1. unordered_set是存储唯一元素的容器，这些元素没有特定的顺序，并且允许根据它们的值快速检索个别元素。
2. 在unordered_set中，元素的值同时也是其键，这个键唯一地标识了它。键是不可变的，因此一旦元素被插入unordered_set中，它们就不能被修改——尽管它们可以被插入和移除。
3. 内部地，unordered_set中的元素没有按照任何特定的顺序排序，但是根据它们的哈希值被组织到不同的桶中，以允许通过它们的值直接快速访问个别元素（平均时间复杂度为常数）。
4. unordered_set容器比集合容器更快地通过键访问个别元素，尽管它们通常在对元素的子集进行范围迭代时效率较低。
5. unordered_set中的迭代器是前向迭代器。

3.2unordered_set的接口

和set的使用及其类似。这里不在介绍

但是要注意其通过迭代器访问的时候是不会像set一样排序的。

下面是插入和迭代器访问的代码：

# include<iostream>
# include<unordered_set>
# include<set>
using namespace std;// 有关unordered_set容器的使用的学习
void test_unordered_set()
{// unordered_set使用起来其实和set是差不多的。// 只是这个的底层是哈希表，set的底层是红黑树unordered_set<int> _us;_us.insert(1);_us.insert(4);_us.insert(7);_us.insert(5);_us.insert(4);_us.insert(6);cout << "unordered_set的迭代器遍历结果：\n";// 根据输出结果可以发现，能实现去重，但是不会排序。unordered_set<int>::iterator it = _us.begin();while (it != _us.end()){//*it = 1; // 不能修改cout << *it << " "; ++it;}cout << endl;  // 1 4 7 5 6set<int> _s; _s.insert(1);_s.insert(4);_s.insert(7);_s.insert(5);_s.insert(4);_s.insert(6);// set是有双向迭代器的，但是unordered_set只有单向的// set是去重+排序cout << "set的迭代器遍历结果：\n";set<int>::iterator sit = _s.begin();while (sit != _s.end()){cout << *sit << " ";++sit;}cout << endl; // 1 4 5 6 7// 其他的接口使用unordered_set和set几乎是一样的，这里再举一个find的使用、cout << "接口find和算法find的使用：\n";// 这里这个find如果找不到返回的是迭代器的末尾 也就是 s.end()//set<int>::iterator pos = find(_s.begin(), _s.end(), 2); // 时间复杂度O（N）set<int>::iterator pos = _s.find(20); // 这个是set容器的接口，时间复杂度是O(logN)if (pos == _s.end()){cout << "没找到\n";}// unordered_set和set一样自带find接口//unordered_set<int>::iterator upos = find(_us.begin(), _us.end(), 20);unordered_set<int>::iterator upos = _us.find(20);if (upos == _us.end()){cout << "没找到\n";}}int main()
{test_unordered_set();return 0;
}

4.相关OJ题

961. 在长度 2N 的数组中找出重复 N 次的元素 - 力扣（LeetCode）

class Solution {
public:int repeatedNTimes(vector<int>& nums) {// 遍历数组，统计每个数字出现的次数也可以完成这道题// 这里用unordered_map实现//【利用unordered_map统计每个数字出现的次数】unordered_map<int, int> countMap;for(auto& e : nums){countMap[e]++;}// 找到出现了N次的元素int N = nums.size()/2;for(auto& e : countMap){if(e.second == N)return e.first;}return 0;}
};

两个数组的交集

这个题之前在学习set的使用已经做过了，只是unordered_set也可以做这道题

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 用unordered_set对nums1中的元素去重unordered_set<int> s1;for (auto e : nums1)s1.insert(e);// 用unordered_set对nums2中的元素去重unordered_set<int> s2;for (auto e : nums2)s2.insert(e);// 遍历s1，如果s1中某个元素在s2中出现过，即为交集vector<int> vRet;for (auto& e : s1){if (s2.find(e) != s2.end())vRet.push_back(e);}return vRet;}
};

两个数组的交集 II

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2){vector<int> ret;// 先将nums1的元素全部装进unordered_map中，记录其每个数字出现的次数unordered_map<int, int> um;for (int& e : nums1){um[e]++; // 对于重载[]的运用}// 如果在nums2中出现过，那么就在um中减去一次出现次数，这样就可以将交集统计出来for (int& n : nums2){if (um.count(n)) // 在um中查找是否存在n，找到了返回值是大于0，没找到返回值小于0{//找到了就再um中--出现次数um[n]--;ret.push_back(n); // 将交集放在数组中// 还得判断此时出现次数是否为0，如果为0，就意味着nums2的n出现的次数大于在nums1中出现的次数if (um[n] == 0){um.erase(n); // 删除这个元素}}}return ret;}
};

存在重复元素

class Solution {
public:bool containsDuplicate(vector<int>& nums){// 使用unordered_map统计每个元素出现的次数// 这里使用unordered_set也是可以的，在插入的时候判断元素已经存在与unordered_set中，存在就是重复，返回trueunordered_map<int, int> um;for (int& e : nums){um[e]++;}// 然后遍历um，看看是否有元素出现1次以上for (auto& pair : um){// 只要不是1就是出现1次以上if (pair.second != 1){return true;}}return false;}
};

两句话中的不常见单词

官方题解用了lambda表达式，由于还没学习到这里，我用了一个自己写的insert函数来代替

class Solution {
public:// 将字符串切割成单词，并放到um中，依次统计各个单词出现的次数void insert(const string& str, unordered_map<string, int>& um){stringstream ss(str); // 切割str字符串string word; // 用来放ss中切割出来的单词while (ss >> word){um[word]++; // 统计word这个单词出现的次数}}vector<string> uncommonFromSentences(string s1, string s2){vector<string> ret;unordered_map<string, int> um;// 将先s1，s2切割成一个个单词，然后再往um放insert(s1, um); // 先统计s1的单词insert(s2, um); // 再统计s2的单词// 然后遍历um，将出现一次的单词尾插到ret中for (auto& pair : um){if (pair.second == 1)ret.push_back(pair.first);}return ret;}
};

5.两种容器的区别

5.1性能区别

上面说unordered_map和unordered_set的增删查的时间复杂度是O(1)，map和set的增删查的时间复杂度是O(logN)。

可能没有什么直观的感受，下面我们来看两段代码来感受一下效率的差距

• unordered_set和set的效率对比

// 对比unordered_set和set之间的增删查的效率差距
void test_OP()
{srand((unsigned int)time(NULL)); // 种子unordered_set<int> us;set<int> s;const int N = 1000000;vector<int> v;v.reserve(N);for (int i = 0; i < N; i++){v.push_back(rand());}size_t begin1 = clock();for (int i = 0; i < N; i++){us.insert(v[i]); // 给unordered_set插入数据}size_t end1 = clock();size_t begin2 = clock();for (int i = 0; i < N; i++){s.insert(v[i]); // 给set插入数据}size_t end2 = clock();size_t begin3 = clock();for (int i = 0; i < N; i++){us.find(v[i]); // unordered_set查找数据}size_t end3 = clock();size_t begin4 = clock();for (int i = 0; i < N; i++){s.find(v[i]); // 给set查找数据}size_t end4 = clock();size_t begin5 = clock();for (int i = 0; i < N; i++){us.erase(v[i]); // unordered_set查找数据}size_t end5 = clock();size_t begin6 = clock();for (int i = 0; i < N; i++){s.erase(v[i]); // 给set查找数据}size_t end6 = clock();cout << "unordered_set插入" << N << "个数耗时为:" << (end1 - begin1) << "ms\n";cout << "set插入" << N << "个数耗时为:" << (end2 - begin2) << "ms\n";cout << "unordered_set查找" << N << "个数耗时为:" << (end3 - begin3) << "ms\n";cout << "set查找" << N << "个数耗时为:" << (end4 - begin4) << "ms\n";cout << "unordered_set删除" << N << "个数耗时为:" << (end5 - begin5) << "ms\n";cout << "set删除" << N << "个数耗时为:" << (end6 - begin6) << "ms\n";}

下图是执行结果

可以看到总的来说，unordered_set比起set的效率还是优秀一些

• unordered_map和map的效率对比

// 对比unordered_map和map之间的效率差距
void test_OP()
{unordered_map<int, int> um;map<int, int> m;const int N = 1000000;vector<int> v;v.reserve(N); // 提前开辟空间srand((unsigned int)time(NULL)); // 设置种子for (int i = 0; i < N; i++){v.push_back(rand());}size_t begin1 = clock();for (int i = 0; i < N; i++){um.insert(make_pair(v[i], v[i])); // 给unordered_map插入数据}size_t end1 = clock();size_t begin2 = clock();for (int i = 0; i < N; i++){m.insert(make_pair(v[i], v[i])); // 给map插入数据}size_t end2 = clock();size_t begin3 = clock();for (int i = 0; i < N; i++){um.find(v[i]); // unordered_map查找数据}size_t end3 = clock();size_t begin4 = clock();for (int i = 0; i < N; i++){m.find(v[i]); // 给map查找数据}size_t end4 = clock();size_t begin5 = clock();for (int i = 0; i < N; i++){um.erase(v[i]); // unordered_map删除数据}size_t end5 = clock();size_t begin6 = clock();for (int i = 0; i < N; i++){m.erase(v[i]); // 给map删除数据}size_t end6 = clock();cout << "unordered_map插入" << N << "个数耗时为:" << (end1 - begin1) << "ms\n";cout << "map插入" << N << "个数耗时为:" << (end2 - begin2) << "ms\n";cout << "unordered_map查找" << N << "个数耗时为:" << (end3 - begin3) << "ms\n";cout << "map查找" << N << "个数耗时为:" << (end4 - begin4) << "ms\n";cout << "unordered_map删除" << N << "个数耗时为:" << (end5 - begin5) << "ms\n";cout << "map删除" << N << "个数耗时为:" << (end6 - begin6) << "ms\n";
}

下图是执行结果：

可以看到，unordered_map比起map的效率也是优秀一些

6.底层结构(重要！！！)

unordered_set、unordered_map和map、set在使用上是差不多的，但是效率却有差距、

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。现在就来了解并学习哈希

为了方便理解哈希，这里举个例子：

之前做过一道题找出字符串中第一个只出现一次的字符，这里为了找到只出现一次的字符，做了一个映射的处理。之前的计数排序也用了类似的映射思想、

而哈希就跟这个映射有点关系

6.1哈希的概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素

时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

• 插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

• 搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表

6.2什么是哈希冲突？

哈希冲突——不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突

或哈希碰撞。

下面举个例子来理解哈希冲突

例如：数据集合{1，7，6，4，5，9， 9998}；

按照之前的思想，就是开一个空间为9998的数组，这样中间会有大量空间被浪费。

这个映射的方式叫做直接定址法，一般是直接映射或者是相对映射。【之前的找出字符串中第一个只出现一次的字符中采取的是相对映射，也是直接定值法】

而哈希表采取的是除留余数法（常用）

注意：

哈希表的构造方法有很多种，除留余数法只是其中一种常用的方法。

上图的数据集合，采用除留余数法，9998就会放在8的位置

那怎么查找呢？

怎么映射的就怎么找，这里是key%10的映射方式，那么在找9998这个数字自然就需要去余数为8的位置去找。用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

但是此时会发现一个问题：

如果再来一个余数为1或者余数为8等数字，比如11，此时这个11要放在哪里呢？如果按照除留余数法，那么就应该放在1的位置，但是这里已经有个1了。

此时就会造成一个现象——哈希冲突【不同的值映射到了相同的位置】

6.3能否避免哈希冲突？

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。但是哪怕哈希函数设计的再合理再精妙，也是无法避免哈希冲突的

因此要减少哈希冲突，就应该让哈希函数足够合理

• 哈希函数设计原则：

1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

2. 哈希函数计算出来的地址能均匀分布在整个空间中

3. 哈希函数应该比较简单

• 常见哈希函数

1. 直接定址法–(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

面试题：找出字符串中第一个只出现一次的字符

2. 除留余数法–(常用)

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

3. 平方取中法–(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；

再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法–(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这

几部分叠加求和，并按散列表表长，取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法–(了解)

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中

random为随机数函数。

通常应用于关键字长度不等时采用此法

6. 数学分析法–(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

例如：

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的

若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

6.4解决哈希冲突

解决哈希冲突两种常见的方法是：闭散列和开散列

6.4.1闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去

那要如何找到这个空位置呢？

6.4.1.1线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

• 插入

还是如下图所示，拿上面的例子来解释

此时如果要插入一个11，就会先按照除留余数法，算出其余数为1，哈希地址就是1，准备将其放到下标为1的位置，但是此时发现这个位置有了元素1【哈希冲突】，那么就会线性的寻找下标1后的空位置，找到的就是下标为2的位置

如果再插入一个21呢，继续线性的从下标1开始寻找空位置，找到下标为3的位置

再插入一个31呢？此时会发现线性往后找不到空位置了，此时就会绕回来继续找

这里会发现一个规律，哈希冲突越多，效率越低，一开始的1和11和21插入的效率都还好，但是插入31时的效率就低了【绕了一圈】

如果此时在插入数据，没有空位置了，哈希表就会扩容。

• 删除

在删除的时候会遇到一种情况：在下图的哈希表中找到一个11，并删除，再找到21再删除

此时，按照除留余数法存的，就要找这个法来找，找到的第一个位置是1，但是这里是1不是11，就继续按照线性探测法来找，找到的就是11。

虽然找到了11，但是不能直接删除！为什么？因为会导致无法找到21、因为在哈希表中，如果2是空位就代表没有余数是1的数据了。

如果仍然要将剩下的数据都找一遍的话，那哈希表的效率又该如何保证呢？

实际上是这样处理的：

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

那这个伪删除法具体是什么意思呢？其实就是给每个哈希表中的数据一个状态。

enum State
{EMPTY, // 空，没有数据EXITS, // 有数据，未被删除状态DELETE, // 有数据，被删除状态
};

如果你是被删除的，此时的状态就是被删除，这个时候寻找数据找到你就不会停止寻找，而是继续寻找。

线性探测实现

整体的框架：

enum State
{EMPTY, // 空，没有数据EXITS, // 有数据，未被删除状态DELETE, // 有数据，被删除状态
};template<class T>
struct HashData
{T _data;State _state; // 存储在哈希表中的每个数据，都有一个状态
};// 这里用K，T是为了同时给unordered_set和unordered_map使用【模拟实现map和set的时候也是这处理的】
// unordered_set<K> -> HashTable<K, K>
// unordered_map<K, V> -> HashTable<K, V> 这个V是pair<K, V>
template<class K, class T, class KeyOFT>
class HashTable
{
public:private:// 哈希表可以通过数组来存储，由于可能要增容最好用动态顺序表，但是自己实现太麻烦，直接用vectorvector<HashData<T>> _table; //将T根据映射关系存储到哈希表中size_t _num; // 表示存了几个有效数据。不是哈希表的容量大小
};

下面是插入、删除、查找三个接口的实现【要注意代码中注释的思路】

插入接口的实现：

	// 除留余数法+线性探测 实现哈希表的插入bool Insert(const T& d) // 返回值应该是个pair类型，这里简单化处理{// 计算d这个数据的Key在表中映射的位置// 但是d可能是Key也可能是pair，因此这里需要和之前的红黑树改造一样，需要一个仿函数来处理KeyOFT koft;// 这里哈希表的构造函数，我选择用除留余数法size_t hashadd = hashFunc(d); // 计算余数// 根据余数来映射表中位置，但是要判断该位置是否能够插入等操作// 哈希表是不能满的，不然下面这个就是死循环，因此哈希表是不会满的// 这里需要一个负载因子的概念 负载因子————表中有效数据个数/表的大小【用来衡量哈希表满的程度】// 负载因子越大，表越满，越容易哈希冲突，效率越低，负载因子越大，表越空，效率越高，浪费空间越大// 因此哈希表不是满了才增容，在开放定址法中，一般负载因子到0.7左右就要增容//	每次将数据插入到哈希表中之前，都要判断哈希表空间是否足够CheckCapacity();while (_table[hashadd]._state == EXITS){// 哈希表需要做到数据去重if (koft(_table[hashadd]._data) == koft(d)){return false;}// 只要是有数据存在就要按照线性探测找到下一个空位++hashadd; // 线性探测，一个一个找if (hashadd == _table.size()){// 如果找空位找到结尾，就要从头开始找hashadd = 0;}}// 只要哈希表的容量足够，走到这里就是找到空位_table[hashadd]._data = d; // 将d存储在该位置 _table[hashadd]._state = EXITS;_num++; // 哈希表的有效数据++return true;}

查找接口的实现：

	// 除留余数法 + 线性探测实现哈希表的查找HashData<T>* Find(const K& key) // 返回值按理来说给迭代器，但是这里先简单化处理{KeyOFT koft;size_t hashadd = hashFunc(key); // 通过计算余数获得key在哈希表的位置// 到碰到空位就说明该key不存在于哈希表中while (_table[hashadd]._state != EMPTY){if (koft(_table[hashadd]._data) == key){// 找到了还得判断该位置的数据是否是被删除状态if (_table[hashadd]._state == DELETE)return nullptr;else if (_table[hashadd]._state == EXITS)return &_table[hashadd];}// 没找到找下一个位置hashadd++;// 碰到尾部就回到开头去找if (hashadd == _table.size()){hashadd = 0;}}// 走到这里就是遇到空位了，就是找不到return nullptr;}

删除接口的实现：

	// 除留余数法 + 线性探测实现哈希表的删除bool erase(const K& key){// 删除特别简单，代码复用即可HashData* ret = Find(key);if (ret){// 这里不能真删除，只能未删除，修改状态即可ret->_state = DELETE;--_num;return true;}else{return false;}}

关于什么时候扩容的一些解释：

个人对哈希表什么时候扩容的一些总结：

哈希表是不能满的，哈希表接近满的时候，哈希冲突概率大，效率很低

如何解决呢？这里需要引入一个负载因子的概念

负载因子————表中有效数据个数/表的大小【用来衡量哈希表满的程度】
负载因子越大，表越满，越容易哈希冲突，效率越低，负载因子越大，表越空，效率越高，浪费空间越大
因此哈希表不是满了才增容，在开放定址法中，一般负载因子到0.7左右就要增容

如何扩容？

这里对哈希表的扩容并不是想的那样直接开个空间并且拷贝数据那么简单

为什么?

因为哈希表的空间变大了，代表这映射关系也随之改变了，之前哈希表的数据要重新映射到新的哈希表中，再删除旧空间

下面举个例子：

可以看到，原来表的大小是10，数据按照10来映射，现在扩容后的表是20，就要按照20来映射

增容代码如下：

	// 构造函数HashTable(size_t capacity = 3):_num(0),_table(capacity) // 哈希表创建空间 【本质是vector<HashData<T>> _table(capacity)】{for (size_t i = 0; i < capacity; i++){_table[i]._state = EMPTY; // 设置状态}}void CheckCapacity(){if (_num * 10 / _table.size() >= 7) // *10是因为两个整数无法除成小数{// 只要负载因子大于0.7就增容HashTable<K, T, KeyOFT> newtable(_table.capacity() * 1.5);for (int i = 0; i < _table.capacity(); i++){if (_table[i]._state == EXITS)newtable.Insert(_table[i]._data); // 将原哈希表的数据按照新的映射关系存储到扩容的哈希表中}// 然后交换_table.swap(newtable._table); // 旧表的空间交换给了newtable，出了作用域就被释放了，不用手动释放// (this->_table).swap(newtable) 调用了vector的swap方法}}

代码思路如下：

通过构造函数来创建出新的增容后的哈希表newtable，然后将原哈希表的数据按照新的映射关系，新的哈希函数来插入新的哈希表中。最后交换，newtable出了作用域系统会释放，不需要手动释放

线性探测总结：

线性探测优点：实现非常简单，

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

如何缓解呢？可以使用二次探测

6.4.1.2二次探测

线性探测，是遇到哈希冲突之后，一个一个找新位置。即 key%表的大小 + i（i = 0,1,2,3…）

而二次探测是： key % 表的大小 + i^2(i = 0,1,2,3…)

其实二次探测和线性探测只是遇到哈希冲突之后的处理不一样，下面就直接放上代码就可以了

插入接口的实现：

	// 除留余数法+二次探测 实现哈希表的插入bool Insert(const T& d) // 返回值应该是个pair类型，这里简单化处理{// 计算d这个数据的Key在表中映射的位置// 但是d可能是Key也可能是pair，因此这里需要和之前的红黑树改造一样，需要一个仿函数来处理KeyOFT koft;// 这里哈希表的构造函数，我选择用除留余数法size_t start = hashFunc(koft(d)); // 计算余数size_t hashadd = start;int i = 1; // 用于二次探测// 这里需要一个负载因子的概念 负载因子————表中有效数据个数/表的大小【用来衡量哈希表满的程度】// 负载因子越大，表越满，越容易哈希冲突，效率越低，负载因子越大，表越空，效率越高，浪费空间越大// 因此哈希表不是满了才增容，在闭散列的二次探测中，一般负载因子到0.5就要增容//	每次将数据插入到哈希表中之前，都要判断哈希表空间是否足够CheckCapacity();while (_table[hashadd]._state == EXITS){// 哈希表需要做到数据去重if (koft(_table[hashadd]._data) == koft(d)){return false;}// 只要是有数据存在就要按照二次探测找到下一个空位hashadd = start + i * i; // 这个范围有可能越界，因此还得取一次模hashadd %= _table.size();i++;}// 只要哈希表的容量足够，走到这里就是找到空位_table[hashadd]._data = d; // 将d存储在该位置 _table[hashadd]._state = EXITS;_num++; // 哈希表的有效数据++return true;}

查找接口的实现：

	// 除留余数法 + 二次探测实现哈希表的查找HashData<T>* Find(const K& key) // 返回值按理来说给迭代器，但是这里先简单化处理{KeyOFT koft;size_t start = hashFunc(key); // 计算余数size_t hashadd = start;int i = 1; // 用于二次探测// 到碰到空位就说明该key不存在于哈希表中while (_table[hashadd]._state != EMPTY){if (koft(_table[hashadd]._data) == key){// 找到了还得判断该位置的数据是否是被删除状态if (_table[hashadd]._state == DELETE)return nullptr;else if (_table[hashadd]._state == EXITS)return &_table[hashadd];}// 没找到就按照二次探测去找hashadd = start + i * i; // 这个范围有可能越界，因此还得取一次模hashadd %= _table.size();i++;}// 走到这里就是遇到空位了，就是找不到return nullptr;}

删除接口的实现：

	// 除留余数法 + 二次探测实现哈希表的删除bool erase(const K& key){// 删除特别简单，代码复用即可HashData* ret = Find(key);if (ret){// 这里不能真删除，只能未删除，修改状态即可ret->_state = DELETE;--_num;return true;}else{return false;}}

关于二次探测的哈希表的扩容需要注意的是：

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容

因此其负载因子要控制不超过0.5，扩容代码如下：

	// 构造函数HashTable(size_t capacity = 3):_num(0),_table(capacity) // 哈希表创建空间 【本质是vector<HashData<T>> _table(capacity)】{for (size_t i = 0; i < capacity; i++){_table[i]._state = EMPTY; // 设置状态}}void CheckCapacity(){if (_num * 10 / _table.size() >= 5) // *10是因为两个整数无法除成小数{// 只要负载因子大于0.5就增容HashTable<K, T, KeyOFT> newtable(_table.capacity() * 2);for (int i = 0; i < _table.capacity(); i++){if (_table[i]._state == EXITS)newtable.Insert(_table[i]._data); // 将原哈希表的数据按照新的映射关系存储到扩容的哈希表中}// 然后交换_table.swap(newtable._table); // 旧表的空间交换给了newtable，出了作用域就被释放了，不用手动释放// (this->_table).swap(newtable) 调用了vector的swap方法}}

6.4.1.3闭散列的总结

• 闭散列优点：实现较为简单

• 闭散列的缺点：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。因为哈希冲突通过闭散列的方式来解决其实不是一个好的方式，当一个数据冲突了之后，闭散列的解决方式是去占用别的数据本来映射的空间，一旦遇到一些特殊情况，就会导致效率低下。

6.4.2开散列（重点）

开散列：开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。【也可以叫哈希桶】

如下图所示：

从上面两个图可以理解：开散列（哈希桶）在遇到哈希冲突之后，不是按照闭散列那样去找其他新的空位置，而是直接将其挂起来。

因此哈希表的实现上和闭散列就会不同。需要另外单独实现

6.4.2.1开散列的实现

开散列的大致框架：

	// 开散列的话，哈希表每个位置存储的就是哈希节点的指针template<class T>struct HashNode{T _data; // 节点存储的数据HashNode<T>* _next; // 指向下一个哈希冲突被挂起的节点 HashNode(const T& data):_data(data),_next(nullptr){}};template<class K, class T, class KeyOFT>class HashTable{typedef HashNode<T> Node;public:private:// 哈希函数size_t hashFunc(const K& key){// 除留余数法return key % _table.size();}vector<Node*> _table; // vector动态顺序表作为哈希表底层，存储哈希节点的指针size_t _num; // 有效数据个数};
}

关于开散列的扩容：

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

下面是开散列的扩容的实现：

	HashTable(size_t capacity = 5):_num(0),_table(capacity){for (size_t i = 0; i < _table.capacity(); i++){_table[i] = nullptr;}}void CheckCapacity(){// 负载因子 = 有效数据 / 表的大小// 开散列中一般控制到1if (_table.size() == _num){// 扩容HashTable<K, T, KeyOFT> newtable(_table.capacity() * 2);// 扩完容之后，按照新的哈希表将原来的数据重新映射到哈希表中for (size_t i = 0; i < _table.size(); i++){// 遍历每一个哈希桶，将桶内数据插入新的哈希表中Node* cur = _table[i];while (cur){newtable.Insert(cur->_data); cur = cur->_next;}}// 然后再交换_table.swap(newtable._table);}}

开散列的插入实现：

	// 开散列实现bool Insert(const T& data) {KeyOFT koft; // 仿函数处理T的不同类型【pair<K, V>或者K】size_t hashadd = hashFunc(koft(data)); // 除留余数法计算哈希地址// 先判断data是否存在于这个哈希表中Node* cur = _table[hashadd]; while (cur){//将该位置的所有元素都取出来对比，看看data是否存在于表中if (koft(cur->_data) == koft(data)){return false;}else{cur = cur->_next;}}// 插入之前也得通过负载因子来控制哈希表的效率【尽管哈希桶是不会装满的，但是一个桶的数据太多会导致效率降低】// 开散列的负载因子是1左右CheckCapacity();// 走到这里就说明data不存在表中，并且链式表的容量合理，可以插入// 插入的话要头插到映射位置的桶里【头插尾插都可以，但是头插效率高】Node* newnode = new Node(data);newnode->_next = _table[hashadd]; _table[hashadd] = newnode; ++_num; // 有效数据++return true;}

开散列的查找实现：

	// 开散列实现哈希表的查找Node* Find(const K& key) // 实际上返回迭代器，这里简单处理{KeyOFT koft;// 按除留余数法存的，要根据除留余数法找size_t hashadd = hashFunc(key);Node* cur = _table[hashadd]; // 记载桶的初始位置//在这个桶里（链式表）里找数据是否存在while (cur){if (koft(cur->_data) == key){return cur;}cur = cur->_next;}return nullptr; // 没找到返回空}

开散列的删除实现：

	// 开散列实现哈希表的删除bool erase(const K& key){// 由于是开散列，删除实际上就是对单链表（桶）做删除KeyOFT koft;size_t hashadd = hashFunc(key);Node* cur = _table[hashadd];Node* prev = nullptr; // prev指向cur的上一个位置while (cur){// 找到了就要删除if (koft(cur->_data) == key){// 这里分两种情况，一种是cur指向头，此时是头删，一种是中间删除if (prev == nullptr){_table[hashadd] = cur->_next; // 直接让下一个成为链表首元素}else{prev->_next = cur->_next;cur->_next = nullptr;}delete cur; // 处理完节点关系，就释放掉cur = nullptr;}else{// 没找到就迭代cur = cur->_next;prev = cur;}}return true;}

6.4.2.2开散列的思考

• 如果存入的数据哈希冲突的很厉害，总是频繁的增容，如何解决呢？

如果一个链表特别长，超过了一个定值，那么就将挂单链表改为挂红黑树。这样哪怕冲突几百万个数据在一个红黑树上，找一个数据最坏也就是logn级别的次数，效率几乎可以看成O(1)

在java中的HashMap就是这样干的，当桶的长度超过了8，就要改为挂红黑树

cpp中的unordered_map和unordered_set没有这样处理

• 上面的哈希表中，因为用的是除留余数法，其实只能处理整形的数据。如果处理其他类型的数据呢？

// 哈希函数采用处理余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法
// 整形数据不需要转化
template<class T>
class DefHashF
{
public:size_t operator()(const T& val){return val;}
};
// key为字符串类型，需要将其转化为整形
class Str2Int
{
public:size_t operator()(const string& s){const char* str = s.c_str();unsigned int seed = 131; // 31 131 1313 13131 131313unsigned int hash = 0;while (*str){hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF);}
};
// 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起
template<class V, class HF>
class HashBucket
{// ……
private:size_t HashFunc(const V& data){return HF()(data.first)%_ht.capacity();}
};

各种字符串Hash函数 - clq - 博客园

• 开散列和闭散列的比较

应用链地址法处理溢出(哈希桶)，需要增设链接指针，似乎增加了存储开销。

事实上：

由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。