-
哈希（开散列、闭散列）-位图-布隆过滤器-哈希切分
文章目录
unordered系列的关联式容器之所以效率比较高是因为底层使用了哈希表结构unordered_set相较于set功能相同但是效率更高，插入随机数时重复比较多百万级别相差时间已经是10倍关系。
并不是绝对的效率优势，在有序的情况下就是set更高效率。
实验：测试效率对比。练习：两个数组的交集：两个unorder_set中，在就是交集不在就不是交集。要有去重的效果。或者用set先有排序加去重的操作，谁小谁就加加，相等就是交集，再同时++。
1、哈希概念
顺序结构以及平衡树中，元素关键码和存储位置之间没有对应的关系，所以每次查找都要进行多次的比较。
在查找的过程中能够不通过任何的比较，一次性从表中得到想要搜索的元素是理想的搜索方式。
如果构造一种存储结构，通过某种函数（哈希函数）使得元素的存储位置和他的关键码之间能够建立一一映射的关系，那么在查找时通过该函数很快就能找到该元素。
这个函数构造出来的结构（哈希表）插入元素时，根据待插入元素的关键码，以此函数计算出该函数的存储位置，并且按照此位置进行存放，搜索元素时，对该元素关键码进行同样的计算，把求得的函数值当作函数的存储位置，在结构中按照这个位置拿元素关键码，相等则搜索成功。
2、哈希表/散列表
（1）哈希函数的设计：
（2）（最常用）除留余数法：
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函 数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。但是可能两个数余数相同，导致两个不同的值插入到一个位置中导致位置冲突，就叫做哈希冲突（碰撞）。
（3）如何解决哈希冲突？更加合理的设计哈希函数
-
闭散列（开放定址法）：
如果发生冲突，就将他放到有空位置的地方。
（1）线性探测：从发生冲突的位置依次向下探索，到下一个空位置的地方- 问题一：
我们知道，在查找时到空就说明要结束了，因为线性探测得到的应该是挨着的数据组。
当删除的中间位置x时就会出现歧义，因为原来这个地方x不是空，所以将冲突的数据y放到了x后面，所以在查找y时遇到x的位置为空就会停下来，不知道是不是y原先没有的，你去向后遍历，你知道遍历多久会找到吗？效率更低，所以
可以用加标记的方式区别是删的还是没有的->枚举状态标识，枚举就是常量。不删除数据，只是将标记位改动，下次插入依然可以，叫做伪删除法。遍历查找遇到他时，只要不是空就不停止。
- 问题2：有人占了我的位置，我就往后走直接占别人的位置，导致插入的值过于拥挤的分配到表格中，连续位置的值比较多，引发踩踏洪水效应。
（2）二次探测（缓解踩踏洪水）
start+i^2,也就是寻找空位时步子迈的大一点，+1,+4,+9……可以在范围内绕更多的圈来找到空位置，让位置更加分散。但是不管怎样探测，都会存在冲突的概率很大，所以要适度的扩容，让冲突尽量减少。
已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行（N*(N+1)/2）次探测
- 问题三：什么时候进行扩容？
计算负载因子，大于0.7时进行扩容，负载因子越小，冲突概率越低，效率越高，空间浪费越多，因为永远有30%的空间利用不上，到0.7就扩容了啊。
如果是第一次进来，将开空间的步骤也可以加进来。
- 问题四：扩容时用resize
resize()扩完容之后空间大小size改变了，那么数据存好的位置(/size)是不也发生变化了呢？就会重新建立映射关系，代价更大。如果我们另找一个更大的数组vector开空间，然后再拷贝数据到新数组，随后交换一下指针就行，但是在插入到新数组的时候仍然会重新计算大小有映射的重新建立，所以我们直接开一个新的哈希表，负载因子也不会超，新表插入的时候直接给他新的位置，按照新表走，可以实现代码的复用，交换新的哈希表中的tables。
- 问题五
存在相同的值可以继续插入，所以还可以实现去重的功能。
Find()函数，暴露出来的问题：
- 第一次插入的时候要处理除零错误计算位置时。
- Data是resize出来的会调用构造函数需要进行初始化，所以我们可以给枚举类型一个缺省值。
- 删除的时候是伪删除，只是将状态码进行改变，这样在根据Key查找的时候即使删除仍然能获得地址信息，所以我们要在find是加上对于状态的区分。
- 问题六：
如果key是string类型，如何确定他的位置呢？无法用key进行大小取模了，可以取首元素的ASCII码，或者string转化为一个整形值就可以了，HashFunc专门给字符串准备的仿函数将所有的ASCII码值相加，实现区分。但是会出现顺序不同但是数的和相同的情况解决不了，字符串是无限的情况，size_t有限，冲突肯定是不可避免的，所以引入字符串哈希算法（BKDRHash），需要乘上一个特定的转化因子来减少冲突。之后操作中所有的取模都可以用这个仿函数处理一层，整数就转整数，字符串就转字符串。HashFunc仿函数模板参数再给个缺省值，避免整形也走这个处理字符串的不通的问题，只要你的Key能够实现隐士类型转化为size_T类型，就直接返回size_t无符号整数（负数可以插入吗？问题七）。字符串类型需要走偏特化版本特殊处理字符串。当以后key类型是自定义类时，只需要声明一个特定的仿函数，将key类转化为一个size_t 类型来支持取模操作。
- 问题七：为什么非的是无符号数呢？
负数是可以取模的，那么可以取abs()绝对值，但是会和正数冲突。所以转化为无符号，负数变成一个很大的值就行了。所以仿函数很重要，STL六大组件之一。
- 问题八：
闭散列这种线性探测会造成冲突数据互相影响，相邻位置的冲突会争抢位置，极端的情况就是很多值堵在一部分，负载因子还没有达到的那种恶心人的场景，传销是吧！优化：
-
开散列/拉链法/哈希桶/链地址法
相邻位置冲突不会再争抢位置，不会互相影响。
头插，二维的将冲突的数字进行链表排列，相邻位置冲突就不会再互相影响。
但是也可能会存在极端情况，一个桶里面就是有很多的值，所以需要控制负载因子–负载因子到了就扩容，扩容之后就会有重新的映射，让极端情况得到缓解。Java中当一个桶的值超过一定长度之后，就转换为红黑树，防止一个桶的值位置太多，链表太长。
问题一：
闭散列中扩容是找了一个新的哈希表,复用insert，再交换。那开散列不行，开散列开辟一个新的tables，遍历原表，需要将内些节点一个个拿下来，然后重新映射到新的tables中。
如果是像闭散列中开辟一个新的哈希表，new出一个新的节点拷贝构造之后放到新大小的tables中，还要将原来的节点进行释放，数据量很大时造成空间的浪费。能不能还用原来节点直接映射呢？不能将原来的桶直接拿下来，因为新的大小tables映射就变了。
3. map中的key需要满足什么样的要求呢？
map中的key需要能够进行小于比较或者转化为小比较的。
Key类型对象支持小于比较或者传递一个小于的仿函数，小于号两边值换边就是大于了。
4.unordered_map的key类型的对象要求
能支持取模或者支持转化为取模的无符号整数，支持key比较相等或者相等仿函数，下图模板参数的仿函数比较时不是自己想要的就得自己写一个。
仿函数作为模板参数还是使得容纳量的增加，就是接口很多的口子，让更多的自定义类型去比较大小有自己定义的空间。
3. unordered_map和unordered_set的用哈希表底层实现
（1）模板参数KeyOfT和HashFunc
unordered_map是K-V类型，所以传值的时候传的是两个，unordered_set是K类型。传值的时候为了配合泛型编程所以传了两个K,传到哈希表是K-V都是K,配合适配。
在HashTable的初始化中为了泛型也多声明的两个模板参数。- 返回key时为了包含k和pair
- 将各种类型转化为size_t 类型来进行size_t/size()进行定位，所以HashFunc仿函数（缺省和特化）。
（2）哈希表如何支持迭代器？
一个桶的一个桶的找
-
迭代器里面放什么？才能实现加加操作
存放节点指针之外，再存放一个指向哈希表对象的指针来找下一个不为空的桶。
哈希表对象的指针加节点的指针构造迭代器
这种思想替代了传vector当中某一个节点的地址指针，直接传到的是哈希表的指针，先把表头算出来再去找。
this就是这个哈希表对象的指针
迭代器的结尾是最后一个节点的下一个位置就是空，所以end()使用nullptr初始化。
typename 等到后面的类模板实例化之后再去类模板里面找Iterator，取模板里面的内嵌类型，要加一个typename.!=用节点的指针进行迭代器相等与否的比较。
-
问题：
- 互相引用：哈希表中用迭代器，迭代器中有哈希表的定义。加上前置声明，先让他允许，是个类模板。
- 友元处理权限问题，不让迭代器访问tables。
（3）补充函数接口
-
拷贝构造->operator()，完成深拷贝
HashTable拷贝构造的实现operator()
增加之后，就不会自动产生HashTables的默认构造函数了，只要你写了某种形式的构造就不会产生默认构造了，但是报错的时候报的是unordered_map/set没有默认构造函数，因为他是我们实现的自定义类型会调用他底层的哈希Table的默认构造函数。- 解法一：显示的写一个。会走初始化列表阶段，会调用vector的默认构造函数，内置类型是需要缺省值的。
- 解法二： HashTable的默认构造=default，显示指定编译器去生成。
-
赋值->operator=()，深拷贝现代写法
-
Find()函数返回值返回节点迭代器，operator[]返回key值对应的value.
-
析构函数~HashTable(){}
-
哈希大小最好用 素数。扩容只有的大小不一定是素数，所以提供一个素数表，大小二倍增长然后都是素数
素数表的最大到42亿，不能再大了就会内存不足
直接定址法（拓展）本质也是一种哈希映射
整数32位，假如分成4组，每组8位，每组映射2^8bit位的层，查找一个数字最多查找4层。先取高8位确定第一层位置，无法确定的话，再用次8位在第二层中找。从高往低位找。除留余数法本质也是确定一个位置，直接定址法可以开一层，可以开多层，每层确定位置，各层拼接得到各层可存储的位置实现多层位置唯一确定存储。
哈希表的时间复杂度O(1)。
哈希表大小用素数最好，可以减少映射的冲突
扩容的地方，扩容之后不一定是素数的。所以提供一个素数表，扩容的时候在素数表中拿值，获取下一个素数。
4. 位图的应用
题目：
-
给40亿个无符号整数，没排过序，如何判断一个数是否在这40亿个数中？
40亿如果是排过序的，二分查找大约查找32次就够。
如果放到红黑树或者哈希表会占用多少空间？40亿个整数，234B=224KB=214MB=24G=16G,外加上数据结构的内在消耗，什么孩子指针颜色标记什么的，表的指针，内存放不下。
所以推荐使用位图，直接定址法映射：
-
这题，我们只需要判定在还是不在，空间开不了，开多少个 位 就行，谁有就把这个位标记位1。 40亿个整数，每一个值一个比特，4B->16G，1B=2^8bit=32bit，所以1bit->16G/32 = 500M大小空间,这个大小是可以承受的，一共开了42亿个比特位，开空间应该按照范围去开，不是只在1~40亿中，范围最大到42亿，因为是直接映射。
-
怎么开N个比特位？char是1byte->8bit的开，确定每一个分区的大小这样整体的开，比如8个bit一个字节的开，每个字节多开一个bit位避免出现不整除导致有的值无法映射。比如100/8=12.5，所以多开1Byte，避免那一小部分出现时没有地方映射。
-
如何确定他在第几个分区（第几个char呢？）
比如 i=10/8=1; i表示的是第几个Byte分区中，j=10%8=2; j表示的是第几个bit中存放着你的信息，表示你在或者不在。在，就将你那一bit设置为1，不在就重置为0。
-
如何设置
bits[i]的第j个比特位=1呢？假设右边低左边高位进行存储bits[i] |=(1<
-
- 1
如何设置某一位reset为0呢？
找一个数，那一位是0，其他位是1，按位与设置。
bits[i] & =(~(1<- 1
-
-
如何检验那一位是1？
先找到你的区，再按个bit用1按位与，为1 说明那一位就在，为0代表不在。
return bits[i]&(1<
- 1
所以，用fstream将值读入并且用set设置到500M内存中，oxffffffff或者-1或者UnsignInt的宏。
- stl中也有位图，bitset,set();reset();test();
给定100亿的整数把出现一次的数字找出啦
位图的变形，100亿整数占用40G空间，最大范围是40亿个数，所以肯定是存在出现多次的情况，本题只需要找一次，所以只需要记录1次和多次的区别。一个位图只能表示0或者1，现在用两个比特位表示[0~4),两个比特位表示一个值，用两个位图来实现。
00 01 10及以上，出现一次加一就行.
#include
template
class TwoBitSet
{
void set(size_t n)
{
//00->01
if (!_bs1.test(n) && !_bs2.test(n))
{
_bs2.set(n);
}
//01->10
else if (!_bs1.test(n) && _bs2.test(n))
{
_bs1.set(n);
_bs2.reset(n);
}
//10表示2次及以上就不用处理了
}
void PrintOnceNum()
{
for (size_t i = 0; i < N; i++)
{
if (!_bs1.test(i) && _bs2.test(i))//01
{
cout << i << endl;
}
}
}
private:
bitset _bs1;
bitset _bs2;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
整数是按照范围去开辟空间的，范围就是42亿，有100亿甚至更高都只是出现了重复的值，所以我们只需要500M内存就可以概括，建立映射，位图的本质就是哈希。
- 法一：一个文件中的整数set放到位图里面，另一个按个去判断在不在，在就是交集，但是交集中会多次把重复值找出来。还需要考虑去重。
- 法二：一个文件中的整数set放到位图里面，另一个文件中的整数set大位图二，位图和set都是具备去重的功能的，位被标记了就不会重读被标记了。遍历bs1中的值，看在不在bs1中；或者两个位图按位与一下，与完之后是1的位置就是交集。
1 个文件有100亿个int，1G内存，设计算法找到出现次数不超过两次的？
节省空间，效率高O(1)的时间复杂度。
局限性：只能处理整数
- 那标记一堆字符串，或者自定义类型怎么处理呢？
先将字符串转成对应的一个整数就像哈希表里面一样，然后进行标记位进行标记从而节省空间
- 如何判定在不在呢？还能用对应下标下是否为1或者0呢？
哈希冲突导致误判而不能使用，结果中判定在会有误判，不在的结果是准确的，没消息就是好消息，判定在的话可能是冲突值设置的。
位图用的是直接定址法不怕冲突，因为整数的数量就那么多，每个位置都是整数的唯一标识。
而字符串是没有限制数量的，引入布隆过滤器进行处理。
5. 布隆过滤器（基于位图）
实现黑名单系统,爬虫去重问题(爬过的网站就别爬了)
如果用哈希表裸实现黑名单信息的记录,内存要求太大了.
允许一定程度的失误率,只可能出现我把白名单的误报为黑名单中内容,认为设计可以降的很低,但是失误率不可避免.
虽然无法排除误判冲突，那么我们可以降低误判率：
映射一个位置会有冲突，那我用多个算法一次映射多个位置共同保存呢？
就降低了很多对于某一个字符串误判的情况，不可能多个位置都和别人冲突吧！
100亿个数
使用m个bit位组成一个数组
数字u1,调用n个HashFunc函数得到n个out值,out%m得到应该在哪一个格子,描黑.
…
直到100亿个数.
如何判断某个值是否是黑名单的呢?
num再调用K个哈希函数得到out值,这k个格子必须都是黑的才能确定这个值是黑名单,只要是,就不可能存在白格子.
影响因素:
- 位图大小m.越大误判越小
- 哈希函数(特征点选择)的选择K个:受到m大小的影响的, 当选择更多的HashFunc时,误判率会逐渐降低,但是存在临界点,因为函数越多描黑的点越多,当m值不合适时,就会造成函数越多误判率提升的情况,所以当m确定时,一定存在最低点,此时的k个数是最好的.
当然了,如果m值能够更大,使得最合适的k个函数更多,误判率会更低.
底层依然是用位图进行映射，能转换成整数最好，最常用的也是整数
使用的还是非类型模板参数，size_t N,多个HashFunc算法来转整数实现将一个值映射到不同的位置中，等等，注意模板参数的缺省值是从右往左
- 如何将对应的位设置到位图中呢在？set()
问题：
-
最开始开多大的空间作为布隆过滤器的长度？
4.2*N(插入的个数) =M (过滤器的长度)。vector<>大小确定。
控制大小不变，相似字符串之间，不相似字符串之间计算误判率，字符串之间换前缀后缀什么的
经过测评，最影响误判率的还是个数和空间之间的比率m/n，存多少个值开多少个bit位。
字符串相似还是没多少影响的。就像影响哈希的还是负载因子的设置。布隆过滤器不能保证没有误判。
如何根据实际请款设计布隆过滤器?
设计(类黑名单情况+允许失误+没有删除)
n:样本数量 P失误率
- 如何让布隆过滤器支持删除？
不能随便删除数据，可能会有冲突，随便删除会影响其他值。如何非要支持删除呢？
每个标记位使用多个比特位也就是多个位图进行控制，存储引用计数（有几个值映射了当前的位置）。
支持删除的话整体消耗的空间变多了，优势就下降了。
使用场景：
数据量大，节省空间，允许误判，这样的场景就可以使用布隆过滤器。
比如：
-
判断昵称是否已经有人用过，将昵称放到布隆过滤器中，在是有误判，不在就是准确的也就不用再去数据库中确定了。误判也没事，让用户再取一个名就行，所以是允许误判。如果还是存在的话，就去数据库查一遍，降低误判。
-
人是否在黑名单当中，不在就一定不是，如果显示在也有可能是误判导致的，再去数据库中查找再返回。
-
减少磁盘IO和网络请求，提高效率的话再前端设置一个布隆过滤器，提高的点就是不在的话就是准确的。
给定100亿个字符串query，我们只有1G内存，如何准确的找到两个文件的交集？
近似算法：可以放到布隆过滤器中，另一个在去找。交集里面存在误判导致不是交集的query，是交集的一定会进去。
精确算法：假如每个query是10byte，100亿个query就是100G空间。还不允许误判，就需要新的方法->哈希切分
6.哈希切分（区别于位图）
哈希切分 这100G，一个文件分成100个小文件，但是如果是一个一个进行二维遍历，并没有达到提高效率的目的，所以将100G切分为指定大小的小份不能提高效率。
所以要进行哈希切分：
其中一个文件读取query,i=BKDRHash(query)%200,这个query就进入Ai号小文件，
另一个文件读取query,i=BKDRHash(query)%200,这个query就进入Bi号小文件，
类似于哈希桶，Ai和Bi小文件找交集就行了。冲突的和相同的就进入了一个小文件。A和B中，相同的query一定进入编号相同的小文件。切200分平均一份就是500MB，也可以分成别的，这样就可以500MB一次进入内存中进行对比。
可能存在某个文件当中的字符串太多了，可增长文件数目，增加负载因子类似，减少一个编号文件太大，如果Ai和Bi还是很大，超过内存，那么就再用另一个哈希算法进行一次哈希切分，相同或者类似的字符串还是会进一个编号中。
给一个超过100G大小的logfile日志文件，log中存着IP地址，设计算法找到出现次数最多的地址？
哈希切分，依次读取ip，用哈希函数把IP转化为整数，%份数，比如200，那么一个文件就是500MB
i是多少，IP就进入对应的编号小文件当中，相同IP的进入有一个文件中，将这500MB依次加载到内存中，那么用map统计一个小文件中的IP的次数就是它准确的次数，返回一个pair,出现最多的10个ip，用优先级队列，priority_queue用小堆。小堆是一个比一下小进入堆中。
7.一致性哈希
信息都存在几个服务器中，那如何确定是哪一个服务器呢？Hash(id)%num得到服务器编号。如果我新添加一台服务器，那么是不就得重新建立映射的问题，就需要一致性哈希。
- key如何选择才能保证服务器的负载均衡?
选择重复率高的属性比如姓名.如果重复率低比如选择性别,那么只有男女那两个机器超级负载.
- 引入
采用key值经过处理之后硬取模的方式选择哪台服务器.导致新增一台机器,导致其他值还得重新取模.一致性哈希就取消这种取模机制.
N台机器作为节点组成一个环状结构,N台机器之间的哈希值差距都很大,
一个m值经过哈希函数的处理得到一个值out,这个out值越靠近哪个服务器,就将这个业务部署到哪台服务器上.
在逻辑端将N台机器的值进行排序,用out值越靠近哪个值就使用哪台机器.
环上新增一个节点,只需要将部分数据从原来的机器分配到新的机器上.
- 存在问题
1. 开始的机器数量如何实现均分?比如:咋可能一开始就是各自三分之一.
2. 新增机器之后可能不同机器之间是无法实现负载均衡的.有的机器还是负责三分之一,有的就只需要1/4.
- 使用虚拟节点,按比例分配,就能解决上述两个问题
m1 m2 m3三台机器假如每一台机器各自分了1000个节点,在这个环上,排列按照随机时的分配或者m1m2m3m1m2m3的方式,那么一段区间中三台机器的负载一定是均衡的.那么我新增加一台机器,新增加1000个m4节点,将其余的节点差不多的分一些业务给到m4的节点即可实现分配之后的负载均衡.
- 管理负载
通过服务器的实际负载情况可以通过比例管理负载,比如A服务器状态很好,我就给他分配2000个节点.
8. 习题
-
哈希是一种用于查找的数据结构，时间复杂度平均是O(1)。如果存在哈希冲突，时间复杂度就不是O(1)。是以牺牲空间换取时间的方法，因为所需空间>元素个数避免哈希冲突。
-
散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。由于散列函数不是一对一的关系，所以选择好的（散列函数和冲突处理）方法是散列文件的关键。
-
常见的哈希函数有：直接定址法、除留余数法、平方取中法、随机数法、数字分析法、叠加法等。哈希函数无法避免哈希冲突。
常见哈希冲突处理：闭散列（线性探测、二次探测）、开散列(链地址法)、多次散列
-
采用开放定址法处理散列表的冲突时，其平均查找长度高于链接法处理冲突，容易引起一连篇的冲突。
所谓的平均查找长度就是在查找运算中需要对比的关键字的次数。冲突越多对平均查找长度的影响越大。