位图及布隆过滤器的模拟实现与面试题

位图

模拟实现

namespace yyq
{template<size_t N>class bitset{public:bitset(){_bits.resize(N / 8 + 1, 0);//_bits.resize((N >> 3) + 1, 0);}void set(size_t x)//将某位做标记{size_t i = x / 8; //第几个char对象size_t j = x % 8; //这个char对象的第几个比特位_bits[i] |= (1 << j); //标记}void reset(size_t x)//将某位去掉标记{size_t i = x / 8;size_t j = x % 8;_bits[i] &= (~(1 << j));}//测试值是否在bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bits[i] & (1 << j);//整型提升，bool是4字节，char是1字节，按符号位来补}private:std::vector<char> _bits;};
}

当然位图也有缺点，它只能处理整型数据。

应用

1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记
   位图，是利用一个比特位来标识数据在不在（哈希的直接地址法），优点是节省空间，效率高，缺点是只能处理整型数据且要求数据相对集中。将哈希与位图结合，即布隆过滤器。

位图是要把一个数据通过一个哈希函数映射到一个位置，判断在不在；布隆过滤器是要把一个数据通过多个哈希函数映射到多个位置，降低误判率，判断一定不在或可能在

布隆过滤器

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

模拟实现

哈希函数个数的选择

哈希函数个数越多，布隆过滤器要开的bit位就越多，内存占用更大，则布隆过滤器bit位置为1的速度越快，但是效率变低；个数过少的话，误报率会变高。

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

计算公式为$k=m/n\ast ln(2)$以及$m=-n\ast ln(p)/ln2/ln2$

第一个公式可以得出$m=k\ast n/ln2$，当我们用3个哈希函数时，布隆过滤器的长度为$3\ast n/ln2\approx 4.33n$。

在代码中，我们直接取5n，代码中为X == 5，可以更改。

struct BKDRHashFunc
{size_t operator()(const std::string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};struct APHashFunc
{size_t operator()(const std::string& key){size_t hash = 0;const char* str = key.c_str();for (int i = 0; *str; i++){if ((i & 1) == 0){hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));}else{hash ^= (~(hash << 11) ^ (*str++) ^ (hash >> 5));}}return hash;}
};struct DJBHashFunc
{size_t operator()(const std::string& key){size_t hash = 5381;const char* str = key.c_str();while (*str){hash += (hash << 5) + (*str++);}return hash;}
};// N是最多存储的数据个数
// 平均存储一个值，开辟X个位
template<size_t N, size_t X = 5, class K = std::string, class HashFunc1 = BKDRHashFunc, class HashFunc2 = APHashFunc, class HashFunc3 = DJBHashFunc>
class BloomFilter
{public:void set(const K& key){//3个哈希函数映射size_t hashi1 = HashFunc1()(key) % (X * N);size_t hashi2 = HashFunc2()(key) % (X * N);size_t hashi3 = HashFunc3()(key) % (X * N);_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);}bool test(const K& key){//3个哈希函数映射size_t hashi1 = HashFunc1()(key) % (X * N);if (!_bs.test(hashi1)){//如果通过一个映射值不在，那肯定不在return false;}size_t hashi2 = HashFunc2()(key) % (X * N);if (!_bs.test(hashi1)){//如果通过一个映射值不在，那肯定不在return false;}size_t hashi3 = HashFunc3()(key) % (X * N);if (!_bs.test(hashi1)){//如果通过一个映射值不在，那肯定不在return false;}//前三个映射值都存在，那么key可能在（有可能三个位置都冲突）return true;}private:std::bitset<N * X> _bs;
};

测试误判率

void test_bloomfilter2()
{srand(time(0));const size_t N = 100000;BloomFilter<N> bf;std::vector<std::string> v1;std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";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 url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";url += std::to_string(999999 + i);v2.push_back(url);}size_t n2 = 0;for (auto& str : v2){if (bf.test(str)){++n2;}}std::cout << "相似字符串误判率:" << (double)n2 / (double)N << std::endl;// 不相似字符串集std::vector<std::string> v3;for (size_t i = 0; i < N; ++i){std::string url = "zhihu.com";url += std::to_string(i + rand());v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.test(str)){++n3;}}std::cout << "不相似字符串误判率:" << (double)n3 / (double)N << std::endl;
}

不支持reset

因为某一位可能被多个值映射，有冲突。把这个位reset掉，可能导致真的在的key就变成不在了。

面试题

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

位图要完成的事情是在不在，只需要2种状态==>1个比特位，char的8个比特位可以表示8个数的状态。而这道题需要3种状态（0：00、1：01、n：10）==>2个比特位，char的8个比特位可以表示4个数的状态。

开两个位图，两个位图的相同的位置可以用0和1表示，当这个数出现第1次，第一个位图对应位置置1；第2次及以上次出现，第2个位图对应位置置1。

要筛选出现1次的整数，就用2个位图；要筛选出现2次的整数，就用3个位图，以此类推。

	template<size_t N>class twobitset{public:void set(size_t x)//将某位做标记{			if (!_bits1.test(x) && !_bits2.test(x))//00{_bits2.set(x);}else if (!_bits1.test(x) && _bits2.test(x))//01{_bits2.reset(x);_bits1.set(x); //10}else//10{//啥也不做}}private:std::bitset<N> _bits1;std::bitset<N> _bits2;};
}

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

两个文件的话，每个文件分别使用一个位图，此时位图对应的功能就包括去重+交集。两个位图位置都为1，就是两个文件的交集。

3、位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。

int的最大值为24亿多，找不超过两次的，要用到2个位图4种状态(00\01\10\11)，然后要过滤掉00和11这两个状态对应的数据

4、给一个超过100G大小的log文件, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

ip是这样的127.0.0.1一个字符串。位图只能解决K问题（在不在），不能解决KV问题（多少次）。这里要求出现次数最多的，只能采用map来解决问题，100G大小肯定放不进去内存，我们利用哈希切割，先将文件分为100个小文件（注意不是平均分割），将每个小文件当作一个哈希桶，用函数将ip转成整型，i = HashFunc(ip) % 100，i冲突的ip就会进入对应i号文件，那同一类ip就会进入同一个文件（相同的值一定会进入同一个文件，当然也会有哈希冲突的值），再对每个文件进行map统计出现次数。

如果：单个小文件超过1G，说明这个小文件里冲突的ip很多，a.大多是不同的ip/b.大多是相同的ip，该如何处理？

a.大多是不同的ip的情况，用map肯定无法完全统计，换个字符串哈希转换函数，递归再切分。

b.大多是相同的ip的情况，用map可以统计，大不了再用外排序。

如果map的insert失败，就表示没有内存了，相当于new节点失败，new失败会抛异常，就按a来处理。

5、给两个文件（A、B），分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。

query是查询指令，比如可能是一个网页请求或者是一个数据库sql语句。

精确算法：假设每个query指令是50字节，那100亿个query大小约为500GB。将这些数据分到1000个小文件（Axx、Bxx），每个文件约0.5GB。每个小文件是通过同一个哈希函数，对应编号的文件里的数据大多是差不多的，把数据去个重，然后A01和B01分别用哈希表求交集，…A99和B99分别求交集。若小文件超过1GB，就再换个哈希函数再切分。

近似算法：用布隆过滤器，先把一个文件过一遍布隆过滤器，另一个文件来判断一下有哪些在。

6、如何扩展BloomFilter使得它支持删除元素的操作

计数器，有几个值映射到这个位，这个位就是几，当要求reset时，这个位置的值–。但是要实现计数的功能，映射位置就不能再使用一个位标记，而是需要多个位存储计数值，空间消耗成倍增加。故此方案在实际中不会被使用，还不如用哈希表。