布隆过滤器

2.1 布隆过滤器的概念

布隆过滤器的底层数据结构与位图相同，且具备一系列哈希函数，可以做到快速查询一个元素是否在集合中，同时节省内存空间。

它的缺点是 存在误判（原本不存在，判断为存在） 和 不便删除 。

可以把布隆过滤器想象成一个集合，Set() 插入元素，Test() 元素是否存在。

• Set(“Tencent”) ——> 经过一系列哈希函数的映射，对布隆过滤器底层数据结构上 pos1、pos2、… 等位置进行标记；
• Test(“Tencent”) ——> 判断 Tencent 经这一系列哈希函数映射的、对应底层数据结构的位置，是否都被标记，得出结论。
  • 存在误判：若插入一系列元素，经一系列哈希函数映射，分别标记 Tencent 所对应的 pos1、pos2、… ，那么即便没有插入 “Tencent” ，Test(Tencent）的结果仍然为 True ；可以通过 扩大底层空间 和 增加哈希函数个数 减小误判率。
  • 不便删除：删除 “Tencent”是否意味着要将其映射的位置重新标记成 0 ？假设 “Tencent” 与 “Baidu” 映射到同一 pos2 ，删除 “Tencent” ，将无法再查询到 “Baidu”。

2.2 性能优秀的字符串哈希算法

详细：

struct HashFuncBKDR
{
	// BKDR
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

struct HashFuncAP
{
	// AP
	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;
	}
};

struct HashFuncDJB
{
	// DJB
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash = hash * 33 ^ ch;
		}

		return hash;
	}
};

2.3 BloomFilter 实现

	template<size_t N, class K = string
		class Hash1 = HashFuncBKDR,
        class Hash2 = HashFuncAP,
		class Hash3 = HashFuncDJB>
    class BloomFilter
    {
    private:
        static const size_t M = 5 * N; // 静态成员常量，用于给底层开更大的空间
        // 2 种创建底层的写法
        bitset<M> _bs; // 1
        bitset<M>* _bs = new bitset<M>; // 2
    };

经过实测，std::bitset 是在栈区开空间，当数据量很大时会导致栈溢出，因此选择第二种写法 —— 在堆区开空间：

		bitset<M>* _bs = new bitset<M>;

不需要为 BloomFilter 写构造函数，内置类型 bitset 会调用自己的构造函数。

	class BloomFilter
    {
    public:
        void Set(const K& key)
        {
            size_t Hashi1 = Hash1()(key) % M; // 仿函数；% M 防止越界访问
            size_t Hashi2 = Hash2()(key) % M;
            size_t Hashi3 = Hash3()(key) % M;
            
            _bs->set(Hashi1);
            _bs->set(Hashi2);
            _bs->set(Hashi3);
        }
        
        bool Test(const K& key)
        {
            size_t Hashi1 = Hash1()(key) % M;
            if (_bs->test(Hashi1) == false)
                return false;
            
            size_t Hashi2 = Hash2()(key) % M;
            if (_bs->test(Hashi2) == false)
                return false;
            
            size_t Hashi3 = Hash3()(key) % M;
            if (_bs->test(Hashi3) == false)
                return false;
            
            return true;
		}
    };

2.4 切分思想

1. 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
2. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？

处理这类大量数据的问题，通用的解法就是：把大文件按照某种规律分为若干个小文件存进硬盘中，如： Hash(IP) % 1000 、 Hash(query) % 1000 —— 通过哈希函数把具有相同特征的元素分成 1000 份，再在内存中对这些小文件逐个处理。

某个小文件太大，分为两种情况：

1. 存在大量重复的元素。 ——> 存入 set 或 bitset 等容器中，会自动去重，无须担心。
2. 存在大量不重复的元素。——> 换一个哈希函数，把该小文件再切分，再处理，以此类推。

2.5 拓展支持删除

以多个比特位组为一个标准单位。