目录
5. 哈希表的实现 并 封装模拟实现unordered系列容器
“哈希"是什么？
在进入正题之前，先带大家看一下什么是序列式/关联式容器：
比如：vector、list、deque、 forward_list(C++11)等，这些容器统称为序列式容器 ，因为其底层为线性序列的数据结构，里面存储的是元素本身。
关联式容器 也是用来存储数据的，与序列式容器不同的是，其底层为非线性 结构，且里面通常存储的是
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器（set/map/multiset/multimap），在查询时效率可达到log_2 N，即使最差情况下也只需要比较红黑树的高度次，相较 序列式容器的线性查找 效率更高；但当树中的节点非常多时（海量数据），查询效率也不理想。
由此可以得到结论：搜索的效率取决于搜索过程中关键码的比较次数。
那么最理想的搜索方法就是：可以不经过任何比较，直接就能将元素找到；或者退而求其次，将整体的比较次数降到最低。
至于如何做到呢，就是本文的重点 ——哈希：构造一种存储结构，让其可以通过某种方法，使关键码（key）和 其存储位置建立一 一对应的映射关系。
当向该结构中：
插入元素时： 根据待插入元素的关键码，以这种方法得到该元素的存储位置并按此位置进行存放。
搜索元素时： 对元素的关键码进行同样的计算，得到存储位置，在结构中按此位置取元素决定是否搜索成功。
这样的方法就称为：哈希函数（hashfunc）
构造出来的结构称为：哈希表或散列表
如下示例一：
至此，就可以回答最初的问题：“哈希"是什么？—— “哈希” 是一种数据结构和算法的思想，通俗点说就是一种解决问题的思考方式和处理手段；不是某种具体的数据结构或容器。
而在C++11中，STL提供的4个 unordered 系列的关联式容器，其底层结构就是用 哈希思想 实现的。
（关于unordered系列容器的接口使用与红黑树结构的关联式容器使用方式基本类似，此处不赘述，可点击查看在线文档说明：unordered_map ，unordered_set ，unordered_multimap ，unordered_multiset )
接下来，本文将围绕以下内容展开： 哈希函数的设计和选择；会产生的问题(哈希冲突)及如何解决；改造模拟实现unordered系列容器；哈希的应用等。
哈希冲突
也叫哈希碰撞，即不同关键码通过 同一哈希函数 映射 到同一位置。
把具有不同关键码而具有相同哈希地址的数据元素称为"同义词”。
比如，现在要在上述点1的示例一中插入元素16，即key为16，Hashi(16) = 16 % 10 = 6，但是此时6地址处已有元素，于是发生冲突。
那么发生哈希冲突该如何处理呢？
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数
3.1 设计原则
哈希函数的定义域必须包括需要存储的全部关键码；而如果散列表允许有m个地址时，其值域(h哈希地址)必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中——>尽量减少冲突
哈希函数应该比较简单
3.2 常见哈希函数
1. 直接定址法（常用）
直接用关键码做哈希地址
优点：简单
缺点：需要事先知道关键码的大小分布情况；可能造成较大空间浪费
只适用于：元素集合的关键码较小且连续的情况。比如：找出字符串中只出现一次的英文字母，就可以建立数组，直接用字母的ASCII值做哈希地址 进行次数统计。
2. 除留余数法（常用）
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数， 按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。如上述点1的示例一。
3. 平方取中法
假设关键码为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键码为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。
平方取中法比较适合：不知道关键码的分布，而位数又不是很大的情况
4. 折叠法
关键码从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这 几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键码的分布且位数比较多的情况
5. 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。
通常应用于关键字长度不等时采用此法
6. 数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀，只有某几种符号经常出现。此时可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
比如：假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的4位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环移位(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的 若干位分布较均匀的情况
……
上述所有方法的共同点是：关键码都是整型才能得到整形哈希地址，但是实际上的关键码key可以是任何类型，以常见的 string 来说，如何在使用上述方法求哈希地址前将其转换成整形，可减小冲突概率呢？点击查看各种字符串Hash函数对比
总的来说，在哈希函数的设计上，留给我们的发挥空间更大了，但于此同时，我们要考虑的东西也更多了，对能力的要求也提高了不少，而这恰恰也是我们对自己的要求和学习的动力！
回到正题：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。
至于如何解决这个问题，我们接着往下看。
解决哈希冲突的两种常见方法
4.1 闭散列
也叫开放定址法 ，一种将所有数据存储在散列表本身的方法。
插入元素时，如果发生哈希冲突，并且哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的 “下一个” 空位置中去。 （这里暂且假设表的空位置充足）
还是以点1的示例一为例，继续依次插入元素16，9，19；结果如下：
这种方法就叫做线性探测，下一个探测位置的Hashi = (current_position + i) % table_size。【i 是探测的步数，上述示例取为1（常用）】
查询也是如此，但是如果表中没有你要查找的元素时，终止此操作的条件又是什么呢？—— 遇到空位置，表明这个位置从始至终没有元素。
关键是现在还有一个操作：删除。表中某位置进行此操作后，此时这个位置的数据状态应该认为就是空 呢，还是需要一个新的 删除状态呢？如果遵循前者设为空，假设要查询的元素均在表中，第一次查询刚才被删除的元素，发现对应位置为空，终止查询，没有找到，返回结果为失败，这个过程是正确的；但是再一次查询另一个元素时，因为存在哈希冲突，导致此次查询元素的存储位置在已删除元素的位置"后面”(逻辑意义上的，因为线性探测是从冲突位置往后的，如上图示例，可能又从表头开始)，而查询遇到空就终止，因此就会发生漏查的情况。
所以，我们实现时，散列表的每个位置的数据状态至少有三种情况：Empty，Exist，Delete。插入时的"空"包括Empty 和 Delete；查询终止时的"空"则只指Empty；并且有了Empty后，只需修改状态就行，无需改动数据，属于"伪删除”。
线性探测的优点是：实现非常简单。
但缺点也很明显：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据"堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
这与其找下一个探测位置有关系，所以出现 新的探测方式 “二次探测”，也叫平方探测，来缓解这个问题；其下一个探测位置的Hashi = (current_position + c1 * i + c2 * i^2) % table_size。它的特点是：步长不再是固定的，而是根据冲突的次数而变化；这样，即使两个关键字产生相同的初始散列地址，它们在探测过程中也可能分散到不同的位置。
【c1和c2是常数参数，它们可以任意选择，但通常会根据实际情况进行调整。常见的选择方式是c1 = c2 = 1，或者c1 = 1，c2 = -1。这些选择可以在一定程度上减少哈希冲突的发生，提高哈希表的性能。然而，具体选择哪个常数值是根据实际问题和性能需求来确定的，不是任意选择的。
i 通常的初始值为0，然后逐步增加至1、2、3，以此类推，直到找到可以插入元素的位置或者遍历完整个哈希表。
】
除此之外，再介绍一种方法： 双重散列法。其特点为：通过引入第二个哈希函数来降低冲突概率。
其下一个探测位置的Hashi = (h1(key) + i * h2(key)) % table_size。【h1和h2分别表示两个不同的哈希函数，i 是探查次数】
具体做法为：首先使用第一个哈希函数h1将关键码映射到一个位置；如果该位置已经被占用，则使用第二个哈希函数 h2(key) * i 做增量值（通常确保 h2(key) 不等于零，以避免陷入死循环）找下一个探查位置。
举个例子：
假设有一个哈希表 table，大小为 7。我们要插入键 key1 = 5，key2 = 12 和 key3 = 19。
哈希函数定义：
h1(key) = key % 7h2(key) = 1 + (key % 6)（注意：确保h2(key)不为零）插入
key1 = 5：计算
h1(5) = 5 % 7 = 5位置5为空，将
key1插入位置 5。插入
key2 = 12：计算
h1(12) = 12 % 7 = 5计算
h2(12) = 1 + (12 % 6) = 1位置 5 已经被占用，因此用步长 1 探查下一个位置
(5 + 1 * 1) % 7 = 6，将key2插入位置 6。插入
key3 = 19：计算
h1(19) = 19 % 7 = 5计算
h2(19) = 1 + (19 % 6) = 2位置 5 被占用，因此用步长 2 探查下一个位置
(5 + 1 * 2) % 7 = 7 % 7 = 0，将key3插入位置 0。
其它的方法，如：再哈希法（Rehashing），伪随机探测法（Pseudo-random Probing）, Hopscotch Hashing法，Cuckoo Hashing（布谷鸟哈希），Robin Hood Hashing等等，各有优缺点，适用于不同的场景，留给大家自行探索吧！
至于如何使用闭散列自行实现一张哈希表，先不急，因为有些问题还没解决，小编在后面会给出参考代码，请继续往下看。
4.2 开散列
STL中的unordered系列容器就采用这种方法。
不同于闭散列的是：其数据是 使用指针链接到外部存储的，哈希表中存的是指针。所以，也叫链地址法（拉链法），或者哈希桶。
具体做法为：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同 一 子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
如下图例：
这种方法就不会产生4.1中的数据"堆积"问题，每个桶中放的都是发生哈希冲突的元素。
至于增删查等操作，只要找到对应的桶去操作链表就可以，此处不再赘述。
4.3 散列表的扩容问题
这个问题的核心是：决定散列表是否要扩容的衡量标准是什么？
—— 负载因子（load_factor） = 实际存的数据量 / 整个表的地址量
一般来说，负载因子越小，冲突的概率就越低，但是空间浪费就会多一些，这就类似于降低密度，减少竞争以提高产量的做法。
对闭散列来说，有研究表明： 当表的长度为质数且表负载因子不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次；因此只要表中有一半的空位置，就不会存在表满的问题。此时在搜索时就可以不考虑表装满的情况，但在插入时必须确保表的负载因子a不超过0.5，如果超出必须考虑增容。此时空间利用率比较低，这是闭散列最大的缺陷，也是哈希的缺陷。
因此，在有些版本的STL源码中，在扩容时的容量选择上有类似如下代码：
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
};
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
但实际一般情况下，开放定址法的负载因子通常设置在0.7到0.75之间。这个范围是为了在保证较高的存取效率（如查找、插入和删除操作的时间复杂度）与内存利用率之间取得平衡。
而对开散列来说 ，桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下 ，可能会导致一个桶中链表节点非常多，影响散列表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点， 再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容 。所以，开散列的负载因子一般在1及其以上。
哈希表的实现 并 封装模拟实现unordered系列容器
点击 my_unordered_set/map 前往我的Gitee仓库获取参考代码。
哈希的应用
本大点主要介绍如何运用哈希思想解决海量数据（几亿个，几十亿个，几百亿个……）的处理处理问题，并由此设计出的一些 结构 或 模板。
6.1 位图 – bitset
概念：就是用每一位（二进制bit位）来存放某种状态。
通常是用来判断某个数据存不存在的，比如 1表示存在，0表示不存在。
其底层结构设计采用哈希思想，属于直接映射，即哈希地址就是关键码key，所以决定位图容量大小的是数据本身的大小范围，而不是数据个数，所以没有哈希冲突。
如下图例： 
那么如何运用到具体场景中呢？下面是小编总结好的一些示例：
示例1：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯面试题】
变形1： 给定100亿个整数，设计算法找到只出现一次的整数?
变形2：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集?
示例2： 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
这种分割方式就叫做 哈希切割，其不同于 平均切割 的地方是：它在切割的同时还有"分类"的作用，即将共性更高（发生哈希冲突）的数据集中到一起，可以说，这种分割方式是有着很强且明确的 目的性 的，更有利于解决复杂问题。
同样的方法，还有下面的变形1:
变形1：给两个文件，分别有100亿个query(查询，即字符串)，我们只有1G内存，如何找到两个文件交集？
相信这几个例子会加深你对哈希的自我理解！
接下来，就是简单模拟实现STL中的类模板bitset：
参考代码：
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 32 + 1, 0);
}
//三个核心操作
// 把pos位置映射的位标记成1
bitset& set(size_t pos)
{
assert(pos <= N);
size_t i = pos / 32;
size_t j = pos % 32;
_bits[i] |= (1 << j);
return *this;
}
// 把pos位置映射的位标记成0
bitset& reset(size_t pos)
{
assert(pos <= N);
size_t i = pos / 32;
size_t j = pos % 32;
_bits[i] &= ~(1 << j);
return *this;
}
bool test(size_t pos) const
{
assert(pos <= N);
size_t i = pos / 32;
size_t j = pos % 32;
return _bits[i] & (1 << j);
}
private:
vector<int> _bits;
};
至此，小结一下位图的几种常用场景：
1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3.求两个集合的交集、并集等
4. 操作系统中磁盘块标记
6.2 布隆过滤器 – Bloom Filter
设想现在有这么个场景： 字符串 “baidu” 在 位图 中 set()，通过某哈希函数转换后的映射位置是 pos1；此时查询字符串 “jingdong”（从未set() 过） 是否存在，发现映射位置也是pos1，如果 “tengxun” 也映射到pos1，…… ，就会返回错误的结果，进而可能影响后序操作。
前面我们说过，这种情况叫 哈希冲突，而引起 此 的一个重要原因是：哈希函数设计不够合理。那么是不是说只要重新设计哈希函数就能解决这个问题呢？理论上确实如此，但是实际情况是：你的 数学分析能力 真的能找到把 海量数据中的每一个不确定性 都变成 相对唯一性 的一种方法吗？
想必你已经在摇头了，这着实也不是个 “经济划算” 的事。
【那么，不如转换一下思路，虽然我们在哈希函数 的 “质” 上能力有限，但在“量” 上，可以使用多个哈希函数，即每个元素映射多个位置。查询某个元素时，只要其中任意一个映射位置状态为空，就可以确定这个元素一定不存在 ；如果每个映射位置状态都为非空，那大概率这个元素存在 ，较小概率不存在 ，因为映射位置可能产生的冲突是无法避免 的，如下图例。】
此时查询 “baidu” , 就只能说其可能存在。
但相较于 位图 的单个映射，误判的概率大大降低了！
这便是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，可以用来告诉你 “某样东西一定不存在或者可能存在”。
比如，下面的这个模型：
资讯，广告，视频推荐也是相似的道理。
那么，如何选择合适的 哈希函数的个数和布隆过滤器的长度，将误报率尽可能的降低呢？
如下统计：
计算m和K的公式：
下一个问题：可以删除吗？
传统的布隆过滤器并不支持删除操作，因为存在哈希冲突导致相互影响，如上示例图（“baidu”, “tengxun”），但如果把每个位置改成多位的 引用计数 就可以支持 ，但也可能产生新的问题，如"计数回绕”；可参考文章 Counting Bloom Filter 的原理和实现
下面给一段传统布隆过滤器的简单实现和测试 参考代码：
template<size_t N,
class K = string,//常用的数据类型：字符串
class Hash1 = HashFuncBKDR,//前面给过的：字符串哈希函数
class Hash2 = HashFuncAP,
class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
BloomFilter& set(const K& key)
{
size_t hash1 = Hash1()(key) % M;
size_t hash2 = Hash2()(key) % M;
size_t hash3 = Hash3()(key) % M;
_bs->set(hash1);
_bs->set(hash2);
_bs->set(hash3);
return *this;
}
bool test(const K& key)
{
size_t hash1 = Hash1()(key) % M;
if (_bs->test(hash1) == false)
return false;
size_t hash2 = Hash2()(key) % M;
if (_bs->test(hash2) == false)
return false;
size_t hash3 = Hash3()(key) % M;
if (_bs->test(hash3) == false)
return false;
return true; // 存在误判(有可能3个位都冲突)
}
private:
static const size_t M = 10 * N;
std::bitset<M>* _bs = new std::bitset<M>;//避免数据量过大时，有些编译器实现的std::bitset<N> 开的是静态数组，有栈溢出的风险
};
//测试：一般来说，同一个K值，如果空间加大，映射位置变多，理论上会降低误判的概率
#include<time.h>
void TestBloomFilter()
{
srand(time(0));
const size_t N = 1000000;
BloomFilter<N> bf;
std::vector<std::string> v1;
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
std::string url1 = "你好";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.set(str);
}
// v2跟v1是相似字符串集（前缀一样），但是后缀不一样
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string urlstr = url;
urlstr += std::to_string(9999999 + i);
v2.push_back(urlstr);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.test(str)) // 误判
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
// 不相似字符串集 前缀后缀都不一样
std::vector<std::string> v3;
for (size_t i = 0; i < N; ++i)
{
string urlstr = std::to_string(i + rand()) + url1;
urlstr += std::to_string(i + rand());
v3.push_back(urlstr);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
本文至此就结束了，如果对你有所帮助，就是对小编最大的鼓励，可以的话 三连并留下你的评论也是小编坚持创作的不懈动力，持续更新中！
原文链接: https://blog.csdn.net/m0_74171054/article/details/141782642