前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【C++进阶】位图/布隆过滤器与海量数据处理

【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。

代码语言:javascript
复制
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并不影响原来的值。

代码语言:javascript
复制
void reset(size_t x)
{
	size_t i = x / 32;
	size_t j = x % 32;

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

接口 test

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

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

代码语言:javascript
复制
bool test(size_t x)
{
	size_t i = x / 32;
	size_t j = x % 32;

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

三.位图完整代码

代码语言:javascript
复制
    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;
	};

四.布隆过滤器

概念

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

布隆过滤器的插入

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

各种字符串哈希函数

代码语言:javascript
复制
        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的个数。

五.布隆过滤器完整代码

代码语言:javascript
复制
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内存,如何找到两个文件交集?分别给出 精确算法和近似算法。

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

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

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

如何找交集?

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

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

此时分两种情况:

  1. 相同数据太多
  2. 哈希冲突太多

解决方案:

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

位图应用

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

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

所以就需要用位图解决。

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

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

我们可以用:

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

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

代码语言:javascript
复制
    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;
	};

2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?

还是和前面一样使用双位图,如果只把一个文件的数据映射到一个位图,另一个文件的数据用来遍历找交集的话,就会出现重复项。

把两个文件的数据分别映射到两个位图中,由于整形数据是有范围的,实际上在100亿个整数中,有非常多重复的,当两个文件的数据映射完成后,遍历所有整数,如果在两个位图中都在,那么这个数就是一个交集。这要做的好处是不会找到重复的数。

3. 位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数

这题还是和第一题是一样的,只不过是找不超过2次的整数,可以:

  • 00 表示出现 0 次
  • 01 表示出现 1 次
  • 10 表示出现 2 次
  • 11 表示出现 2 次以上
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-01-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一.什么是位图
  • 二.位图的模拟实现
    • 思路
      • 接口 set
        • 接口 reset
          • 接口 test
          • 三.位图完整代码
          • 四.布隆过滤器
            • 概念
              • 布隆过滤器的插入
                • 布隆过滤器的查找
                  • 布隆过滤器的删除
                  • 五.布隆过滤器完整代码
                  • 六.海量数据处理面试题
                    • 哈希切割
                      • 位图应用
                        • 1. 给定100亿个整数,设计算法找到只出现一次的整数?
                          • 2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
                            • 3. 位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数
                            相关产品与服务
                            对象存储
                            对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
                            领券
                            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档