位图：

引入

位图实现：

位图的结构

插入数据(标记数据)

删除数据(重置数据)

查找数据

位图完整代码：

位图的优缺点：

布隆过滤器：

引入

布隆过滤器实现：

布隆过滤器的结构：

插入数据(标记数据)

查找数据

删除数据(重置数据)

面试题：如何实现布隆过滤器的删除？

构造函数(开辟容量)

哈希函数

布隆过滤器完整代码：

布隆过滤器的优缺点：

面试题：

位图：

给定100亿个整数，设计算法找到只出现一次的整数？

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

布隆过滤器：

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出近似算法

哈希切割：

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出精确算法

哈希切分：

给一个超过100G大小的log file(日志)，log中存着IP地址，设计算法找到出现次数最多的IP地址？如何找到top K的IP？

一致性哈希

位图：

本篇建立在已经熟悉哈希表直接定址法的基础上，有兴趣的读者可以看这篇文章

【数据结构】哈希——闭散列/开散列模拟实现(C++)-CSDN博客https://blog.csdn.net/suimingtao/article/details/149002209

引入

先来看一道腾讯的面试题，

题目：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

很明显，这道题可以用哈希来解决，而又因为题目上已经明确指出40亿个数据中不会重复，那么直接定址法是最好选择，但即使是这样，还有一个难题：要怎么存进这40亿整型数据？

一个Int占4个字节，40亿个int大约占16G，难道要把这16G数据都存在内存中吗？

显然，这才是腾讯这道面试题考察的地方

我们可以不用存数据本身，既然是直接定址法，只要在对应位置标记一下就可以。假如这道题目是100个不重复的无符号整数，且范围是0~99，那我们就可以开辟100个空间，要插入哪个值，就在对应的下标位置标位1，否则为0。既然只需要标记0或1，那1个二进制位足以。

这就是位图——即用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

腾讯这道题用位图法，只需要开辟约500M的空间就可以把这40多亿的数据全存进去

位图实现：

位图的结构

思路我们有了，但要怎么开辟空间呢？

C++中可以定义的最小的数据单位就是1字节，而1字节是8个位，不可能直接按照位来开辟数组

那我们可以用内置类型来代替开辟位：例如，如果要开辟100个位的空间，可以开上100/32+1(向上取整)个int，也可以开辟100/8+1个char，这里理论来说用char能更节省空间浪费，但就那么几十个位的破空间，其实都无所谓，这里编主就用int来实现

#pragma once
#include <vector>class bitset//位图
{
public:bitset(size_t n)//构造函数:_num(0){_bits.resize(n / 32 + 1,0);//标记默认为0}private:std::vector<int> _bits;//存数据的数组(准确来说是标记数据)size_t _num = 0;//有效数据的个数
};

插入数据(标记数据)

插入数据时，需要先找到该数据在数组的第几个int中，再确定到具体的该int的第几位，置1即可

可以直接将数据除以32，以得到该数据在第几个Int，将数据模除32，以得到该数据在int中的第几位

为什么要用|(或运算)？

如果用&(与运算)的话，int中别的位的标记也会被改动，因此要用|(或运算)

void set(size_t data)//标记数据(插入数据)
{size_t index = data / 32;//找到该数据在哪个整型中size_t pos = data % 32;//该数据在整型的第几位_bits[index] |= (1 << pos);//将该整型的第pos位标记成功_num++;//有效数据+1
}

删除数据(重置数据)

删除数据时，只需要把该数据所在位，置0即可，和插入时相似

将1 << pos再取反，就能得到除了一位是0，其他位全是1的数据，再将这个数据和原数据与运算，除了是0的那位之外，原来是1的数据就还是1，原来是0的数据还是0，不会改变

void reset(const size_t data)//重置数据(删除数据)
{size_t index = data / 32;//找到该数据在哪个整型中size_t pos = data % 32;//该数据在整型的第几位_bits[index] &= ~(1 << pos);//将该整型的第pos位标记删除_num--;//有效数据-1
}

查找数据

查找数据的思路也和前面大差不差

但此时就不能 &= 了，如果等于，会破坏本来原本的数据，只需要返回这个&之后的数据即可，只要是非0，就为找到，0就为找不到

bool test(const size_t data)//查找数据
{size_t index = data / 32;//找到该数据在哪个整型中size_t pos = data % 32;//该数据在整型的第几位return _bits[index] & (1 << pos);//若该位置有标记，就会返回非0
}

其实在STL中也有bitset

虽然接口很多，但主要的还是这三个

位图完整代码：

#pragma once
#include <vector>
class bitset//位图
{
public:bitset(size_t n)//构造函数:_num(0){_bits.resize(n / 32 + 1,0);//标记默认为0}void set(const size_t data)//标记数据(插入数据){size_t index = data / 32;//找到该数据在哪个整型中size_t pos = data % 32;//该数据在整型的第几位_bits[index] |= (1 << pos);//将该整型的第pos位标记成功_num++;//有效数据+1}void reset(const size_t data)//重置数据(删除数据){size_t index = data / 32;//找到该数据在哪个整型中size_t pos = data % 32;//该数据在整型的第几位_bits[index] &= ~(1 << pos);//将该整型的第pos位标记删除_num--;//有效数据-1}bool test(const size_t data)//查找数据{size_t index = data / 32;//找到该数据在哪个整型中size_t pos = data % 32;//该数据在整型的第几位return _bits[index] & (1 << pos);//若该位置有标记，就会返回非0}private:std::vector<int> _bits;//存数据的数组(准确来说是标记数据)size_t _num = 0;//有效数据的个数
};

位图的优缺点：

优点：节省空间，效率高

缺点：只能处理整型(由于位图用的是直接定址法，因此只能处理整型)

布隆过滤器：

引入

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找呢？

这时就不能用位图了，因为记录一般是字符串类型，但用哈希表来处理的话，当记录过多时，空间占用就会很大

还是可以用位图时采用的方法——即把某个位标记为1

但再怎么样的字符串哈希算法，都只是降低重复的概率，如果还是有一个字符串与其他字符串转换成整型后重复了怎么办？放在题目上说就是本来这个题目没给你推荐过，但还是被误判成推荐过了怎么办？

哈希冲突是不可避免的，但可以减少它出现的概率，即减少误判的概率，既然只有一个值很容易重复，那存多个值呢？即一个值映射多个位置

此时再发生哈希冲突，即误判的概率会大幅度降低，存的位置越多，哈希冲突概率越小

而这就是布隆过滤器——它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

布隆过滤器实现：

布隆过滤器的结构：

由于布隆过滤器也是用位图实现的，因此可以在里面直接实例化一个位图对象，再定义一个容量，用于后面进行除留余数法

模板参数中，首先是该布隆过滤器存储数据的类型(因为除了string还有可能是结构体，类等等自定义类型)，再根据一个值映射几个位置，就定义几个不同的哈希函数(这里编主选择一个值映射3个位置)

template<class K,//插入数据的类型class Hash1,//三个可以将K类型转为整型的不同哈希函数class Hash2,class Hash3>
class boolmfilter//布隆过滤器
{private:bitset _bs;//位图size_t _size;//开辟的位数
};

插入数据(标记数据)

由于使用布隆过滤器的类型都不是整数，因此要先将该值转换成整型，为了降低哈希冲突的概率，就需要用三种不同的转换方法，分别将一个值转成3个不同的值，再将这3个不同的值插入位图中即可

void set(const K& key)
{size_t index1 = Hash1()(key) % _size;//通过三个哈希函数算出不一样的三个值size_t index2 = Hash2()(key) % _size;//这里的Hash()是匿名对象size_t index3 = Hash3()(key) % _size;_bs.set(index1);//三个位存1个整数_bs.set(index2);_bs.set(index3);
}

上图中我们给每个转换后的值都模除了位图的容量，而位图的实现中我们没有%容量，这是因为位图用于表示某个固定范围内的整数是否出现（例如，统计 0~1000000 的整数是否出现），可以直接用整数本身作为索引。但布隆过滤器精确判断范围，因此需要模除容量。至于开辟多大容量，后面将构造函数时再说

查找数据

查找数据时，只有当三个哈希函数算出来的整数值都有标记，才可以确认为有。但前面也说过，这样只能降低出现哈希冲突的概率，还是有可能出现“一个值没有被插入过，但算出来的三个整数值都被标记”的情况，但只要是插入过的数据，是肯定能找到的

由此可以得出，布隆过滤器查找不在的数据，是准确的；布隆过滤器查找在的数据，是不准确的(哈希冲突时就是不准确的)

bool test(const K& key)//查找数据
{size_t index1 = Hash1()(key) % _size;//用三种不同方式将K类型转换为整型if (_bs.test(index1) == false)return false;size_t index2 = Hash2()(key) % _size;if (_bs.test(index2) == false)return false;size_t index3 = Hash3()(key) % _size;if (_bs.test(index3) == false)return false;return true;//如果都找到了就返回真
}

删除数据(重置数据)

布隆过滤器应该有删除数据的接口吗？

下图中，插入了两个数据，绿色和红色各代表一个数据，并且绿色和红色数据有一个重复的标记

如果此时要删除绿色，就需要把三个绿色标记都重置

那此时红色的一个标记也被重置，也就会将红色数据误删

因此，一般布隆过滤器不支持删除

面试题：如何实现布隆过滤器的删除？

如果非要让布隆过滤器可以删除元素，需要怎么处理？

可以将每个位都标记成计数器，当前位每次被标记，都让计数器+1

此时就算删除红色数据，也只会将三个哈希函数得出的整数位都-1,减完后“12”位中还有1，不影响蓝色数据

但这样做也有缺陷：一个位的计数器要给多少bit？如果bit给少了，多个值映射到一个位置就导致计数器溢出；但如果使用了更多bit映射一个位置，那么空间消耗就大了，不要忘了布隆过滤器的特点就是节省空间。并且这样就允许插入重复值了，去重操作将需要重新实现

构造函数(开辟容量)

构造函数需要完成布隆过滤器空间的开辟，那么到底开辟多少空间合适呢？

位图开辟空间只需要开辟整数的范围即可，但非整型可无法知道范围。

过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置置1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

(ps：k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率)

这里有一个参考公式：

$m = -\frac{n \ln p}{(\ln 2)^2}$ $k = \frac{m}{n} \ln 2$

(图和参考公式来自于这篇文章：详解布隆过滤器的原理，使用场景和注意事项 - 知乎)

由此可得出在哈希函数为3个的情况下，m 约等于 4.3(倍)，这里就按5倍来看

boolmfilter(size_t num)//构造函数:_bs(num*5)//在哈希函数为3个的情况下，开辟空间为4.3倍为最佳，这里就按5倍算(公式所得),_size(num*5)
{ }

哈希函数

模板中的三个哈希函数还没有实现，这里就默认为处理的类型是string，那么就是要定义3个字符串哈希函数

各种字符串Hash函数 - clq - 博客园https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html 这篇文章整理了很多字符串哈希函数，这里就选择前三个用(相对来说冲突率最低的三个)

struct BKDRHash
{size_t operator()(const std::string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++)hash = hash * 131 + s[i];return hash;}
};struct RSHash
{size_t operator()(const std::string& s){size_t hash = 0;size_t magic = 63689;	for (size_t i = 0; i < s.size(); i++){hash = hash * magic + s[i];magic *= 378551;}return hash;}
};struct SDBMHash
{size_t operator()(const std::string& s){size_t index = 0;for (size_t i = 0; i < s.size(); i++)index = index * 65599 + s[i];return index;}
};

STL库中没有布隆过滤器，只有位图！！

布隆过滤器完整代码：

#pragma once
#include "bitset.h"
#include <string>
struct BKDRHash
{size_t operator()(const std::string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++)hash = hash * 131 + s[i];return hash;}
};struct RSHash
{size_t operator()(const std::string& s){size_t hash = 0;size_t magic = 63689;	for (size_t i = 0; i < s.size(); i++){hash = hash * magic + s[i];magic *= 378551;}return hash;}
};struct SDBMHash
{size_t operator()(const std::string& s){size_t index = 0;for (size_t i = 0; i < s.size(); i++)index = index * 65599 + s[i];return index;}
};template<class K = std::string,//插入数据的类型class Hash1 = BKDRHash,//三个可以将K类型转为整型的不同哈希函数class Hash2 = SDBMHash,class Hash3 = RSHash>
class boolmfilter//布隆过滤器
{
public:boolmfilter(size_t num)//构造函数:_bs(num*5)//在哈希函数为3个的情况下，开辟空间为4.3倍为最佳，这里就按5倍算(公式所得),_size(num*5){ }void set(const K& key)//标记数据{size_t index1 = Hash1()(key) % _size;//通过三个哈希函数算出不一样的三个值size_t index2 = Hash2()(key) % _size;//这里的Hash()是匿名对象size_t index3 = Hash3()(key) % _size;_bs.set(index1);//三个位存1个整数_bs.set(index2);_bs.set(index3);}bool test(const K& key)//查找数据{size_t index1 = Hash1()(key) % _size;//用三种不同方式将K类型转换为整型if (_bs.test(index1) == false)return false;size_t index2 = Hash2()(key) % _size;if (_bs.test(index2) == false)return false;size_t index3 = Hash3()(key) % _size;if (_bs.test(index3) == false)return false;return true;//如果都找到了就返回真}private:bitset _bs;//位图size_t _size;//开辟的位数
};

布隆过滤器的优缺点：

优点：节省空间，效率高，可以标记存储任意类型

缺点：存在误判(判断一个数据不在布隆过滤器中是准确的，判断一个数据在布隆过滤器中是不准确的)，不支持删除

面试题：

位图：

给定100亿个整数，设计算法找到只出现一次的整数？

这道题可以用改进后的位图来解决。

上面我们实现的位图，一个数据只有一位，一位只能表示0或1，但如果一个数据用两位来表示呢？

00代表出现0次，01代表出现1次，10代表出现2次及以上，查找只出现一次的整数，只需要查找出两位为01的数据即可。可以实例化两个位图对象，第一个位图对象代表第一位，第二个位图对代表第二位

下面给出一部分代码，目的是为了让大家更理解思路

class solution
{
public:void set(size_t data){if (_bs1.test(data) == 0 && _bs2.test(data) == 0)//00，出现0次时{_bs2.set(data);//变成01，出现1次}else if (_bs1.test(data) == 0 && _bs2.test(data) == 1)//01，出现1次时{_bs1.set(data);_bs2.reset(data);//变成10，出现2次及以上}}
private:bitset _bs1;//第一位bitset _bs2;//第二位
};

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

方案一：可以定义两个位图，将文件1的整数映射到位图1中，将文件2的整数映射到位图2中，再将位图1和位图2 &(按位与)，结果就是交集

方案2：将其中一个文件映射到位图中，再读取另一个文件中的数据，判断在不在位图，在就是交集

1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

本题思路和第一题一样，只不过有了第四位，即11表示出现三次及以上，这里也只实现一个set

class solution
{
public:void set(size_t data){if (_bs1.test(data) == false && _bs2.test(data) == false)//00，即出现0次时{_bs2.set(data);//01，即出现一次}else if(_bs1.test(data) == false && _bs2.test(data) == true)//01，即出现一次时{_bs1.set(data);_bs2.reset(data);//10，即出现2次}else if (_bs1.test(data) == true && _bs2.test(data) == false){_bs2.set(data);//11，即出现3次及以上}}
private:bitset _bs1;//映射位图1的数据bitset _bs2;//映射位图2的数据
};

布隆过滤器：

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出近似算法

query可以理解为查询，也就是SQL语句，一条SQL查询语句大约在30~60B，100亿query就是300~600G。我们可以将文件1的数据都映射到布隆过滤器中，再读取文件2数据，判断在不在不用过滤器中，再就是交集。

但前面说过，布隆过滤器对于查找不在的数据是准确的，查找在的数据有可能会误判(某个值的多个哈希函数结果有可能在布隆过滤器中都有标记)。因此，这个方法的缺陷：交集中有些数据不准确，有些非交集的数据也可能因为映射的多个哈希函数值相同而误判为在交集

哈希切割：

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出精确算法

上面这道题是给出的近似算法，这里来实现一下不会存在误判的精确算法

既然一个文件太大，放不到内存中，那么我们可以把文件切分成多个小文件，将小文件一个一个加载到内存中，即平均切分

一个小文件具体的大小取决于内存，该题目说只有1G内存，就代表两个小文件的大小加起来不能超过1G，因此拆分成1000份，这样一份小文件就只有300~600M，两个小文件在1G左右

如果是平均切分，那就代表A0中是交集的数据可能在B0，也可能在B1、B2等等。因此A0放到内存中后，需要和B的1000个文件都比较一遍，以此类推，A1放到内存中也需要和B的1000个文件都比较一遍

看着好像是O(N^2)的时间复杂度，但其实比较的效率还是高的，因为Ax的小文件放在set中，在set中查找数据还是很快的。

哈希切分：

但有没有更快的办法？

上面用的方法叫做平均切分，缺点是每个小文件中都有可能存着交集的数据。

我们可以结合哈希表的思想，同样将每个文件分成1000个大文件，但数据不再平均切分，而是哈希切分——根据文件中的query的哈希值来判断应该放进哪个小文件中

哈希切分好后，因为相同的值哈希值必然相同，所以交集的值肯定都在相同的小文件中了

那么A0就只需要和B0比较，A1只需要和B1比较，以此类推。

将Ai小文件的数据放到一个set中，选取对应的Bi小文件中的query，如果在Ai中，就是交集

给一个超过100G大小的log file(日志)，log中存着IP地址，设计算法找到出现次数最多的IP地址？如何找到top K的IP？

首先，这道题要做的是统计次数，统计次数我们一般用map解决，但这里的问题是有100G数据，放不到内存中

这道题还是可以用哈希切割，也就是将这个100G大文件切分成1000份小文件(这里还是1000份，是因为哈希切分并不是平均切分，有可能出现某个小文件很小，某个小文件很大的情况，为了让很大的情况可以放下，因此要多开点)，读取IP计算出 i = hash(IP) % 1000，i是多少，IP就进入对应编号的Ai小文件，这样相同IP一定都在一个小文件中

再创建一个map<string,int> cnt;读取Ai中的数据统计次数，读取完后用一个pair<string,int> max;来存取该小文件中出现次数最多的IP，再cnt.clear()清除当前map中的数据后读取下一个小文件的数据

至于topK问题，可以建K个元素的小堆，把前几个数据放进去，后续只要有比堆顶次数多的，就替换堆顶数据并向下调整(topK问题细讲在这里：【基础算法】堆排序与TopK问题（C语言）_c#面试题 topk算法-CSDN博客)

一致性哈希

拿微信来举例，如果现在需要存每个用户的微信号和朋友圈信息，并且要方便快速查找

很明显，可以创建一个map<微信号,朋友圈>来存储

但真正需要考虑的是服务器存储数据的问题，因为微信有14亿用户，假设平均一个用户的信息是100M，那么大概需要 14亿 * 100M ≈ 130PB ，按一个服务器1TB来算，大约需要13w台服务器来存储数据(多机存储)

假如，此时用户valkyrie发了一条朋友圈，那这条朋友圈会存到那台机器？浏览和删朋友圈时又会怎么查找？

还是可以用到上面的哈希切割，将用户信息和存储的机器做一个映射关系

比如valkyrie的朋友圈信息，i = hash("valkyrie") % 13w ，结果的i就代表valkyrie的朋友圈信息要存到编号为多少的服务器上(实际中需要用一台额外机器存储机器编号和IP的映射关系，这样才能通过编号找到对应IP的服务器)

但这种方法有个缺陷：当数据存满时，需要加装服务器，那么之前的13w台机器上的数据映射关系就不对了，就需要重新计算位置迁移数据

这时候就要用到这个问题的主角——一致性哈希

我们可以将模除的值从13w改成2^32(选这个值是因为这是整型的最大值，实际中也可以是50亿，100亿等等)，即i = hash(用户名) % 2^32，之后再一段范围去映射一个服务器(例如0~10w映射第一个服务器，10w~20w映射第二个服务器)，这样可以让0~2^32范围内的值都映射到现有的13w服务器上