当前位置： 首页 > article >正文

C++——位图与布隆过滤器

article 2024/11/15 15:18:56

目录

一，位图

1.1 关于大量数据的问题

1.2 位图概念

1.3 位图模拟实现

 1.4 位图的应用

 1.5 位图优缺点

二，布隆过滤器

2.1 一些场景

2.2 布隆过滤器概念

2.3 布隆过滤器模拟实现和测试

2.4 布隆过滤器查找

2.5 布隆过滤器删除

2.6 布隆过滤器优缺点

一，位图

1.1 关于大量数据的问题

先看一个面试题：

给40亿个不重复的未排序的无符号整数，然后如何快速判断一个数是否在这40亿个数中

 以我们前面的知识，最先想到的有两种方法：1，排序+二分查找  2，存到哈希表和红黑树中再查

但是题目中给的是40亿个整数，我们先算下需要的内存：1G就是1024MB，是1024*1024KB，是1024*1024*1024Byte，相当于10亿Byte，所以，40亿个数需要4*40Byte大概就是16G的空间，所以由于空间的限制，上面两种方法就都可以去掉了。

所以我们需要一种更好的方法去存储这40亿个整数

1.2 位图概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常用来判断某个数据存不存在的。

比如上面的题目，判断数据在不在，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位位1，代表存在，为0表示不存在，如下图：

1.3 位图模拟实现

namespace bit
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 8 + 1, 0);//8+1，多开一个
			//这样开空间的 {(0       7)(8       15)(16       23)(24       31)...}
		}                    //  char      char         char
		//插入
		void set(size_t x)
		{
			size_t i = x / 8; //一个数组里面有很多个char，每个char有8个比特位，先算x需要被映射到哪个8比特位上
			size_t j = x % 8; //再算在该8比特位里面的位置，整个过程可以理解为看电影时，先找在哪一排，再找具体的位置
			_bits[i] |= (1 << j);
			//假如x是10，10/8=1，找到第一个char，再模8就是2，然后将1往左移两格，向高位移，比如00000001，往左移就是00000010
			//这样的话，我们就用非常小的空间代价把大量数据存起来了
		}
		//删除
		void erset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] &= ~(1 << j);//按位取反，1与0为0完成删除，0与0还是0，不变
		}
		//判断在不在
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j); //如果存在，那1与1就是1，返回1；如果不在，0与1就是0，返回0
			//return( _bit[i] >> j) & 1;
		}
	private:
		vector<char> _bits;
	};

	void test_bit_set1()
	{
		bitset<100> bs1;
		bs1.set(10);
		bs1.set(11);
		bs1.set(15);

		cout << bs1.test(10) << endl;
		cout << bs1.test(11) << endl;
		cout << bs1.test(15) << endl;
		bs1.erset(10);
		bs1.erset(11);
		bs1.erset(15);

		cout << bs1.test(10) << endl;
		cout << bs1.test(11) << endl;
		cout << bs1.test(15) << endl;
	}

	void test_bit_set2()
	{
		bitset<-1> bs1; //给的是整形的最大值
		bitset<0xFFFFFFFF> bs2;
	}
}

 1.4 位图的应用

先看下下面几个题目：

①给100亿个整数，设计算法找到只出现一次的整数

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

③一个文件有100亿个整数，给1G内存，请设计算法找到出现次数不超过2的所有整数

上面的题目都有个共同点，就是和1，2和大于2的数字有关，换成位就是01，10和11，所以我们可以用一个封装了两个位图的类来解决，对于问题一，在类插入时，如果是00则表示第一次出现，01表示出现过一次，10出现两次，10后的不考虑；后面的两个问题也是同样的解决逻辑

namespace bit
{	
    template<size_t N>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			bool inset1 = _bs1.test(x);
			bool inset2 = _bs2.test(x);

			//00
			if (inset1 == false && inset2 == false) //还未出现
			{
				// -> 01
				_bs2.set(x);
			}
			else if (inset1 == false && inset2 == true) //第一次出现
			{
				// -> 10
				_bs1.set(x);
				_bs2.erset(x);
			}
			else if (inset1 == true && inset2 == false) //第二及以上次出现
			{
				// -> 11
				_bs1.set(x);
				_bs2.set(x);
			}
		}

		void print_onse_num()
		{
			for (size_t i = 0; i < N; ++i)
			{
				if (_bs1.test(i) == false && _bs2.test(i) == true)
				{
					cout << i << endl;
				}
			}
		}

	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};

	void test_bit_set3()
	{
		int a[] = { 3, 4, 5, 2, 3, 4, 4, 4, 4, 12, 77, 65, 44, 4, 44, 99, 33, 33, 33, 6, 5, 34, 12 };
		twobitset<100> bs;
		for (auto e : a)
		{
			bs.set(e);
		}

		bs.print_onse_num();
	}

 1.5 位图优缺点

优点：位图的存储和查找效率非常快，而且可以节省很多空间

缺点：可以看出，位图只能存储可以转化成位的整数，如果是其他类型的数就不能使用位图，比如浮点数，string等自定义类型

所以为了使位图的设计能够支持其他类型的数据，就有了下面要介绍的布隆过滤器

二，布隆过滤器

2.1 一些场景

直接看图：

 又比如我们生活中的场景：

我们在注册账号时：

2.2 布隆过滤器概念

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

2.3 布隆过滤器模拟实现和测试

struct HashBKDR
{
	//BKDR字符串转int
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}

		return val;
	}
};
struct HashAP
{
	// AP
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};
struct HashDJB
{
	// DJB
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}

		return hash;
	}
};

//降低冲突，一个值映射一个位置容易误判，映射多个位置可以降低误判
// N表示准备要映射N个值
//哈希函数个数，代表一个值映射几个位，哈希函数越多，误判率越低，但是需要的空间消耗越多
template<size_t N,
	class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB> 
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		_bits->set(hash1);

		size_t hash2 = Hash2()(key) % (_ratio * N);
		_bits->set(hash2);

		size_t hash3 = Hash3()(key) % (_ratio * N);
		_bits->set(hash3);
	}

	bool Test(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		if (!_bits->test(hash1))
			return false; // 准确的

		size_t hash2 = Hash2()(key) % (_ratio * N);
		if (!_bits->test(hash2))
			return false; // 准确的

		size_t hash3 = Hash3()(key) % (_ratio * N);
		if (!_bits->test(hash3))
			return false;  // 准确的

		return true; // 可能存在误判
	}

private:
	const static size_t _ratio = 5;
	bit::bitset<_ratio* N>* _bits = new bit::bitset<_ratio * N>;
	//由于std库中这个东东是用静态数组实现的，一旦数据过大就会栈溢出，所以使用new的方式将数据转移到堆上，就可以解决了
};

测试一

void TestBloomFilter1()
{
	BloomFilter<10> bf;
	string arr1[] = { "苹果", "西瓜", "阿里", "美团", "苹果", "字节", "西瓜", "苹果", "香蕉", "苹果", "腾讯" };

	for (auto& str : arr1)
	{
		bf.Set(str);
	}

	for (auto& str : arr1)
	{
		cout << bf.Test(str) << “ ”;
	}
	cout << endl << endl;

	string arr2[] = { "苹果111", "西瓜", "阿里2222", "美团", "苹果dadcaddxadx", "字节", "西瓜sSSSX", "苹果 ", "香蕉", "苹果$", "腾讯" };

	for (auto& str : arr2)
	{
		cout << str << ":" << bf.Test(str) << endl;
	}
}

 测试二

void TestBloomFilter2()
{
	srand(time(0));
	const size_t N = 100000;
	BloomFilter<N> bf;
	cout << sizeof(bf) << endl;//因为报栈溢出，查看bf的大小

	std::vector<std::string> v1;
	std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";

	for (size_t i = 0; i < N; ++i)
	{
		v1.push_back(url + std::to_string(1234 + i)); //让每个字符不一样
	}

	for (auto& str : v1)
	{
		bf.Set(str);
	}

	// 相似
	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string url = "http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html";
		url += std::to_string(rand() + i);
		v2.push_back(url);
	}

	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.Test(str))
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		string url = "zhihu.com";
		url += std::to_string(rand() + i);
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

2.4 布隆过滤器查找

布隆过滤器不是为了解决冲突，而是为了降低冲突！

将一个元素用多个哈希函数映射到一个位图中，因此被映射到位置的比特位一定为1，所以在查找时，分别计算每个哈希值对应的比特位置存储的是否为0，只要有一个为0，表面该元素一定不在哈希表中，如果都不为0，那么可能存在，因此存在误判

2.5 布隆过滤器删除

布隆过滤器不能直接支持删除，因为在删除一个元素时会影响其他元素

2.6 布隆过滤器优缺点

优点：

①增加和查询的时间复杂度为O(K)，K为哈希函数个数，一般都是一位数，因此和数据量大小无关

②哈希函数相互之间没有关系，方便硬件运算

③布隆过滤器不存储元素本身，所以在某些保密要求较高的场合有很大优势

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

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

缺点：

①有误判，即存在假阳性，不能准确判断元素是否在集合中，但也有补救方法

②不能获取元素本身

③大多数情况不能删除元素


http://www.kler.cn/a/233290.html

相关文章：

  • Python 中.title()函数和.lower()函数
  • Mysql数据库里的SSH连接
  • 浅谈：基于三维场景的视频融合方法
  • Java面向对象编程进阶之包装类
  • 【嵌入式开发】单片机CAN配置详解
  • 系统架构设计师论文：大数据Lambda架构
  • JVM系列——垃圾收集器Parrlel Scavenge、CMS、G1常用参数和使用场景
  • 二维差分---三维差分算法笔记
  • Android:自定义控件
  • Vue 封装的 axios 类的使用（小bug 改进）
  • 5G技术对物联网的影响
  • C# BackgroundWorker的使用
  • 广义表-C语言
  • 面向工业 X.0 的工业网络简述
  • 微软.NET6开发的C#特性——类、结构体和联合体
  • VitePress-12-markdown中使用vue的语法
  • 年货大数据（电商平台年货节数据）：水果销售额增长72%，海鲜肉类涨幅高于蔬菜
  • Stable Diffusion 模型下载：Disney Pixar Cartoon Type A（迪士尼皮克斯动画片A类）
  • React 常用 Hooks
  • 探索Gin框架：Golang Gin框架请求参数的获取
  • 【Web】基于Mybatis的SQL注入漏洞利用点学习笔记
  • 图书商城系统
  • 机器学习系列——（二十二）结语
  • Windows下搭建Redis Sentinel
  • 低代码流程引擎在数字设计平台的应用：简化创作流程，提升生产效率
  • CSS高级技巧