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

位图和布隆过滤

article 2024/11/16 14:02:49

1.位图的概念

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

1. 遍历，时间复杂度O(N)

2. 排序(O(NlogN))，利用二分查找: logN

但问题是这里有40亿个数，若是我们要将这些数全部加载到内存当中，那么将会占用16G的空间，空间消耗是很大的。因此从空间消耗来看，上面这两种方法实际都是不可行的。

实际在这个问题当中，我们只需要判断一个数在或是不在，即只有两种状态，那么我们可以用一个比特位来表示数据是否存在，如果比特位为1则表示存在，比特位为0则表示不存在。比如：

无符号整数总共有2^{32}个，因此记录这些数字就需要2^{32}个比特位，也就是512M的内存空间，内存消耗大大减少。

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

2.bitset的使用

C++的STL库中也提供看位图这个数据结构，其主要操作就是set，reset和test。下面是其一些成员函数。

下面是其基本使用：

#include<iostream>
#include<bitset>

using namespace std;

int main()
{
	// 最后一位就是第0位
	bitset<8> bs;
	bs.set(2);  //00000100
	bs.set(4);  //00010100
	
	cout << bs << endl;
	cout << bs.count() << endl; //2		该位图有有多少个2
	cout << bs.test(1) << endl; //0		从左往右第2个位置为1还是为0
	cout << bs[0] << endl; //0
	bs.reset(2);  //将第二位置为0
	bs.reset(3); //将第三位置为0
	cout << endl;
	bitset<16> bs1(8);  //0000000000001000 转为二进制初始化
	bitset<16> bs2(0xfa5); // 0000111110100101
	bitset<16> bs3(string("10111001")); //0000000010111001
	cout << (bs1|bs2) << endl;  //相同位数的位图可以进行&| ~
	cout << (bs << 1) << endl;  //可以进行移位
	return 0;
}

3.位图的模拟实现

namespace xwy {
	//非类型模板参数
	template <size_t N>
	class bitset
	{
	public:
		bitset()
		{
			size_t x = N / 32 + 1;
			_bits.resize(x, 0);
		}
		
		void set(size_t n) 
		{
			assert(n < N);
			size_t i = n / 32;
			size_t j = n % 32;
			_bits[i] |= (1 << j);
		}
		void reset(size_t n)
		{
			assert(n < N);
			size_t i = n / 32;
			size_t j = n % 32;
			_bits[i] &= (~(1 << j));
		}
		int test(size_t n)
		{
			assert(n < N);
			size_t i = n / 32;
			size_t j = n % 32;
			if ((_bits[i] >> j) & 1)
				return 1;
			return 0;
		}
		void Print()
		{
			for (int n = N - 1; n >= 0; n--)
			{
				if (test(n))
					cout << "1";
				else
					cout << "0";
			}
			cout << endl;
		}
	private:
		vector<int> _bits;
	};
}

4.布隆过滤器的概念

在注册账号设置昵称的时候，为了保证每个用户昵称的唯一性，系统必须检测你输入的昵称是否被使用过，这本质就是一个key的模型，我们只需要判断这个昵称被用过，还是没被用过。

方法一：用红黑树或哈希表将所有使用过的昵称存储起来，当需要判断一个昵称是否被用过时，直接判断该昵称是否在红黑树或哈希表中即可。但红黑树和哈希表最大的问题就是浪费空间，当昵称数量非常多的时候内存当中根本无法存储这些昵称
方法二：用位图将所有使用过的昵称存储起来，虽然位图只能存储整型数据，但我们可以通过一些哈希算法将字符串转换成整型，比如BKDR哈希算法。当需要判断一个昵称是否被用过时，直接判断位图中该昵称对应的比特位是否被设置即可。

位图虽然能够大大节省内存空间，但由于字符串的组合形式太多了，映射到整数之中无论通过何种哈希算法将字符串转换成整型都不可避免会存在哈希冲突。

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询。

1. 布隆过滤器其实就是位图的一个变形和延申，虽然无法避免存在哈希冲突，但我们可以想办法降低误判的概率。
2. 当一个数据映射到位图中时，布隆过滤器会用多个哈希函数将其映射到多个比特位，当判断一个数据是否在位图当中时，需要分别根据这些哈希函数计算出对应的比特位，如果这些比特位都被设置为1则判定为该数据存在，否则则判定为该数据不存在。
3. 布隆过滤器使用多个哈希函数进行映射，目的就在于降低哈希冲突的概率，一个哈希函数产生冲突的概率可能比较大，但多个哈希函数同时产生冲突的概率可就没那么大了。

布隆过滤器的插入

如下：baidu和tencent两个字符串都映射并插入到位图的三个位置当中

布隆过滤器的查找

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

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

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关

误判率的控制

很显然，过小的布隆过滤器很快所有的比特位都会被设置为1，此时布隆过滤器的误判率就会变得很高，因此布隆过滤器的长度会直接影响误判率，布隆过滤器的长度越长其误判率越小。


此外，哈希函数的个数也需要权衡，哈希函数的个数越多布隆过滤器中比特位被设置为1的速度越快，并且布隆过滤器的效率越低，但如果哈希函数的个数太少，也会导致误判率变高。

那应该如何选择哈希函数的个数和布隆过滤器的长度呢，人们经过数学计算和验证发现公式

其中k为哈希函数个数，m为布隆过滤器长度，n为插入的元素个数。

我们这里可以大概估算一下，如果使用3个哈希函数，即k的值为3，l n 2 ln2ln2的值我们取0.7，那么 m 和 n 的关系大概是m = 4.3 × n，也就是布隆过滤器的长度应该是插入元素个数的4.3倍,我们向上取，使得其长度是五倍，即实际长度len是位图长度的五倍

5.布隆过滤器的模拟实现

#pragma once
#include<iostream>
#include<vector>
#include<bitset>
#include<assert.h>
#include<string>

using namespace std;

//三种hash方法
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

//布隆过滤器的模拟实现 主要就是set和test两个方法
namespace xwy {
	template<size_t N,
		class K=string,
		class Hash1 = BKDRHash,
		class Hash2= APHash,
		class Hash3= DJBHash>
	class BloomFilter
	{
	public:
		void set(K key)
		{
			size_t hash1 = Hash1()(key) % M; //匿名对象使用hash方法
			size_t hash2 = Hash2()(key) % M;
			size_t hash3 = Hash3()(key) % M;

			_bs->set(hash1);				//将对应数值设置进 位图中
			_bs->set(hash2);
			_bs->set(hash3);
		}
		bool Test(const K& key)
		{
			size_t hash1 = Hash1()(key) % M;
			if (_bs->test(hash1) == false)
				return false;

			size_t hash2 = Hash2()(key) % M;
			if (_bs->test(hash2) == false)
				return false;

			size_t hash3 = Hash3()(key) % M;
			if (_bs->test(hash3) == false)
				return false;

			return true; // 存在误判(有可能3个位都是跟别人冲突的，所以误判)
		}

	private:
		static const int M = N * 5;
		//std::bitset<M> _bs;  // 直接复用位图
		std::bitset<M>* _bs = new std::bitset<M>;// std中使用的bitset没有开辟在堆区
	};
}

布隆过滤器的删除

布隆过滤器一般不支持删除操作，原因如下：

因为布隆过滤器判断一个元素存在时可能存在误判，因此无法保证要删除的元素确实在布隆过滤器当中，此时将位图中对应的比特位清0会影响其他元素。

此外，就算要删除的元素确实在布隆过滤器当中，也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的，此时将这些比特位清0也会影响其他元素。


如何让布隆过滤器支持删除？

要让布隆过滤器支持删除，必须要做到以下两点：

1. 保证要删除的元素在布隆过滤器当中。比如刚才的呢称例子当中，如果通过调用Test函数得知要删除的昵称可能存在布隆过滤器当中后，可以进一步遍历存储昵称的文件，确认该昵称是否真正存在。
2. 保证删除后不会影响到其他元素。可以为位图中的每一个比特位设置一个对应的计数值，当插入元素映射到该比特位时将该比特位的计数值++，当删除元素时将该元素对应比特位的计数值–-.


可是布隆过滤器最终还是没有提供删除的接口，因为使用布隆过滤器本来就是要节省空间和提高效率的。在删除时需要遍历文件或磁盘中确认待删除元素确实存在，而文件IO和磁盘IO的速度相对内存来说是很慢的，并且为位图中的每个比特位额外设置一个计数器，就需要多用原位图几倍的存储空间，这个代价也是不小的。

布隆过滤器的优点

        增加和查询元素的时间复杂度为O(K)（K为哈希函数个数，一般比较小,与数据量大小无关。
        哈希函数相互之间没有关系，方便硬件并行运算。
        布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
        在能够承受一定的误判时，布隆过滤器比其他数据结构有着很大的空间优势。
        数据量很大时，布隆过滤器可以表示全集，其他数据结构不能。
        使用同一组哈希函数的布隆过滤器可以进行交、并、差运算。

布隆过滤器的缺陷

  • 有误判率，即存在假阳性（False Position），即不能准确判断元素是否在集合中（补救方法：再自建一个白名单，存储可能会误判的数据）
  • 不能获取元素本身。
  • 一般情况下不能从布隆过滤器中删除元素。

布隆过滤器使用场景

使用布隆过滤器的前提是，布隆过滤器的误判不会对业务逻辑造成影响。

比如当我们首次访问某个网站时需要注册用户id，而用户的各种数据实际都是存储在数据库当中的，也就是磁盘上面。此时如果我们布隆过滤器判断该id 已经注册，我们再去实际查询数据库，可以大大增加我们的判断速度。

布隆过滤器是位图的扩展，哈希表是将string映射到int的vector容器中，而布隆过滤器映射到位图中，它可以节省空间，同时可以进行字符串的映射。

6.海量数据处理面试题目

海量数据处理是指基于海量数据的存储和处理，正因为数据量太大，所以导致要么无法在短时间内迅速处理，要么无法一次性装入内存。

  • 对于时间问题，就可以采用位图、布隆过滤器等数据结构来解决。
  • 对于空间问题，就可以采用哈希切割等方法，将大规模的数据转换成小规模的数据逐个击破。

一、位图相关

题目一：给定100亿个整数，设计算法找到只出现一次的整数。

给两个42亿的位图bs1，bs2，如果10出现0次，两个位图对应位置都为0，出现一次，第一个位图set(10),第二个位图还是0，出现两次以及两次以上，则把位图的两个位置都置为1.

存储100亿个整数大概需要40G的内存空间，因此题目中的100亿个整数肯定是存储在文件当中的。为了能映射所有整数，位图的大小必须开辟为 2^{32}位，也就是代码中的4294967295，因此开辟一个位图大概需要512M的内存空间，两个位图就要占用1G的内存空间，所以代码中选择在堆区开辟空间，若是在栈区开辟则会导致栈溢出。

题目二：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？

方案一：（一个位图需要512M内存）

1. 依次读取第一个文件中的所有整数，将其映射到一个位图。
2. 再读取另一个文件中的所有整数，判断在不在位图中，在就是交集，不在就不是交集。
方案二：（两个位图刚好需要1G内存，满足要求）

1. 依次读取第一个文件中的所有整数，将其映射到位图1。
2. 依次读取另一个文件中的所有整数，将其映射到位图2。
3. 将位图1和位图2进行与操作，结果存储在位图1中，此时位图1当中映射的整数就是两个文件的交集。

题目三：一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数。

该题目和题目一的方法是一样的，在该题目中我们标记整数时可以将其分为四种状态：

出现0次。
出现1次。
出现2次。
出现2次以上。
一个整数要表示四种状态也是只需要两个位就够了，此时当我们读取到重复的整数时，就可以让其对应的两个位按照00→01→10→11的顺序进行变化，最后状态是01或10的整数就是出现次数不超过2次的整数。

二、布隆过滤器相关

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

题目要求给出近视算法，也就是允许存在一些误判，那么我们就可以用布隆过滤器。

  • 先读取其中一个文件当中的query，将其全部映射到一个布隆过滤器当中。
  • 然后读取另一个文件当中的query，依次判断每个query是否在布隆过滤器当中，如果在则是交集，不在则不是交集。

如何扩展BloomFilte使得它支持删除元素的操作。

布隆过滤器一般不支持删除操作，原因如下：

因为布隆过滤器判断一个元素存在时可能存在误判，因此无法保证要删除的元素确实在布隆过滤器当中，此时将位图中对应的比特位清0会影响其他元素。
此外，就算要删除的元素确实在布隆过滤器当中，也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的，此时将这些比特位清0也会影响其他元素。


如果要让布隆过滤器支持删除，就必须要做到以下两点：

1. 保证要删除的元素在布隆过滤器当中，比如在删除一个用户的信息前，先遍历数据库确认该用户确实存在。
2. 保证删除后不会影响到其他元素，比如可以为位图中的每一个比特位设置一个对应的计数值，当插入元素映射到该比特位时将该比特位的计数值++，当删除元素时将该元素对应比特位的计数值–即可。

三、哈希切割相关

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

首先需要估算一下这里一个文件的大小，便于确定将一个文件切分为多少个小文件。
假设平均每个query为50字节，那么100亿个query就是500G，由于我们只有1G内存，这里可以考虑将一个文件切分成100个小文件。
这里我们将这两个文件分别叫做A文件和B文件，此时我们将A文件切分成了A0~A999共400个小文件，将B文件切分成了B0~B999共1000个小文件。
在切分时需要选择一个哈希函数进行哈希切分，以切分A文件为例，切分时依次遍历A文件当中的每个query，通过哈希函数将每个query转换成一个整型 i 并对1000进行去模，然后将这个query写入到小文件Ai当中。对于B文件也是同样的道理，但切分A文件和B文件时必须采用的是同一个哈希函数。

经过hash之后，hash冲突和相同的query进入同一个文件，每个文件都在500M左右（存得下），此时我们将每个文件Ai存储到set当中，如果是因为query相同进入的这个文件，set会将其去重，因此不必当心，如果因为hash冲突进去的且冲突数量过多，我们insert到set中，set存储不下，抛异常，我们此时对Ai和Bi再选用另外的hash函数去切分，（比如利用另一个hash函数把Ai，Bi再分到10个文件当中），再对这次切分的结果Aii，进行insert到 一个set中，成功之后，读取Bii文件的每个query，进行set.find()操作，如果查找成功，它就是两个文件交集，将这个query存到结果文件中。

给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址？如何找到top K的IP？如何直接用Linux系统命令实现？

该题目同样需要用到哈希切分，切分步骤如下：

我们将这个log file叫做A文件，由于A文件的大小超过100G，这里可以考虑将A文件切分成100个小文件。
在切分时选择一个哈希函数进行哈希切分，通过哈希函数将A文件中的每个IP地址转换成一个整型 i（0 ≤ i ≤ 99），然后将这个IP地址写入到小文件Ai当中。
由于哈希切分时使用的是同一个哈希函数，因此相同的IP地址计算出的 i值是相同的，最终这些相同的IP地址就会进入到同一个Ai小文件当中。

经过哈希切分后得到的这些小文件，理论上就能够加载到内存当中了，我们采用map<string, int>容器统计次数。如果个别小文件仍然太大那可以对其再进行一次哈希切分，总之让最后切分出来的小文件能够加载到内存。

现在要找到出现次数最多的IP地址，就可以分别将各个小文件加载到内存中， 然后用一个map<string, int>容器统计出每个小文件中各个IP地址出现的次数，然后比对各个小文件中出现次数最多的IP地址，最终就能够得到log file中出现次数最多的IP地址。


如果要找到出现次数top K的IP地址，可以先将一个小文件加载到内存中，选出小文件中出现次数最多的K个IP地址建成一个小堆，然后再依次比对其他小文件中各个IP地址出现的次数，如果某个IP地址出现的次数大于堆顶IP地址出现的次数，则将该IP地址与堆顶的IP地址进行交换，然后再进行一次向下调整，使其仍为小堆，最终比对完所有小文件中的IP地址后，这个小堆当中的K个IP地址就是出现次数top K的IP地址。


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

相关文章：

  • [Admin] Dashboard Filter for Mix Report Types
  • 麒麟kysec安全
  • 民事诉讼中，火灾事故认定书并非不可推翻，其证明力弱于鉴定意见
  • sql在按照当前表查询返回
  • k8s笔记——核心概念
  • 数据产品：深度探索与案例剖析
  • 【Linux】内核调用栈打印函数dump_stack使用效果
  • 充电桩布局建设的智能趋势
  • c中柔性数组
  • AI开发-计算机视觉库-OpenCV
  • AVL树了解并简单实现
  • 产业与学术相互促进，2024年OEG海上能源博览会助力全球能源可持续发展
  • PL/0-语法分析器
  • SystemVerilog学习——类的继承
  • node.js知识点总结
  • PaoluGPT——千里挑一
  • Windows安装Elasticsearch及Spring Boot整合ES教程
  • Flutter-左侧导航栏跟随窗口的宽变化
  • 使用机器学习优化数据库查询性能
  • FastGPT部署通义千问Qwen和智谱glm模型|OneAPI配置免费的第三方API
  • 基于集成Whisper 与 Pepper-GPT改进人机交互体验并实现顺畅通信
  • Git之国内项目托管平台
  • 物联网低功耗广域网LoRa开发(二)：LoRa开发环境搭建及驱动移植
  • CSS基础知识01
  • 论文 | On Second Thought, Let’s Not Think Step by Step!
  • 【澜舟科技-注册/登录安全分析报告】