目录
1. “哈希”是什么?
2. 哈希冲突
3. 哈希函数
3.1 设计原则
3.2 常见哈希函数
4. 解决哈希冲突的两种常见方法
4.1 闭散列
4.2 开散列
4.3 散列表的扩容问题
5. 哈希表的实现 并 封装模拟实现unordered系列容器
6. 哈希的应用
6.1 位图 -- bitset
6.2 布隆过滤器 -- Bloom Filter
1. “哈希”是什么?
在进入正题之前,先带大家看一下什么是序列式/关联式容器:
比如:vector、list、deque、 forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。
关联式容器也是用来存储数据的,与序列式容器不同的是,其底层为非线性结构,且里面通常存储的是<key, value>结构的键值对。
在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系列容器;哈希的应用等。
2. 哈希冲突
也叫哈希碰撞,即不同关键码通过 同一哈希函数 映射 到同一位置。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
比如,现在要在上述点1的示例一中插入元素16,即key为16,Hashi(16) = 16 % 10 = 6,但是此时6地址处已有元素,于是发生冲突。
那么发生哈希冲突该如何处理呢?
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。
3. 哈希函数
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. 解决哈希冲突的两种常见方法
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 % 7
h2(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及其以上。
5. 哈希表的实现 并 封装模拟实现unordered系列容器
点击 my_unordered_set/map 前往我的Gitee仓库获取参考代码。
6. 哈希的应用
本大点主要介绍如何运用哈希思想解决海量数据(几亿个,几十亿个,几百亿个......)的处理处理问题,并由此设计出的一些 结构 或 模板。
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位置映射的位标记成1bitset& set(size_t pos){assert(pos <= N);size_t i = pos / 32;size_t j = pos % 32;_bits[i] |= (1 << j);return *this;}// 把pos位置映射的位标记成0bitset& 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;
}
本文至此就结束了,如果对你有所帮助,就是对小编最大的鼓励,可以的话 三连并留下你的评论 也是小编坚持创作的不懈动力,持续更新中!