目录
1.位图
2.布隆过滤器
3.海量数据处理面试题
3.1哈希切割
3.2位图的应用
3.3布隆过滤器应用
1.位图
位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
1.1位图的模拟实现
因为需要对位图的每一个比特位进行管理，所以可以想到使用char类型的数组，从而实现对每一个比特位的管理。
template <size_t N>
class mybitset
{
public://构造函数mybitset(){_bits.resize(N/8 +1);}//设置比特位void set(size_t x){size_t i=x/8;size_t j=x%8;_bits[i]|=(1<<j);}void reset(size_t x){size_t i=x/8;size_t j=x%8;_bits[i]&=~(1<<j);}//判断是否有xbool test(size_t){size_t i=x/8;size_t j=x%8;return _bits[i]&(1<<j);}
private:vector<char> _bits;
}
1.2 用位图来解决问题
首先：40亿个数据，用hash、遍历或者排序的方法，内存开销会16GB，但是使用位图，开销只有0.5GB。
位图结构：无符号整数的范围是：0~2^32-1，所有无符号整数的范围（种类）为42亿9千万（2^32）左右，我们使用位图，位图的每一位对应与一个无符号整数的种类，一共需要2^32bit=0.5GB。
对40亿个数据遍历一边，将位图中的映射位置为1.然后x找到映射位，为0或者1，来判断数据是否存在。
bool find(vector<int> arr, size_t x) {bitset<(size_t)-1> set1;for (int& val : arr) {set1.set(val);}return set1.test(x);
}2.布隆过滤器
布隆过滤器是由布隆在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你“某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
单个哈希函数与位图结合
容易出现的问题：
- 比特位只能标记该点对应的数据是否存在
- 当发生哈希冲突时，存在误判的情况。
- 所以可以判断数据一定不存在或者可能存在。
多个哈希函数与位图结合
位图只能标记这个位置对应hashi存不存在；
最佳的哈希函数个数
过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。
k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率
可以计算得到结果：m=(k*n)/0.69
2.1布隆过滤器的实现
Hash函数的个数由自己确定最合适的个数，这里取三个哈希函数。
布隆过滤器的查找思想：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
template <size_t M,class T=string,class Hashfunc1=BKDRHash,class Hashfunc2=APHash,class Hashfun3=DJBHash>
class BloomFilter
{
public://构造函数BloomFilter(){} //默认构造函数足够使用//设置当前位置void set(const T&key){size_t hash1=Hashfun1()(key)%M;size_t hash2=Hashfun2()(key)%M;size_t hash3=Hashfun3()(key)%M;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}//检测是否存在bool Test(const T&key){size_t hash1=Hashfun1()(key)%M;if(_bs.test(hash1)==false){return false;}size_t hash2=Hashfun2()(key)%M;if(_bs.test(hash2)==false){return false;}size_t hash2=Hashfun3()(key)%M;if(_bs.test(hash3)==false){return false;}//存在误判return true;}
private:bitset<M> _bs;
}
不同的哈希函数
struct BKDRHash
{size_t operator()(const string& s){size_t value = 0;for (auto ch : s){value *= 31;value += ch;}return value;}
};struct APHash
{size_t operator()(const string& s){size_t hash = 0;for (long 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;}
};struct DJBHash
{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}
};
struct JSHash
{size_t operator()(const string& s){size_t hash = 1315423911;for (auto ch : s){hash ^= ((hash << 5) + ch + (hash >> 2));}return hash;}
};
布隆过滤器的删除
如果使用位图结构，那么布隆过滤器是无法支持删除。因为如果只是单单将需要删除的元素对应的比特位修改为0； 那么可能会导致其他的元素，因为对应比特位被错误的修改为0而被“删除”。
假如我们把上面的IP1删除，因为IP2对应的比特位和IP4对应的比特位有相同的，所以当IP1被删除后，IP2也会被认为“删除”。
一种支持删除的布隆过滤器的设计方式是：
将每个比特位扩展为一个小的计数器，当插入元素时，该哈希地址对应的计数器加1，删除的时候减1。当然该方法也无法解决哈希冲突导致的误判。
2.4布隆过滤器的优缺点
优点
- 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无
- 关
- 2. 哈希函数相互之间没有关系，方便硬件并行运算
- 3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
- 4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
- 5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
- 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺点
- 1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
- 建立一个白名单，存储可能会误判的数据)
- 2. 不能获取元素本身
- 3. 一般情况下不能从布隆过滤器中删除元素
- 4. 如果采用计数方式删除，可能会存在计数回绕问题
3.海量数据处理面试题
3.1哈希切割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
3.2位图的应用
给定100亿个整数，设计算法找到只出现一次的整数？
思路：因为只使用一个位图只能记录是否出现了该整数，不能判断出现了几次。所以我们考虑使用两个位图。
template<size_t N>
class doubitset
{//默认的构造函数够使用//设置参数函数void set(size_t x){int in1 = _bs1.test(x);int in2 = _bs2.test(x);if (in1 == 0 && in2 == 0){_bs2.set(x);}else if (in1 == 0 && in2 == 1){_bs1.set(x);_bs2.reset(x);}}bool is_once(size_t x){return _bs1.test(x) == 0 && _bs2.test(x) == 1;}
private:mybitset _bs1;mybitset _bs2;
};
3.3布隆过滤器应用
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
近似算法：布隆过滤器
精确算法：哈希切割