1. 位图

1.1 位图概念

1. 面试题
   给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在
   这40亿个数中。【腾讯】
   解题思路1：暴⼒遍历，时间复杂度O(N)，太慢
   解题思路2：排序+⼆分查找。时间复杂度消耗 O(NlogN) + O(logN)
   深⼊分析：解题思路2是否可⾏，我们先算算40亿个数据⼤概需要多少内存。
   **1G = 1024MB = 10241024KB = 102410241024Byte 约等于10亿多Byte**
   那么40亿个整数约等于16G，说明40亿个数是⽆法直接放到内存中的，只能放到硬盘⽂件中。⽽⼆分查找只能对内存数组中的有序数据进⾏查找。

解题思路3.位图解决
**数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。**比如：

2. 位图概念
   所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
   
   实现中需要注意的是，C/C++没有对应位的类型，只能看int/char这样整形类型，我们再通过位运算去控制对应的⽐特位。⽐如我们数据存到vector中，相当于每个int值映射对应的32个值，⽐如第⼀个整形映射0-31对应的位，第⼆个整形映射32-63对应的位，后⾯的以此类推，
   那么来了⼀个整形值x，i = x / 32；j = x % 32；计算出x映射的值在vector的第i个整形数据的第j位。

1.2 位图的模拟实现

模拟实现的位图，不管大小端的存储，由于1左移j位，则模拟实现就定义与左高位，右边低位

位图的三个核心方法

1. set ：x映射的位标记成1
   进行或运算，只改变那一位的数据为1

// 核心的三个接口
// x映射的位标记成1
// x是你的数据
void set(size_t x)
{size_t i = x / 32;// 寻找数据在vector的第几个索引位置size_t j = x % 32;// 寻找数据在i索引下的第几位_bs[i] |= (1 << j);// 做或运算，任何数与1做或运算得1
}

2. reset ：x映射的位标记成0
   先按位取反，得到那一位是0，其他位都是1，之后进行与运算

// x映射的位标记成0
void reset(size_t x)
{size_t i = x / 32;// 寻找数据在vector的第几个索引位置size_t j = x % 32;// 寻找数据在i索引下的第几位_bs[i] &= (~(1 << j));// 按位取反，得到x映射的位就是0，其他位都是1
}

3. test
   a. x映射的位是1返回真
   b. x映射的位是0返回假
   直接进行与运算判断

// 检测
// x映射的位是1返回真
// x映射的位是0返回假
bool test(size_t x)
{size_t i = x / 32;// 寻找数据在vector的第几个索引位置size_t j = x % 32;// 寻找数据在i索引下的第几位// 做与运算，与1相与结果得本身bool ret = _bs[i] & (1 << j);return ret;
}

整体模拟实现代码

// 位图
// 只适合于整型的数据
// 由于数据的数量很大，一般的数据结构无法存放的下这么多的数据 40亿个数据
// 我们可以用二进制位来存储，每一个位进行一个标记，看每一个数字是否出现，0   1 表示
// 这样40亿个数据也就只用开辟500M的空间
// 由于最小类型是char，不能单独开辟bit位的空间// 用非非类型模板参数实现
template<size_t N>
class bit_set
{
public:// 构造函数// 事先开辟好空间bit_set(){// 如果数据多余32的倍数（不整除的情况），则多出来的数据则就无法存// 则要加1多开辟一个字节空间_bs.resize(N / 32 + 1);}// 不管大小端的存储，由于1左移j位，则就定义与左高位，右边低位// 核心的三个接口// x映射的位标记成1// x是你的数据void set(size_t x){size_t i = x / 32;// 寻找数据在vector的第几个索引位置size_t j = x % 32;// 寻找数据在i索引下的第几位_bs[i] |= (1 << j);// 做或运算，任何数与1做或运算得1}// x映射的位标记成0void reset(size_t x){size_t i = x / 32;// 寻找数据在vector的第几个索引位置size_t j = x % 32;// 寻找数据在i索引下的第几位_bs[i] &= (~(1 << j));// 按位取反，得到x映射的位就是0，其他位都是1}// 检测// x映射的位是1返回真// x映射的位是0返回假bool test(size_t x){size_t i = x / 32;// 寻找数据在vector的第几个索引位置size_t j = x % 32;// 寻找数据在i索引下的第几位// 做与运算，与1相与结果得本身bool ret = _bs[i] & (1 << j);return ret;}private:vector<size_t> _bs;// 用数组来存放,一个size_t有32位
};

1.3 位图的优缺点

优点：增删查改快，节省空间
缺点：只适⽤于整形

1.3 位图相关考察题目

1. 给定100亿个整数，设计算法找到只出现⼀次的整数？
   虽然是100亿个数，但是还是按范围开空间，所以还是开2^32个位，跟前⾯的题⽬是⼀样的
2. 给两个⽂件，分别有100亿个整数，我们只有1G内存，如何找到两个⽂件交集？
   把数据读出来，分别放到两个位图，依次遍历，同时在两个位图的值就是交集
3. ⼀个⽂件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数
   之前我们是标记在不在，只需要⼀个位即可，这⾥要统计出现次数不超过2次的，可以每个值⽤两个位标记即可，00代表出现0次，01代表出现1次，10代表出现2次，11代表出现2次以上。最后统计出所有01和10标记的值即可。
   

// 实现面试题目
template<size_t N>
class twobitset
{
public:// x出现一次// 则当前xzai在位图上映射的位置的次数也要+1void set(size_t x){// 当前两个位图中的x相应位置是什么bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2)// 00->01{// bit2的相应位置置为1_bs2.set(x);}else if (!bit1 && bit2)// 01->10{// bit1相应位置置为1// bit2相应位置置为0_bs1.set(x);_bs2.reset(x);}else if (bit1 && !bit2)// 10->11{_bs1.set(x);_bs2.set(x);}}// 返回0 出现0次数// 返回1 出现1次数// 返回2 出现2次数// 返回3 出现2次及以上// 记录x出现了多少次int getCount(size_t x){// 当前两个位图中的x相应位置是什么bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);// 判断次数if (!bit1 && !bit2)// 00{return 0;}else if (!bit1 && bit2)// 01{return 1;}else if (bit1 && !bit2)// 10{return 2;}else// 11{return 3;}}private:// 用两个位图来表示bit_set<N> _bs1;bit_set<N> _bs2;
};

2. 布隆过滤器

2.1 布隆过滤器的概念

有⼀些场景下⾯，有⼤量数据需要判断是否存在，⽽这些数据不是整形，那么位图就不能使⽤了，使
⽤红⿊树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。
布隆过滤器的思路就是把key先映射转成哈希整型值，再映射⼀个位，如果只映射⼀个位的话，冲突率
会⽐较多，所以可以通过多个哈希函数映射多个位，降低冲突率。

布隆过滤器这⾥跟哈希表不⼀样，它⽆法解决哈希冲突的，因为他压根就不存储这个值，只标记映射的位。它的思路是尽可能降低哈希冲突。判断⼀个值key在是不准确的，判断⼀个值key不在是准确的。

2.2 布隆过滤器器误判率推导

由于这里的推导比较困难，我们在这里只介绍结论
假设
m：布隆过滤器的bit⻓度。
n：插⼊过滤器的元素个数。
k：哈希函数的个数。

哈希函数取定的情况下，n增加时，误判率增加，m增加，误判率减少，即布隆过滤器的长度增加，误判率就会减少，m/n越大，误判率越低

2.3 布隆过滤器代码实现

首先，采用三个仿函数将数据转换为可以取余的类型

// 三个仿函数保证数据类型转换为可以取余的类型（int）
// Hash1
struct HashFuncBKDR
{// 采用的字符串的Hash算法累乘因子为31。size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash *= 31;hash += ch;}return hash;}
};// Hash2
struct HashFuncAP
{// 由Arash Partow发明的一种hash算法。  size_t operator()(const string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++){if ((i & 1) == 0) // 偶数位字符{hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));}else              // 奇数位字符{hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));}}return hash;}
};// Hash3
struct HashFuncDJB
{// 由Daniel J. Bernstein教授发明的一种hash算法。 size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};

set：3个仿函数的处理之后的数据所映射的位置置为1

// 将对应的位置置为1
void Set(const K& key)
{// 每个仿函数所映射到数组中的索引位置// 数据转换为可以取余的数据类型，之后进行除留取余法，找到对应的位置size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash1()(key) % M;size_t hash3 = Hash1()(key) % M;cout << hash1 <<" "<< hash2 <<" "<< hash3 << endl;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}

Test:// 检查
三个仿函数所处理之后映射的位置，只要有一个位置没有匹配上就是错误

// 检查
// 三个仿函数所处理之后映射的位置，只要有一个位置没有匹配上就是错误
bool Test(const K& key)
{size_t hash1 = Hash1()(key) % M;if (!_bs.test(hash1)){return false;}size_t hash2 = Hash2()(key) % M;if (!_bs.test(hash2)){return false;}size_t hash3 = Hash3()(key) % M;if (!_bs.test(hash3)){return false;}return true;// 可能会有误判
}

公式计算误差率

// 获取公式计算出的误判率
double getFalseProbability()
{double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);return p;
}

总体的代码：

// 布隆过滤器
// 可适合于许多数据类型，string类型等，不同的字符传映射相同的位置
// 可能会存在误判：不在是准确的，在是不准确的
//															仿函数
//       元素个数  哈希函数个数  数据类型         3哈希函数:保证key（数据）可以转为整型
template<size_t N , size_t X = 3 , class K = string , class Hash1= HashFuncBKDR , class Hash2= HashFuncAP,class Hash3= HashFuncDJB >
class BloomFilter
{
public:// 将对应的位置置为1void Set(const K& key){// 每个仿函数所映射到数组中的索引位置// 数据转换为可以取余的数据类型，之后进行除留取余法，找到对应的位置size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash1()(key) % M;size_t hash3 = Hash1()(key) % M;cout << hash1 <<" "<< hash2 <<" "<< hash3 << endl;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}// 检查// 三个仿函数所处理之后映射的位置，只要有一个位置没有匹配上就是错误bool Test(const K& key){size_t hash1 = Hash1()(key) % M;if (!_bs.test(hash1)){return false;}size_t hash2 = Hash2()(key) % M;if (!_bs.test(hash2)){return false;}size_t hash3 = Hash3()(key) % M;if (!_bs.test(hash3)){return false;}return true;// 可能会有误判}// 获取公式计算出的误判率double getFalseProbability(){double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);return p;}private:// 定义成静态变量，可以直接使用M当作参数static const size_t M = N * X;// 位图的位数// 插入N个数据，开辟约等于N*X位，就相等于Mbit_set<N*X> _bs;// 位图
};

2.4 布隆过滤器的删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
默认情况下，布隆过滤器不支持删除，删除一个值可能会影响另一个值

2.5 布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无
   关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

2.6 布隆过滤器缺陷

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
   建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题

2.7 布隆过滤器的应用

1. 爬⾍系统中URL去重：
   在爬⾍系统中，为了避免重复爬取相同的URL，可以使⽤布隆过滤器来进⾏URL去重。爬取到的URL可以通过布隆过滤器进⾏判断，已经存在的URL则可以直接忽略，避免重复的⽹络请求和数据处理。
2. 垃圾邮件过滤：
   在垃圾邮件过滤系统中，布隆过滤器可以⽤来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，从⽽提⾼过滤的效率。
3. 预防缓存穿透
   在分布式缓存系统中，布隆过滤器可以⽤来解决缓存穿透的问题。缓存穿透是指恶意⽤⼾请求⼀个不存在的数据，导致请求直接访问数据库，造成数据库压⼒过⼤。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的⽆效查询。
   

4. 对数据库查询提效
   在数据库中，布隆过滤器可以⽤来加速查询操作。例如：⼀个app要快速判断⼀个电话号码是否注册过，可以使⽤布隆过滤器来判断⼀个⽤⼾电话号码是否存在于表中，如果不存在，可以直接返回不存在，避免对数据库进⾏⽆⽤的查询操作。如果在，再去数据库查询进⾏⼆次确认。

3. 海量数据处理问题

1. 10亿个整数⾥⾯求最⼤的前100个。
   先建立一个100个数据的大堆，每次进数据先判断，如果比堆顶数据大则就进堆，向下调整。

2. 给两个⽂件，分别有100亿个query，我们只有1G内存，如何找到两个⽂件交集？
   query是查询
   分析：假设平均每个query字符串50byte，100亿个query就是5000亿byte，约等于500G(1G约等于10亿多Byte)
   解决⽅案1：这个⾸先可以⽤布隆过滤器解决，⼀个⽂件中的query放进布隆过滤器，另⼀个⽂件依次查找，在的就是交集，问题就是找到交集不够准确，因为在的值可能是误判的，但是交集⼀定被找到了。可能不是交集的被找到，而找到的一定是交集
   解决⽅案2：
   1.哈希切分，⾸先内存的访问速度远⼤于硬盘，⼤⽂件放到内存搞不定，那么我们可以考虑切分为⼩⽂件，再放进内存处理。
   2.但是不要平均切分，因为平均切分以后，每个⼩⽂件都需要依次暴⼒处理，效率还是太低了。
   3.可以利⽤哈希切分，依次读取⽂件中query，i = HashFunc(query)%N，N为准备切分多少分⼩⽂件，N取决于切成多少份，内存能放下，query放进第i号⼩⽂件，这样A和B中相同的query算出的hash值i是⼀样的，相同的query就进⼊的编号相同的⼩⽂件就可以编号相同的⽂件直接找交集，不⽤交叉找，效率就提升了。
   4.本质是相同的query在哈希切分过程中，⼀定进⼊的同⼀个⼩⽂件Ai和Bi，不可能出现A中的的query进⼊Ai，但是B中的相同query进⼊了和Bj的情况，所以对Ai和Bi进⾏求交集即可，不需要Ai和Bj求交集。（本段表述中i和j是不同的整数），相同的查询字符串一定进入了相同的索引的小文件（A[i]和B[i]）
   5.哈希切分的问题就是每个⼩⽂件不是均匀切分的，可能会导致某个⼩⽂件很⼤内存放不下。我们细细分析⼀下某个⼩⽂件很⼤有两种情况：1.这个⼩⽂件中⼤部分是同⼀个query。2.这个⼩⽂件是有很多的不同query构成，本质是这些query冲突了。针对情况1，其实放到内存的set中是可以放下的，因为set是去重的。针对情况2，需要换个哈希函数继续⼆次哈希切分。所以本体我们遇到⼤于1G⼩⽂件，可以继续读到set中找交集，若set insert时抛出了异常(set插⼊数据抛异常只可能是申请内存失败了，不会有其他情况)，那么就说明内存放不下是情况2，换个哈希函数进⾏⼆次哈希切分后再对应找交集。超过一定情况可以进行二次切分。
   每个小文件的数据字符串放到set里面遍历set找交集。
   

3. 给⼀个超过100G⼤⼩的logfile,log中存着ip地址,设计算法找到出现次数最多的ip地址？查找出现次数前10的ip地址
   依次读取⽂件A中query，i=HashFunc(query)%500，query放进Ai号⼩⽂件，然后依次⽤map<string,int>对每个Ai⼩⽂件统计ip次数，同时求出现次数最多的ip或者topkip。本质是相同的ip在哈希切分过程中，⼀定进⼊的同⼀个⼩⽂件Ai，不可能出现同⼀个ip进⼊Ai和Aj的情况，所以对Ai进⾏统计次数就是准确的ip次数。