【数据结构 10】位图

一、位图

在海量数据的标记的时候，比如数十亿上百亿上千亿的数据，我们要统计数据是否出现，直接存储数据的话对内存的消耗太大了，这时我们可以通过位图来标记出现过的数据，位图可以标记0~42亿之间的整型数据，我们也可通过复用多个位图实现统计数据出现的次数。

二、布隆过滤器

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

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特
位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为
零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

三、代码

#define _CRT_SECURE_NO_WARNINGS 1

#pragma once
#include <iostream>
#include <vector>

template<size_t N>
class BitSet
{
public:
	BitSet()
	{
		// 每个元素为char类型，占8个bit位
		_bitSet.resize((N >> 3) + 1, 0);
	}

	// 将位图某一位置1
	void Set(size_t x)
	{
		size_t i = x >> 3;
		size_t j = x % 8;
		_bitSet[i] |= (1 << j);
	}

	// 将位图某一位置0
	void Reset(size_t x)
	{
		size_t i = x >> 3;
		size_t j = x % 8;
		_bitSet[i] &= (~(1 << j));
	}

	// 检查位图中某一位是否为1	
	bool Test(size_t x)
	{
		size_t i = x >> 3;
		size_t j = x % 8;
		return _bitSet[i] & (1 << j);
	}

private:
	std::vector<char> _bitSet;
};

四、测试

#define _CRT_SECURE_NO_WARNINGS 1

#include "BitSet.h"
using namespace std;

void TestBitSet()
{
	// 开辟42亿9千万个bit位，512M空间;
	BitSet<-1> bs;
	// BitSet<0xffffffff> bs;

	bs.Set(9);
	bs.Set(19);
	bs.Set(29);
	bs.Set(39);

	cout << bs.Test(9) << endl;
	cout << bs.Test(19) << endl;
	cout << bs.Test(29) << endl;
	cout << bs.Test(39) << endl;
	cout << bs.Test(49) << endl;

	bs.Reset(19);
	bs.Reset(29);

	cout << endl;
	cout << bs.Test(9) << endl;
	cout << bs.Test(19) << endl;
	cout << bs.Test(29) << endl;
	cout << bs.Test(39) << endl;
	cout << bs.Test(49) << endl;
}

int main()
{
	TestBitSet();

	return 0;
}