哈希应用之布隆过滤器及其实现

布隆过滤器

我们在上一篇中主要说的是位图，是用于判断整形是否存在的一种应用，但是他不好的地方就是只能判断整形了，如果是字符串的话就难再应用了

在之前哈希表中，我们使用了一些哈希函数来将字符串转化成整形，再存入哈希表

这里我们是否可以使用同样的方法呢

其实我们讲，可以但是还不够，因为相似的字符串很容易就会产生哈希冲突，本质上来说还是因为字符串的数量太庞大，远远超出了整形能承受的范围，从而形成一种多对少的效果，产生了冲突

那么对于这样的冲突，也不能直接存字符串，因为使用位图本身就是为了节省空间的

这时候就有人想到了一个方法，既然一个关键字（哈希地址）容易产生冲突，那么我如果使用两种不同的哈希函数，每一个字符串对应两个哈希地址，只有当两个哈希地址都是1的时候，我们才认为该字符串是已经存在的

但是这种存在依旧是“不可靠”的，在数据量特别巨大的时候，可能是别的字符串，恰好占用了这两个地址，此时就会误判，但是判断不存在的时候就是可靠的了，因为只要有一个是0，就说明这个字符串并不存在

这也就是为什么我们称之为过滤器，简单说一种应用就是用户注册时不允许重复名称，当我们查询时，发现不存在，这时就不需要再额外消耗资源去数据库中进行对比了，直接就可以确认，而当布隆过滤器发现，他是有可能存在的时候，再到数据库中对比，如果真的存在，再说不允许重复名称即可，这样就能节省大量的服务器资源，还能提高查询效率

模拟实现

struct BKDRHash {
	size_t operator()(const string& key) {
		size_t hash = 0;
		for (auto e : key) {
			hash *= 32;
			hash += e;
		}
		return hash;
	}
};

struct APHash {
	size_t operator()(const string& key) {
		size_t hash = 0;
		for (auto e : key) {
			if ((e & 1) == 0) {
				hash ^= (hash << 7) ^ e ^ (hash >> 3);
			}
			else {
				hash ^= (~(hash << 11) ^ e ^ (hash >> 5));
			}
		}
		return hash;
	}
};

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

template<size_t N, class K= string
, class HashFunc1=BKDRHash
, class HashFunc2=APHash
, class HashFunc3=DJBHash>
class BloomFilter {
public:
	void Set(const K& key) {
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

	bool Test(const K& key) {
		size_t hash1 = HashFunc1()(key) % N;
		if (_bs.test(hash1) == false)
			return false;

		size_t hash2 = HashFunc2()(key) % N;
		if (_bs.test(hash2) == false)
			return false; 
		
		size_t hash3 = HashFunc3()(key) % N;
		if (_bs.test(hash3) == false)
			return false;

		// 可能误判的存在
		return true;
	}
private:
	bitset<N> _bs;
};

布隆过滤器一般是不支持删除的，因为一个删除需要同时删除几个位置的值，有可能会影响其他位置的元素

当然我们也可以想别的办法支持，例如将每个比特位作为计数器，插入元素时就加一，删除元素时减一

但是这种操作会让存储量成倍增加，而且也无法确认元素是否真正在过滤器中