C++中ブロンフィルタ詳細

**
私はこれまでずっと电子笔记を书いていたので、自分が覚えたことをまとめました.だから、基本的には文字です.もともとブログの形式にしたいと思っていましたが、ブログにするのは时间がかかります.そして、ブログの质があまりよくありません.また、ブログを出すことで学んだことも少なくなります.だから、まずノートを出すつもりです.后で更にそれらをブログの形式に変えて、2日少なくとも1篇のブログを変えるように努力して、私が総括したのはまあまあだと思って先に私に関心を持つことができて、后でブログの形式に送ることができて、内容も更に完璧になります
**ブロンフィルタ:実際にはハッシュとビットマップの結合です.ビットマップは正確に検索される構造であるため、出現する可能性のあるすべての数字を列挙する必要がありますが、文字列に遭遇した場合はできません.文字列は無限で、根本的には表現できないので、ハッシュ衝突が発生するに違いありません.ハッシュ衝突が発生すると、ビットマップは使いにくいです.2つの文字列のハッシュ値が同じなので、1つの文字列が追加されると、その位置は1になりますが、別の文字列で検証するときは、ハッシュ値が同じであることに気づいてtrueを返しますが、実際には存在しません.これはエラーをもたらします.そのため、ブロンフィルタがこの問題を解決するために現れたが、実際にはブロンフィルタはこの問題を完全に解決することはできない(実際にはまだこの問題を完全に解決する方法はない).ハッシュ衝突を減らす方法を採用しているため、ハッシュ関数を使用することである.文字列がもともと無限であるため、ハッシュ関数を使用して計算した後、数値が大きくなる可能性がある.しかし、私たちの空間がどれだけ大きいかは、私たちがどれだけの文字列を保存するかによって決まります.各文字列の状態も1つのビットを占めていますが、ビットマップのように算出された数字で直接位置にすることはできません.数字の変化が大きい可能性があるので、ハッシュ関数を用いてハッシュ値を算出し、それから残留法を用いて位置の計算を行います.したがって、ブロンフィルタには1つのメンバーが追加され、私たちが占有するビット数になりますが、パラメータを送信するときは、1つだけ送信すればいいのです.それらはすべて範囲を受信しているので、ブロンにとって、これはビット数の配列になり、最終的に計算されたハッシュ値をビットマップに転送してフィルタリングを保証するために修正されます.ブロンが採用した複数のハッシュ関数を使用する方法は、複数のハッシュ関数で複数の位置を算出し、それぞれ1を置くことであり、ハッシュ競合を減らすことができる.1つはハッシュ競合が発生し、1を置かれたが、計算時には他の位置が0、すなわち1文字列の状態が複数の位置に格納されているため、これらの位置が1つ0であれば、他の位置がハッシュ競合していることを説明して1に置かれている限り、それは存在しないと判定することができ、もしすべて1であれば、それは存在する可能性が高いとしか言えず、必ず存在することを説明することはできません.このようにして払った代価は、私は空間を使って、もし3つのハッシュ関数があれば、それは3倍の空間を多く使う必要があります(このようにハッシュ衝突が発生する可能性が大きいほど、衝突の位置は関係ありません.私たちは状態を修正するだけで保存していないので)、ハッシュの時間複雑度はO(1)ですが、今はハッシュ関数がいくつあるか分からないので、時間複雑度はO(k)kの中でハッシュ関数の個数になります.ブロンフィルタが削除を提供しない理由は、ハッシュ競合が発生した可能性があるため、削除する要素の状態を0に設定すると、ハッシュ競合が発生した要素の位置も0に設定され、さっき言ったように0が1つあれば存在しないことを意味するので、削除操作の実現は提供されません.必ず使用する2つのパラメータを受信する構造があり、追加するときは、まずハッシュ値を計算してビットマップに渡し、テストするときは、だからのハッシュ関数で順次テストし、1つが0であればfalseブロンフィルタに戻って空間を開くときは、複数のハッシュ関数を使うためですが、直接ペアを開くと倍数の空間がもったいないので、そんなに大きなハッシュの衝突は多くありません.だから大男という人たちがいて、いろいろな数学の計算を経て、開空間の公式を与えて、m=k/ln 2*range、その中でkはあなたのハッシュ関数の個数で、rangeはあなたが開く空間の大きさで、mは計算したあなたが実際に開いた空間の大きさのブロンフィルタが削除操作を加える方法です:もともとブロンは削除操作をサポートしていません.これによりエラーが発生し、エラーの原因は、1と0だけをステータスとして使用しているため、ハッシュ競合が発生した後、そのうちの1つを削除すると別のエラーが発生し、その原因を究明すると複数のステータスを記録できないため、カウントを参照して、1つのビットでステータスを記録するのではなく、1つのintでステータスを記録することができます.つまり32ビットは40億個以上を記録することができ、intを使うのは、一般的にブロンを使うと文字列にぶつかるので、intを使ってもあまり大きくありません.また、文字列のハッシュ値を計算するときは、通常int型の数字に変換するので、32ビットのintで複数の状態を記録するのが頼りになります.私たちのintは1つのユニットに相当するため、ハッシュマッピングを経て直接配列の中で状態を変えることに相当するので問題が来て、このようにすると空間が大きすぎて、もし複数のハッシュ関数を使って、5つを使うならば、約20バイトの空間で、私たちが処理しているのは大量のデータで、オーバーヘッドが大きすぎますが、そうしてもいいです.文字列ごとに保存するよりもスペースが相対的に小さいので、ある状態を削除するときは、対応するセルの状態数字-1だけでいいです.

#include 
#include 
using namespace std;
class bitSet
{
     
public:
	bitSet(size_t range)
	{
     
		_bits.resize((range >> 5) + 1);
	}

	void Set(size_t N)
	{
     
		size_t index = N >> 5;
		size_t bitNum = N % 32;
		_bits[index] |= (1 << bitNum);
	}
	void Reset(size_t N)
	{
     
		size_t index = N >> 5;
		size_t bitNum = N % 32;
		_bits[index] &= (~(1 << bitNum));
	}
	bool Test(size_t N)
	{
     
		size_t index = N >> 5;
		size_t bitNum = N % 32;
		return (_bits[index] >> bitNum) & 1;
	}
private:
	vector<int> _bits;
};

void testBitSet()
{
     
	bitSet bs(1001);
	bs.Set(5);
	bs.Set(63);
	bool ret = bs.Test(33);
	if (ret)
	{
     
		cout << "  " << endl;
	}
	else
	{
     
		cout << "   " << endl;
	}
}
//k = (m / range) * ln2
//m = k / ln2 * range 
//k / 0.7 * range
struct HashFun1
{
     
	size_t operator () (const string& s)
	{
     
		size_t hash = 0;
		for (const auto& e : s)
		{
     
			hash = hash * 131 + e;
		}
		return hash;
	}
};
struct HashFun2
{
     
	size_t operator () (const string& s)
	{
     
		size_t hash = 0;
		for (const auto& e : s)
		{
     
			hash = hash * 65599 + e;
		}
		return hash;
	}
};

struct HashFun3
{
     
	size_t operator () (const string& s)
	{
     
		size_t hash = 0;
		for (const auto& e : s)
		{
     
			hash = hash * 3781 + e;
		}
		return hash;
	}
};

template <class T, class HashFun1, class HashFun2, class HashFun3>
class BloomFilter
{
     
public:
	BloomFilter(size_t range)
		:_bitset(5 * range)
		,_bitCount(5 * range)
	{
     }

	void Set(const T& data)
	{
     
		size_t index1 = HashFun1()(data) % _bitCount;
		size_t index2 = HashFun2()(data) % _bitCount;
		size_t index3 = HashFun3()(data) % _bitCount;
		_bitset.Set(index1);
		_bitset.Set(index2);
		_bitset.Set(index3);
	}

	bool Test(const T& data)
	{
     
		size_t index1 = HashFun1()(data) % _bitCount;
		if (!_bitset.Test(index1))
		{
     
			return false;
		}
		size_t index2 = HashFun2()(data) % _bitCount;
		if (!_bitset.Test(index2))
		{
     
			return false;
		}
		size_t index3 = HashFun3()(data) % _bitCount;
		if (!_bitset.Test(index3))
		{
     
			return false;
		}
		return true;
	}
private:
	bitSet _bitset;
	size_t _bitCount;
};

int main()
{
     
	//testBitSet();
	BloomFilter<string, HashFun1, HashFun2, HashFun3> bf(10);
	bf.Set("https://www.google.com/search?sxsrf=ACYBGNRGx4dQYtS12uHZAIz");
	bf.Set("https://www.google.com/search?sxsrf=ACYBGNRGx4");
	bf.Set("arch?sxsrf=ACYBGNRGx4d");

	bool ret = bf.Test("https://www.google.com/earch?sxsrf=ACYBGNRGx4");
	if (ret)
	{
     
		cout << "  " << endl;
	}
	else
	{
     
		cout << "   " << endl;
	}

	system("pause");
	return 0;
}