C++之 位图&布隆过滤器_布隆过滤器查找,,每个元素都需要位图吗

目录

一、位图是什么？

 二、位图海量数据查找

三、位图的应用

四、位图的模拟实现

妙哉的函数！

五、布隆过滤器的概念

 六、布隆过滤器的模拟实现

6.1、布隆过滤器的删除

6.2、布隆过滤器优点

6.3、布隆过滤器缺陷

---

一、位图是什么？

位图其实也是应用哈希思想的一种对数据进行快速查找的方法。位图将每个比特位的两种状态来表示数据的存在与否，0表示数据不存在1表示数据存在。实际应用中一般用来在特别大的数据量中查找元素是否存在。

位图应用的例子：

我们先来看位图映射少量的元素：可以看到在一个数组中有1到22中个别元素如果如果我们每次查找数组中1~22中一个元素是否存在我们每次都需要遍历一遍数组那么是十分慢的，所以我们可以用位图的方式也就是用22个比特位来代表这22个数字的存在状态。那么我们每次判断一个数据是否存在于数组中就可以到位图中去查找。

 二、位图海量数据查找

在平时的生活中，比如腾讯这样的互联网大厂，每天要存储的数据就是海量的，假如是有四十亿，要求查找40亿的数据中某个元素是否存在那么我们就可以用位图的方式来表示。

首先我们来计算一下不用位图的方式来查询四十亿数据。那么我们首先大概计算一下40亿数据大概是占用多少内存。

 可以发现，需要16G的内存才能存储完，但是很多时候16G的内存太大了，我们可能一共只有8G或16G的内存，要是光存储这个数据就要16G的话，那代价也太大了，所以我们要想办法来减小内存，那么这时候我们就可以采用位图来进行解决。

 能够看到，使用位图的话，空间的大小就能够很好的降低

三、位图的应用

 

四、位图的模拟实现

对位图的操作其实已经包括了基本上所有的对于二进制的操作，在模拟实现的时候尤为能够凸显出来

namespace bit
{
	template<size_t _N>
	class bitset
	{
		typedef unsigned long _Ty;
	public:
		bitset()
		{
			_Tidy();
		}
	public:
		size_t count() const
		{
			size_t _V = 0;
			for (int _I = _Nw; 0 <= _I; --_I)
			{
				for (_Ty _X = _A[_I]; _X != 0; _X >>= 4)
					_V += "\0\1\1\2\1\2\2\3"
					"\1\2\2\3\2\3\3\4"[_X & 0xF];
			}
			return (_V);
		}
		//0000 1000 00 ==> 32
		unsigned long to_ulong() const
		{
			enum
			{
				_Assertion = 1 / (sizeof(unsigned long) % sizeof(_Ty) == 0)
			};
			int _I = _Nw;
			for (; sizeof(unsigned long) / sizeof(_Ty) <= _I; --_I)
			{
				//判断溢出
				if (_A[_I] != 0)
				{
					cout << "结果溢出." << endl;
					assert(0);
				}
			}
			unsigned long _V = _A[_I];
			for (; 0 <= --_I; )
				_V = _V << _Nb | _A[_I];
			return (_V);
		}
		bool none() const
		{
			return !any();
		}
		bool any() const
		{
			for (int _I = _Nw; 0 <= _I; --_I)
			{
				if (_A[_I] != 0)
					return  true;
			}
			return  false;
		}
		bitset<_N>& flip(size_t _P)//只把_P位置取反
		{
			assert(_P < _N);
 
			_A[_P / _Nb] ^= (_Ty)1 << _P % _Nb;
 
			return (*this);
		}
		bitset<_N>& flip()//全部取反
		{
			for (int _I = _Nw; 0 <= _I; --_I)
				_A[_I] = ~_A[_I];
			_Trim();
			return (*this);
		}
		bitset<_N>& reset()
		{
			_Tidy();
			return *this;
		}
		bitset<_N>& set()
		{
			_Tidy(~(_Ty)0);
			return (*this);
		}
		bitset<_N>& set(size_t _P, bool _X = true)
		{
			if (_X)
				_A[_P / _Nb] |= 0x01<<_P% _Nb;	//置1
			else
				_A[_P / _Nb] &= ~(0x01 << _P % _Nb);//就是上面的取反就行了
			
			return *this;
		}
		size_t size()const
		{
			return _N;
		}
		bool test(size_t _P)const
		{
			assert(_P >= 0 && _P < _N);
			return (_A[_P / _Nb] & (0x01 << _P % _Nb));//需要准确找到对应的位置
		}
	public:
		bool operator==(const bitset<_N>& _R) const
		{
			for (int _I = _Nw; 0 <= _I; --_I)
			{
				if (_A[_I] != _R._W(_I))
					return (false);
			}
			return (true);
		}
		bool operator!=(const bitset<_N>& _R) const
		{
			return (!(*this == _R));
		}
		_Ty _W(size_t _I) const
		{
			return (_A[_I]);
		}
	private:
		void _Tidy(_Ty _X = 0)
		{
			for (int _I = _Nw; 0 <= _I; --_I)
				_A[_I] = _X;
			if (_X != 0)
				_Trim();//如果设置的不是0，那就需要进行剪切了
		}
		void _Trim()
		{
			if (_N % _Nb != 0)
				_A[_Nw] &= ((_Ty)1 << _N % _Nb) - 1;
		}
		friend ostream& operator<<(ostream& _O, const bitset<_N>& _R)
		{
			for (size_t _P = _N; 0 < _P;)
				_O << (_R.test(--_P) ? '1':'0');
			return _O;
		}
	private:
		enum {
			_Nb = CHAR_BIT * sizeof(_Ty), //32
			_Nw = _N == 0 ? 0 : (_N - 1) / _Nb
		};
 
		_Ty _A[_Nw + 1]; //数组
	};
}

妙哉的函数！

​

五、布隆过滤器的概念

• 布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的（紧凑型的是指用位图进行实现）、比较巧妙的概率型（概率是指他不是一定准确的这一点我们在下面对其详细介绍中会提到）数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

 六、布隆过滤器的模拟实现

#include<iostream>
#include<string>
#include<bitset>
//#include<hash_map>
#include<bitset>
#include"bitset.h"
using namespace std;
 
#define _N 1000   //误判率
 
template<class T>
struct Hashfunc1
{
	size_t operator()(const T& key)
	{
		return BKDRHash(key.c_str());
	}
	size_t BKDRHash(const char* str)
	{
		register size_t hash = 0;
		while (size_t ch = (size_t)*str++)
		{
			hash = hash * 131 + ch;
		}
		return hash;
	}
};
 
 
template<class T>
struct Hashfunc2
{
	size_t operator()(const T& key)
	{
		return SDBMHash(key.c_str());
	}
	size_t SDBMHash(const char* str)
	{
		register size_t hash = 0;
		while (size_t ch = (size_t)*str++)
		{
			hash = 65599 * hash + ch;
		}
		return hash;
	}
};
 
template<class T>
struct Hashfunc3
{
	size_t operator()(const T& key)
	{
		return RSHash(key.c_str());
	}
	size_t RSHash(const char* str)
	{
		register size_t hash = 0;
		size_t magic = 63689;
		while (size_t ch = (size_t)*str++)
		{
			hash = hash * magic + ch;
			magic *= 378551;
		}
		return hash;
	}
};
 
 
template<class T, class KeyToInt1 = Hashfunc1<T>,
	class KeyToInt2 = Hashfunc2<T>,
	class KeyToInt3 = Hashfunc3<T>>
	class BloomFilter
{
public:
	BloomFilter() :_size(0)
	{}
public:
	void Insert(const string& v)
	{
		size_t idx1 = KeyToInt1()(v) % _N;
		_bitmap.set(idx1);
		size_t idx2 = KeyToInt2()(v) % _N;
		_bitmap.set(idx2);
		size_t idx3 = KeyToInt3()(v) % _N;
		_bitmap.set(idx3);
 
		_size++;
	}
	bool Test(const T& key)const
	{
		size_t idx1 = KeyToInt1()(key) % _N;
		if (_bitmap.test(idx1) == 0)
			return false;
		size_t idx2 = KeyToInt2()(key) % _N;
		if (_bitmap.test(idx2) == 0)
			return false;
		size_t idx3 = KeyToInt3()(key) % _N;
		if (_bitmap.test(idx3) == 0)
			return false;
 
		return true;//可能存在，也有可能存在误判
	}
private:
	bitset<_N> _bitmap;//位图
	size_t  _size;
};

6.1、布隆过滤器的删除

我们可以看到上面没有给出布隆过滤器的删除，这是因为用位图的方式实现布隆过滤器将删除布隆过滤器当中的元素是无法删除的。如果我们将一个元素的所有映射关系都置为0那么可能会影响其他元素的存在。

 

 

6.2、布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关

2. 哈希函数相互之间没有关系，方便硬件并行运算。

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。因为布隆过滤器保存的是元素存在与否的信息。

4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势。

5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

6.3、布隆过滤器缺陷

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

3. 一般情况下不能从布隆过滤器中删除元素

4. 如果采用计数方式删除，可能会存在计数回绕问题