C++详细讲解模拟实现位图和布隆过滤器的方法-C/C++开发

位图（bitset）是一种常用的数据结构，常用在给一个很大范围的数，判断其中的一个数是不是在其中。在索引、数据压缩方面有很大的应用。布隆过滤器是由布隆提出的，它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以

位图

引论

四十亿个无符号整数，现在给你一个无符号整数，判断这个数是否在这四十亿个数中。

路人甲：简单，快排+二分。

可是存储这四十亿个整数需要多少空间？

简单算一下，1G=1024M=1024 * 1024KB=1024 * 1024 * 1024Byte，也就是说1G大概也就是十亿个字节。

四十亿个整数多大？40亿 * 4==160亿个字节，换算一下也就是16G。

我电脑内存也就十六个G，还不加上别的应用，显然内存超限了。

所以快排+二分是不可取的，那有没有别的法子呢？

所以也就有了下面要讲的位图。

概念

位图是什么？

根据上面的模型我们可以发现，之前要用四个字节存储一个数字，现在只需一个比特位，当然我们不是存储具体数值，而是存储数字的状态。

因为一个比特位只有两种状态，所以我们存储的是该数字是否存在（数字存在对应位为1，否则为0）

解决引论

上面发现本来需要4个字节存储，现在只需要1位去存储，一下子就缩小了32倍，所以原本需要16G内存存储的数据只需要0.5G。显然这个内存我们是开的起的。

那该怎么判断这个数字是否存在呢？将这个数字/8得到它在第几个字节，将这个数字%8即可得到他在这个数字在第几位。

比如10，就在第一个字节的第二位。（都是从0开始计数）

总结一下应该怎么解决引论提出的问题？开一个能存储42亿位的位图，查找时算出待查找数的位置，如果这个位置为1则表示存在，否则就不存在。

位图也是一种哈希思想的运用

位图的模拟实现

铺垫

从上面可以看出，位图的实现主要在于把某一位置为0和把某一位置为1。

如何把某一位置为1？

把那个位置 |1

|是按位或运算符

如何把某一位置为0？

把那个位置 &0

&是按位与运算符

所以我们在实现时只需要算出那个位置再进行位操作即可。

结构

构造函数

BitSet()
{
	_bits.resize(N / 8 + 1);//开这么多个字节,+1是怕有余数
}

比如开10个位就要开两个字节。

因为采用的是vector,所以所有的char都会被默认置为0。char类型的默认值就是0，空字符。

比如底层实现时resize第二个参数默认值给成T()，T为模板，当用char去实例化时，那默认值就是char()了，也就是ASCII码为0的字符。

存储

vector<char>_bits;

用vector存的。

set,reset,test

test作用：检查这一位是0还是1，是1返回true，否则返回false

bool test(size_t x)
{
	size_t integer = x / 8;//第几个字节
	size_t rem = x % 8;//字节的第几个位置
	return ((_bits[integer] >> rem) & 1) ? true : false;
}

set作用：把某一个位置置为1

void set(size_t x)//第x位置为1
{
	if (!test(x))//如果这一位是0，置为1的话++
	{
		_cnt++;
	}
	size_t integer = x / 8;//第几个字节
	size_t rem = x % 8;//字节的第几个位置
	_bits[integer] |= (1 << rem);
}

reset作用：把某一个位置置为0

void reset(size_t x)//第x位置为0
{
	if (test(x))//如果这一位是1，置为0的话--
	{
		_cnt--;
	}
	size_t integer = x / 8;//第几个字节
	size_t rem = x % 8;//字节的第几个位置
	_bits[integer] &= (~(1 << rem));
}

flip,size,count

flip：翻转，0变为1,1变为0

void flip(size_t x)//翻转
{
	if (test(x))//1
	{
		reset(x);
	}
	else//0
	{
		set(x);
	}
}

size：位图有多少位

size_t size() const
{
	return N;//模板参数
}

count：位图里有多少个1

size_t count()
{
	return _cnt;
}

any,none,all

any：位图里有没有1，有1返回true，否则返回false

bool any()
{
	if (_cnt)
	{
		return true;
	}
	return false;
}

none：与any相反

bool none()
{
	return !any();
}

all：全为1返回true，否则返回false

bool all()
{
	if (_cnt == N)
	{
		return true;
	}
	else
	{
		return false;
	}
}

重载流运算符

重载流运算符必须在BitSet里面加上一个函数声明

template<size_t T>
friend ostream& operator<<(ostream& out, const BitSet<T>& bs);

这里会出现的一个问题是，因为类已经有了一个模板参数，所以很容易写成

friend ostream& operator<<(ostream& out, const BitSet<N>& bs);

导致运行时报链接错误。

原因讲解：目录-解决方法

简单解释一下，因为这是一个声明，所以编译到这里时只当这是个友元函数的声明，并不会把函数里的模板N参数实例化，只有调用流运算符时才会去实例化，这就出现了二次编译（第一次编译只实例化了BitSet类，即类BitSet模板参数N被确定下来）

但因为友元函数只是声明并没有实例化，即第二种写法的N并没有被确定下来，到调用这个函数的时候要对N进行编译，但是不知道这个N具体是什么，因为N是一个模板参数被第一次实例化确定下来后就没了，编译器往上找也找不到，导致有函数声明但是找不到具体函数，从而发生了链接错误。解决就是写成第一种，第二次编译时看到了上面有一个模板声明就知道T是个模板参数，调用时第一次被确定的N传给现在的T，所以就能正确运行。

	ostream& operator<<(ostream& out, const BitSet<T>& bs)
	{
		//从后往前是低位到高位，库里面是这样的
		int len = bs.size() / 8 ;
		char tmp;
		tmp = bs._bits[len];
		for (int i = bs.size() % 8 - 1; i >= 0; i--)
		{
			if ((tmp >> i) & 1)
			{
				cout << '1';
			}
			else
			{
				cout << '0';
			}
		}
		for (int i = len-1; i >=0; i--)
		{
			tmp = bs._bits[i];
			for (int j = 7; j >=0; j--)
			{
				if ((tmp >> j) & 1)
				{
					cout << '1';
				}
				else
				{
					cout << '0';
				}
			}
		}
		//从前往后是低位到高位（人看起来合适）
		//for (int i=0;i<len;i++)
		//{
		//	tmp = bs._bits[i];
		//	for (int i =0;i<8;i++)
		//	{
		//		if ((tmp >> i) & 1)
		//		{
		//			cout << '1';
		//		}
		//		else
		//		{
		//			cout << '0';
		//		}
		//	}
		/

目录

位图

引论

概念