【C++进阶】位图/布隆过滤器与海量数据处理

aosei

发布于 2024-01-23 15:21:31

1040

发布于 2024-01-23 15:21:31

文章被收录于专栏：csdn-nagiYcsdn-nagiY

一.什么是位图

我们知道数据的最小存储位是比特（bite），每个比特位只能是0或1，我们用1和0来表示在或不在，或是其它类型的状态信息，这种结构称作位图。

当我们面对海量数据时，使用 int 类型来存储数据，会需要巨大的空间，这样成本就太高了，这种时候可以用位图来解决，它可以大幅降低所需空间。

二.位图的模拟实现

库里面是有位图这个结构的，可以看到，有一个非类型模板参数，它决定位图的大小。

接下来让我们来模拟实现简易的位图，同样采用非类型模板参数的形式。

思路

位图是需要访问比特位的，但是我们没有任何一个类型的大小是一个比特位，所以我们可以开一个整型数组（当然char也行），一个整型就表示32个比特位，这样我们数组的大小只需要开 N/32+1 就行了。

接口 set

set 的作用是把该比特位设置成1。

给我们一个数 x ，我们该如何把 x 映射到位图中呢，并把映射到的这个位置改成1（并且不改变其它位置）呢？

首先一个字节是32个比特位，先除上个32就能知道 x 在哪个字节。
然后在模上32就能知道是在哪个比特位
比如说80，80/32=2，80%32=16，那么80就在第2个字节的第16个比特位。

接下来使用位运算的知识将这个位置设置成1，并不影响其他位置。

我们知道按位或运算是只要有1就是1，所以按位或上一个0，并不影响原来的值，按位或上一个1结果为1。

void set(size_t x)
{
	size_t i = x / 32;   //求出在哪个字节
	size_t j = x % 32;   //求出在哪个比特位

	bs[i] |= (1 << j);   
}

接口 reset

reset 是把该位置的比特位设置成 0 。

这就要用到按位与了。

对于按位与运算，只要有0就是0，按位与上一个1并不影响原来的值。

void reset(size_t x)
{
	size_t i = x / 32;
	size_t j = x % 32;

	bs[i] &= (~(1 << j));
}

接口 test

判断一个位置的比特位是 0 还是 1

这里同样还是用按位与，但要注意是对某一个位置按位与上一个1，不用像 reset 一样取个反。

bool test(size_t x)
{
	size_t i = x / 32;
	size_t j = x % 32;

	return bc[i] &(1 << j);   //注意不能写成 &=
}

三.位图完整代码

    template<size_t N>
	class Bitset
	{
	public:
		Bitset()
		{
			bs.resize(N / 32 + 1);
		}

		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			bs[i] |= (1 << j);
		}

		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			bs[i] &= (~(1 << j));
		}

		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			return bs[i] &(1 << j);
		}

	private:
		vector<int> bs;
	};

四.布隆过滤器

概念

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

布隆过滤器的插入

布隆过滤器的插入是利用多个哈希函数，将一个数据映射到一个位图的多个位置上，生活中，要插入的数据类型大多是字符串型，所以本篇文章将以插入字符串为例模拟实现布隆过滤器。

各种字符串哈希函数

        void set(const K& key)
		{
			size_t hash1 = Hash1(key) % N;
			bs.set(hash1);
			size_t hash2 = Hash2(key) % N;
			bs.set(hash2);
			size_t hash3 = Hash3(key) % N;
			bs.set(hash3);
		}

布隆过滤器的查找

分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

所以布隆过滤器在实际应用中起到一个过滤器的作用，如果在的话还要到数据库里继续查找，防止误判，提高了效率；如果不在，就一定不存在，就不需要到数据库里取寻找。

布隆过滤器的删除

一般情况下布隆过滤器是不支持删除的，因为布隆过滤器存储的时候是一对多，如果删除一个位置，那么很可能会影响其它的数据。

如果非要删除的话，只能再加一个位图来表示每个比特位为1的个数。

五.布隆过滤器完整代码

struct BKDRHash
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto ch : str)
		{
			hash = hash * 131 + ch;     
		}
		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		size_t ch;
		for (long i = 0; i < str.size(); i++)
		{
			ch = str[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& str)
	{
		if (str.size() == 0)
			return 0;
		size_t hash = 5381;
		for(auto ch:str)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

template<size_t N,
			class K=string,
			class Hash1= BKDRHash,
			class Hash2= APHash,
			class Hash3= DJBHash>
	class BloomFilter
	{
	public:
		void set(const K& key)
		{
			size_t hash1 = Hash1(key) % N;
			bs.set(hash1);
			size_t hash2 = Hash2(key) % N;
			bs.set(hash2);
			size_t hash3 = Hash3(key) % N;
			bs.set(hash3);
		}

		bool test(const K& key)
		{
			size_t hash1 = Hash1(key) % N;
			
			size_t hash2 = Hash2(key) % N;
			
			size_t hash3 = Hash3(key) % N;
			
			return bs.test(hash1)&& bs.test(hash2)&& bs.test(hash2)
		}
	private:
		Bitset<N> bs;
	};

六.海量数据处理面试题

哈希切割

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。

对于大文件，我们可以分成多个小文件，那该怎那么分呢？

首先一定不能均分，均分的效率极低，我们可以利用哈希表的原理来分。

假设一个query的大小是30byte，100亿个query即为300G（1G大约是10亿byte），那么我们把它切成1000个文件，每个文件的大小为300MB左右。
读取文件数据，用哈希函数对1000取模，取模的结果相同的进同一号文件

如何找交集？

读取 Ai 小文件的数据放到set里，在读取 Bi 文件的数据，如果在就是交集并且删掉。

如果哈希冲突太多，会导致一个小文件的大小超过1个G，这该如何解决？

此时分两种情况：

相同数据太多
哈希冲突太多

解决方案：

先把Ai的query读到一个set，如果set的 insert 报错抛异常(bad_alloc)，那么就说明是大多数query都是冲突。如果能够全部读出来，insert 到set里面，那么说明Ai有大量相同的query
如果抛异常，说明有大量冲突，再换一个哈希函数，再进行二次切分。

位图应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？

这里有100亿个整数，如果用set，红黑树这一类的结构，空间必定不够。

所以就需要用位图解决。

但是一个比特位只能表示两种状态，怎么找到只出现一次的整数呢？

可以用两个链表，这样0和1两两组合就有四种状态：00 01 11 10

我们可以用：

00表示出现0次
01表示出现1次
11或10表示出现次数大于1次

可以复用 Bitset 来创建一个有两个位图的双位图结构。

    template<size_t N>
	class TwoBitset
	{
	public:
		void set(size_t x)
		{
			if (bs1.test(x) == 0 && bs2.test(x) == 0)  //00
				bs2.set(x);  //01
			else if (bs1.test(x) == 0 && bs2.test(x) == 1) //01
				bs1.set(x);  //11
			else
				;
		}

		bool test(size_t x)
		{
			if (bs1.test(x) == 0 && bs2.test(x) == 1)
				return true;
			else
				return false;
		}
	private:
		Bitset<N> bs1;
		Bitset<N> bs2;
	};