C++哈希应用之位图,哈希切分与布隆过滤器详解

#pragma once
#include <iostream>
#include <vector>
namespace jly
{
	template <size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 8 + 1, 0);
		}
	public:
		void set(size_t x)//将某个比特位标记为1
		{
			size_t i = x / 8;//算出x位于哪个字节
			size_t j = x % 8;//算出x位于该字节的哪一位
			_bits[i] |= (1 << j);
		}
		void reset(size_t x)//将某个比特位标记为0
		{
			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);
		}
	private:
		std::vector<char> _bits;
	};
	void test_bitset()
	{
		bitset<-1> bs;
	}
}

template <size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		if (_bs1.test(x))//01->10
		{
			_bs1.reset(x);
			_bs2.set(x);
		}
		else if (_bs1.test(x)==false&&_bs2.test(x)==false)//00->01
		{
			_bs1.set(x);
		}
	}
	void PrintOnce()
	{
		for (size_t i = 0; i < N; ++i)
		{
			if (_bs1.test(i) && !_bs2.test(i))
			{
				std::cout << i << std::endl;
			}
		}
	}
private:
	std::bitset<N> _bs1;
	std::bitset<N> _bs2;
};
void test()
{
	twobitset<100> tbs;
	int a[] = { 3,5,6,3,5,8,9,4,3,6,9,4 };
	for (auto& e : a)
	{
		tbs.set(e);
	}
	tbs.PrintOnce();//打印8
}

#pragma once
#include <iostream>
#include <bitset>
#include <string>
using namespace std;
struct BKDRHash
{
	size_t operator()(const std::string& key)
	{
		size_t hash = 0;
		for (auto& ch : key)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};
struct APHash
{
	size_t operator()(const std::string& key)
	{
		unsigned int hash = 0;
		int i = 0;
 
		for (auto ch : key)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
			}
 
			++i;
		}
 
		return hash;
	}
};
 
struct DJBHash
{
	size_t operator()(const std::string& key)
	{
		unsigned int hash = 5381;
 
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
 
		return hash;
	}
};
 
struct JSHash
{
	size_t operator()(const std::string& s)
	{
		size_t hash = 1315423911;
		for (auto ch : s)
		{
			hash ^= ((hash << 5) + ch + (hash >> 2));
		}
		return hash;
	}
};
 
//N为最大存储的个数,X为存一个值，需要开辟的比特位
template <size_t N,size_t X=5,class K=std::string,
class HashFunc1= BKDRHash,
class HashFunc2= APHash,
class HashFunc3= DJBHash>
class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % (X * N);
		size_t hash2 = HashFunc2()(key) % (X * N);
		size_t hash3 = HashFunc3()(key) % (X * N);
		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}
	bool test(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % (X * N);
		size_t hash2 = HashFunc2()(key) % (X * N);
		size_t hash3 = HashFunc3()(key) % (X * N);
		return _bs.test(hash1) && _bs.test(hash2) && _bs.test(hash3);
	}
private:
	std::bitset<X*N> _bs;
};
void test_bloomfilter1()
{
	// 10:46继续
	string str[] = { "a", "s", "d", "w", "a1","1a","白1a","c11a","1a1" };
	BloomFilter<10> bf;
	for (auto& str : str)
	{
		bf.set(str);
	}
 
	for (auto& s : str)
	{
		cout << bf.test(s) << endl;
	}
	cout << endl;
 
	srand((unsigned int)time(0));
	for (const auto& s : str)
	{
		cout << bf.test(s + to_string(rand())) << endl;
	}
}
void test_bloomfilter2()
{
	srand((unsigned int)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;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
 
	// 不相似字符串集
	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		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;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}