目录

简介

Bloom Filter的基本原理

实现

使用

HashFunc越多，性能越好吗？

如何尽量避免误判？

应用

布隆过滤器优点

---

简介

Bloom Filter是一种空间效率极高的概率数据结构，它用于测试一个元素是否属于集合。Bloom Filter的优点是插入和查询操作的时间复杂度都是O(1)，同时它不需要存储元素本身，可以大幅度节省空间。但它的缺点是存在一定的误判率（false positive rate），即可能会错误地判断一个元素属于集合，但绝不会错误地判断一个元素不属于集合。

下面我将用C++语言简单讲解Bloom Filter的实现原理。

Bloom Filter的基本原理

Bloom Filter使用一个很长的位数组（bit array）和几个哈希函数。初始时，位数组所有位都置为0。当要插入一个元素时，该元素会通过几个哈希函数计算出几个哈希值，这些哈希值对应位数组中的位置，然后将这些位置设为1。查询时，同样计算这些哈希值并检查对应位是否为1，如果所有对应位都是1，则可能元素在集合中；如果有任意一位是0，则元素一定不在集合中

实现

namespace bloom_filter
{
	struct BKDRHash
	{
		size_t operator()(const string& key)
		{
			// BKDR
			size_t hash = 0;
			for (auto e : key)
			{
				hash *= 31;
				hash += e;
			}

			return hash;
		}
	};

	struct APHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); i++)
			{
				char ch = key[i];
				if ((i & 1) == 0)
				{
					hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
				}
				else
				{
					hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
				}
			}
			return hash;
		}
	};

	struct DJBHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 5381;
			for (auto ch : key)
			{
				hash += (hash << 5) + ch;
			}
			return hash;
		}
	};

	template<size_t N, class K = string,
		    class Hash1 = BKDRHash, 
			class Hash2 = DJBHash,
			class Hash3 = APHash>
	class BloomFilter
	{
	public:
		void set(const K& key)
		{
			size_t hash1 = Hash1()(key) % N;		//需要%N，防止溢出（除留余数法）
			size_t hash2 = Hash2()(key) % N;
			size_t hash3 = Hash3()(key) % N;
			
			_bits.set(hash1);
			_bits.set(hash2);
			_bits.set(hash3);
		
		}

		// 一般不支持删除，删除一个值可能会影响其他值
		// 非要支持删除，也是可以的，用多个位标记一个值，存引用计数
		// 但是这样话，空间消耗的就变大了
		void Reset(const K& key);

		bool Test(const K& key) 
		{
			size_t hash1 = Hash1()(key) % N;		//需要%N，防止溢出（除留余数法）
			size_t hash2 = Hash2()(key) % N;
			size_t hash3 = Hash3()(key) % N;

			if (_bits.test(hash1) && _bits.test(hash2) && _bits.test(hash3))	//存在误判
				return true;

			return false;		//不存在误判
		}

	private:
		bitset<N> _bits;
	};

使用

布隆过滤器可以理解为哈希与bitset的结合体

对于其他类型的在不在，且数据量很大，那就要借助哈希 + bitset的结合体。

类型不同，只需要借助合理的HashFunc即可。

HashFunc越多，性能越好吗？

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，它用于测试一个元素是否属于集合。布隆过滤器之所以在处理大量哈希函数（Hash Functions）时性能好，主要有以下几个原因：

减少哈希碰撞的概率：布隆过滤器使用多个独立的哈希函数来将一个元素映射到位数组中的不同位置。当使用多个哈希函数时，即使某个哈希函数产生了碰撞，其他哈希函数也可能产生不同的位位置，从而减少总体上的错误率。这提高了判断元素是否可能存在于集合中的准确性。

更高的并行性：使用多个哈希函数可以让布隆过滤器在判断元素是否存在时并行地检查多个位，这在计算上可以更加高效。

灵活的错误率控制：布隆过滤器的错误率（即假阳性率）可以通过调整哈希函数的数量来控制。增加哈希函数的数量可以降低错误率，而减少哈希函数的数量则会提高错误率。这使得布隆过滤器可以根据具体的应用需求来调整其性能。

以下是具体的几个点：

空间效率：布隆过滤器不需要存储元素本身，只需要一个位数组和几个哈希函数。这使得它在空间上非常高效，特别是当集合中元素数量很大时。

时间效率：查询操作只涉及几个简单的哈希计算和位操作，这些操作都非常快速。

可扩展性：布隆过滤器可以很容易地扩展以处理更多的元素和更大的数据集，只需增加位数组的大小和/或哈希函数的数量。

需要注意的是，虽然布隆过滤器在处理大量哈希函数时性能好，但是哈希函数的数量也不是越多越好。过多的哈希函数会增加计算的开销，而且超过一定数量后，减少错误率的收益会逐渐降低。因此，通常需要根据具体的应用场景和可接受的错误率来选择合适的哈希函数数量。

一般来说，三个就很好了！

如何尽量避免误判？

增加位数组的大小：更大的位数组可以减少误判的概率，因为每个元素有更多的空间进行映射。

增加哈希函数的数量：更多的哈希函数可以减少不同元素共享位的概率，但同时也增加了计算的开销。

选择好的哈希函数：使用高质量的哈希函数可以最小化哈希碰撞的概率。

应用

近似算法就是布隆过滤器，精确算法就是bitset        两个都需要借助位图

使用的哈希算法相同，相同的小文件是相同的query

哈希切割问题：

A和B相同的query一定是进入了相同的小文件

可以把小文件理解成一个哈希桶，冲突的值进入了相同的桶

让相同序号的桶进入内存中，借助set去重，找交集 

总结：

采用一致的哈希算法进行切割，分配到小文件中

序号相同的小文件内部的资源（出现冲突）进入setA和setB中进行找交集

（原因：相同的数据即交集，相同的数据通过相同的哈希算法一定进入相同序号的小桶（得到相同的hashi））

缺陷

但是有可能哈希切割之后某个文件太大，无法加载到内存中

1.大多数都是相同的query（继续切割效果不好）

2.有很多不同的query（思路：换一个哈希函数，继续切割）

解决思路：不管何种原因，都插入到set中，

第一种情况，后续会插入失败。

第二种情况，不断set之后，内存出现不足，会抛异常，此时更换新的哈希函数。

哈希切割的核心思想是，相同的数据总是会因为哈希碰撞进入相同的小桶

举例： 

对于去重，我们用set，对于计数，我们用map

问题2：