从前慢现在也慢

这个屌丝很懒，什么也没留下！

热门标签

位图bitset ，布隆过滤器详解及模拟实现[C++]_布隆过滤器位图原理

作者：从前慢现在也慢 | 2024-06-27 16:56:24

踩

布隆过滤器位图原理

位图

问题引入

这里有一个关于鹅厂的题：

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

解决这个题关键是：给40亿个不重复的无符号整数。40亿个整型是需要占有多少内存，16G。我们用数组的排序，红黑树存储不下。如果是比特位呢？

因为数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

刚才我们已经知道40亿个整数要存16G，一个整数是4字节，一个字节8byte，那么一个整数是32byte，所以40亿比特位大致为：16G/32byte=0.5G=500M。500M对于内存是可以承受的。

我们知道开数组最小是以字符（char）类型开辟数组，没有听说过开多少bit位的数组。如果按照char类型开辟数组，如何得知x映射的值在第几char对象上？x的映射的值，在这个char对象上的第几个bit位上?

不管开辟是char类型还是int类型，都是不重要的。如果开辟int类型需要找到x映射的位置，只需要对x/32，先找到该值在第几个int对象上。再对x%32，找到的这个int对象上再确定是第几个bit位。1个int类型是32bit位。这样就确定好了映射的位置。

例：找到64在数组中映射的位置

位图概念

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

下面代码运行图说明VS2019环境下为小端机，小端机：低对低，高对高。

这里提到大小端问题，是为了说明运算符左移是往高位移，右移是往低位移动，并非方向上的左移右移

这里先用char类型进行进行理解，选取7，8作为例子。7位高地址，8位低地址。char的大小端顺序正好是和左移顺序契合的。如果向高位移动，低地址往高地址移动-左移，高地址往低地址移动-右移。

对于int，如果以它的大小端来确定往高位移动，我们会发现7，8是高到低，但（7，8）到（5,6）确是低到高。很显然在以前对int进行左移右移操作的时候，也是左移向高位移的，右移向低位移，那么关于大小端的处理，我们是不需要考虑，操作系统会帮助处理。

bitset类各函数接口总览


namespace Simulate
{
	//模拟实现位图
	template<size_t N>
	class bitset
	{
	public:
		//构造函数
		bitset();
		//设置位
		void set(size_t pos);
		//清空位
		void reset(size_t pos);
		//反转位
		void flip(size_t pos);
		//获取位的状态
		bool test(size_t pos);
		//获取可以容纳的位的个数
		size_t size();
		//获取被设置位的个数
		size_t count();
		//判断位图中是否有位被设置
		bool any();
		//判断位图中是否全部位都没有被设置
		bool none();
		//判断位图中是否全部位都被设置
		bool all();
		//打印函数
		void Print();
	private:
		vector<int> _bits; //位图
	};
}

bitset类的实现

构造函数

在构造位图时，我们需要根据所给位数N，创建一个N位的位图，并且将该位图中的所有位都初始化为0。

一个整型有32个比特位，因此N个位的位图就需要用到N/32个整型，但是实际我们所需的整型个数是N/32+1，因为所给非类型模板参数N的值可能并不是32的整数倍。

例如，当N为40时，我们需要用到两个整型，即40/32+1=2。

在这里插入图片描述

代码如下：


		bitset(size_t _N = N):_bits(_N/32+1 , 0)
		{}

set、reset、flip、test

set成员函数用于设置位。

设置位图中指定的位的方法如下：

计算出该位位于第 i 个整数的第 j 个比特位。
将1左移 j 位后与第 i 个整数进行或运算即可。

代码如下：


		void set(size_t x)
		{
			size_t index = x / 32;
			size_t pos = x % 32;
 
			_bits[index] |= (1 << pos);
		}

reset成员函数用于清空位。

清空位图中指定的位的方法如下：

计算出该位位于第 i 个整数的第 j 个比特位。
将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。

代码如下：


//复位
		void reset(size_t x)
		{
			size_t index = x / 32;
			size_t pos = x % 32;
 
			_bits[index] &= ~(1 << pos);
		}

flip成员函数用于反转位。

反转位图中指定的位的方法如下：

计算出该位位于第 i 个整数的第 j 个比特位。
将1左移 j 位后与第 i 个整数进行异或运算即可。

代码如下：


        //反转位
		void flip(size_t x)
		{
			size_t index = x / 32;
			size_t pos = x % 32;	
			_bits[index] ^= (1 << pos);
		}

test成员函数用于获取位的状态。

获取位图中指定的位的状态的方法如下：

计算出该位位于第 i 个整数的第 j 个比特位。
将1左移 j 位后与第 i 个整数进行与运算得出结果。
若结果非0，则该位被设置，否则该位未被设置。

代码如下：


		//判断是否存在
		bool test(size_t x)
		{
			size_t index = x / 32;
			size_t pos = x % 32;
 
			return _bits[index] & (1 << pos);
		}

size、count

size成员函数用于获取位图中可以容纳的位的个数。

我们直接将所给非类型模板参数进行返回即可。


		//获取可以容纳的位的个数
		size_t size()
		{
			return N;
		}

count成员函数用于获取位图中被设置的位的个数。

获取位图中被设置的位的个数，也就是统计位图中1的个数，我们只需要依次统计每个整数二进制中1的个数，然后将其相加即可得到位图中1的个数。

统计二进制中1的个数的方法如下：

将原数 n 与 n - 1 进行与运算得到新的 n 。
判断 n 是否为0，若 n 不为0则继续进行第一步。

如此进行下去，直到 n 最终为0，此时该操作进行了几次就说明二进制中有多少个1。

因为该操作每进行一次就会消去二进制中最右边的1，例图如下：

代码如下：


		//获取被设置位的个数
		size_t count()
		{
			size_t count = 0;
			for (auto e : _bits)
			{
				int num = e;
				while (num)
				{
					num = num & (num - 1);
					count++;
				}
			}
			return count; 
		}

any、none、all

any成员函数用于判断位图中是否有位被设置。

我们只需遍历每一个整数，若这些整数全部都为0，则说明位图中没有位被设置过。
虽然位图可能并没有包含最后一个整数的全部比特位，但由于我们构造位图时是将整数的全部比特位都初始化成了0，因此不会对此处判断造成影响。


		//判断位图中是否有位被设置
		bool any()
		{
			for (auto x : _bits)
				if (x != 0)
					return true;
			return false;
		}

none成员函数用于判断位图中是否全部位都没有被设置。

位图中是否全部位都没有被设置，实际上就是位图中有位被设置的反面，因此none成员函数直接调用any成员函数，然后将返回值取反后再进行返回即可。

代码如下：


		//判断位图中是否全部位都没有被设置
		bool none()
		{
			return !any();
		}

all成员函数用于判断位图中是否全部位都被设置。

判断过程分为两步：

先检查前n-1个整数的二进制是否为全1。
再检查最后一个整数的前N%32个比特位是否为全1。

需要注意的是，如果位图没有包含最后一个整数的全部比特位，那么最后一个整数的二进制无论如何都不会为全1，所以在判断最后一个整数时应该只判断位图所包含的比特位。

代码如下：


		//判断位图中是否全部位都被设置
		bool all()
		{
			for (size_t i = 0; i < N - 1; i++)
				if ((~_bits[i]))
					return false;
			for (size_t i = 0; i < N % 32; i++)
				if (_bits[N - 1] & (1 << i) == 0)
					return false;
			return true;
		}

打印函数

可以实现一个打印函数，便于检查我们上述代码的正确性，打印位图时遍历位图所包含的比特位进行打印即可，在打印位图的过程中可以顺便统计位图中位的个数count，将count与我们传入的非类型模板参数N进行比较，可以判断位图大小是否是符合我们的预期。


		//打印函数
		void Print()
		{
			int count = 0;
			size_t n = _bits.size();
			//先打印前n-1个整数
			for (size_t i = 0; i < n - 1; i++)
			{
				for (size_t j = 0; j < 32; j++)
				{
					if (_bits[i] & (1 << j)) //该位被设置
						cout << "1";
					else //该位未被设置
						cout << "0";
					count++;
				}
			}
			//再打印最后一个整数的前N%32位
			for (size_t j = 0; j < N % 32; j++)
			{
				if (_bits[n - 1] & (1 << j)) //该位被设置
					cout << "1";
				else //该位未被设置
					cout << "0";
				count++;
			}
			cout << " " << count << endl; //打印总共打印的位的个数
		}

bitset实现代码


	template<size_t N>
	class bitset
	{
	public:
		bitset(size_t _N = N) :_bits(_N / 32 + 1, 0)
		{}
 
		//置位
		void set(size_t x)
		{
			size_t index = x / 32;
			size_t pos = x % 32;
 
			_bits[index] |= (1 << pos);
		}
 
		//复位
		void reset(size_t x)
		{
			size_t index = x / 32;
			size_t pos = x % 32;
 
			_bits[index] &= ~(1 << pos);
		}
 
		//判断是否存在
		bool test(size_t x)
		{
			size_t index = x / 32;
			size_t pos = x % 32;
 
			return _bits[index] & (1 << pos);
		}
 
		//反转位
		void flip(size_t x)
		{
			size_t index = x / 32;
			size_t pos = x % 32;
			_bits[index] ^= (1 << pos);
		}
 
		//获取可以容纳的位的个数
		size_t size()
		{
			return N;
		}
		//获取被设置位的个数
		size_t count()
		{
			size_t count = 0;
			for (auto e : _bits)
			{
				int num = e;
				while (num)
				{
					num = num & (num - 1);
					count++;
				}
			}
			return count; 
		}
 
		//判断位图中是否有位被设置
		bool any()
		{
			for (auto x : _bits)
				if (x != 0)
					return true;
			return false;
		}
		//判断位图中是否全部位都没有被设置
		bool none()
		{
			return !any();
		}
		//判断位图中是否全部位都被设置
		bool all()
		{
			for (size_t i = 0; i < N - 1; i++)
				if ((~_bits[i]))
					return false;
			for (size_t i = 0; i < N % 32; i++)
				if (_bits[N - 1] & (1 << i) == 0)
					return false;
			return true;
		}
		//打印函数
		void Print()
		{
			int count = 0;
			size_t n = _bits.size();
			//先打印前n-1个整数
			for (size_t i = 0; i < n - 1; i++)
			{
				for (size_t j = 0; j < 32; j++)
				{
					if (_bits[i] & (1 << j)) //该位被设置
						cout << "1";
					else //该位未被设置
						cout << "0";
					count++;
				}
			}
			//再打印最后一个整数的前N%32位
			for (size_t j = 0; j < N % 32; j++)
			{
				if (_bits[n - 1] & (1 << j)) //该位被设置
					cout << "1";
				else //该位未被设置
					cout << "0";
				count++;
			}
			cout << " " << count << endl; //打印总共打印的位的个数
		}
 
 
	private:
		//int* _bits;
		std::vector<int> _bits;
	};

布隆过滤器

由名字得知，布隆过滤器是一个过滤器，而且不是用于存储数据的。这个就好比自来水过滤器一样，将水的的杂质排除来。那么布隆过滤器就是对大量的数据进行过滤，对一定不存在的数据进行过滤，再向可能存在的数据进行其他操作。

本质上布隆过滤器是哈希与位图的结合，位图有着节省空间，查询快的特点。但缺点也很明显：

1.一般要求范围相对集中，范围特别分散，空间消耗就上升，就例如存储两个数（1,99999）。

2.只能针对整型，因为底层是bit位。

但通过哈希的映射，就很好的解决范围相对集中，只针对整型这缺点；在位图的基础上又解决浪费空间的缺点。所以这句话就非常棒：不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。

布隆过滤器实质是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

实现原理

首先来看一下布隆过滤器数据结构，这里有三个字符串，“hello”，“world”，“bit_set”,通过hashfunc映射到位图，如果为1则存在，0则不存在。

这个时候就需要确定一下，存在是准确的呢，还是不存在是准确的。

1.在是不准确的，因为可能本来不在，但是这个位置跟别人冲突，出现误判

2.不在是准确的，

1这种情况，比如又有一个字符串“worde”，通过映射处理，映射的位置与“world”一样，发生冲突。

出现误判了，又该如何处理呢？这个就好像我们在生活中那家店好吃，当问一个人时（他可能是吃不得辣），说不好吃；但是这样的结果可能并不是你想要的，那不妨多问几个人。降低误判率。

在这里的做法是映射多个位置，降低误判率，但不能消除误判，布隆过滤器的改进。

布隆过滤器的实现

如何选择哈希函数个数和布隆过滤器长度

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

由上图可知，当布隆过滤器越长报错率越小，哈希函数的个数越多报错率越小。但占用的内存会变大，这个之间取一个平衡。

那应该如何选择哈希函数的个数和布隆过滤器的长度呢，有人通过计算后得出了以下关系式：

$m = - \frac{nlnp}{(ln2)^{2}}$

$k = \frac{m}{n}ln2$

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

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


	template<size_t N ,
		class K = string , 
		class Hash1 = BKDRHash, 
		class Hash2 = APHash, 
		class Hash3 = DJBHash>
	class bloomfilter
	{
    public:
    //...
    private:
	Simulate::bitset<N> _bs;
	size_t _N;
	};

布隆过滤器的插入

布隆过滤器当中需要提供一个Set接口，用于插入元素到布隆过滤器当中。插入元素时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后将位图中的这三个比特位设置为1即可。

代码如下：


		void set(const K& key)
		{
			size_t index1 = hash1(key) % _N;
			size_t index2 = hash2(key) % _N;
			size_t index3 = hash3(key) % _N;
			_bs.set(index1);
			_bs.set(index2);
			_bs.set(index3);
		}

布隆过滤器的查找

布隆过滤器当中还需要提供一个test接口，用于检测某个元素是否在布隆过滤器当中。检测时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后判断位图中的这三个比特位是否被设置为1。

只要这三个比特位当中有一个比特位未被设置则说明该元素一定不存在。
如果这三个比特位全部被设置，则返回true表示该元素存在（可能存在误判）。

代码如下：


		bool test(const K& key)
		{
			size_t index1 = hash1(key) % _N;
			if (!_bs.test(index1))
				return false;
 
			size_t index2 = hash2(key) % _N;
			if (!_bs.test(index2))
				return false;
 
			size_t index3 = hash3(key) % _N;
			if (!_bs.test(index3))
				return false;
			
			return true;
		}

布隆过滤器的删除

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

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

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

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

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

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

布隆过滤器的优点

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

布隆过滤器的缺陷

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

布隆过滤器使用场景

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

比如当我们首次访问某个网站时需要用手机号注册账号，而用户的各种数据实际都是存储在数据库当中的，也就是磁盘上面。

当我们用手机号注册账号时，系统就需要判断你填入的手机号是否已经注册过，如果注册过则会提示用户注册失败。但这种情况下系统不可能直接去遍历磁盘当中的用户数据，判断该手机号是否被注册过，因为磁盘IO是很慢的，这会降低用户的体验。

由于大部分情况下用户用一个手机号注册账号时，都是知道自己没有用该手机号注册过账号的，因此在布隆过滤器中查找后都是找不到的，此时就避免了进行磁盘IO。而只有布隆过滤器误判或用户忘记自己用该手机号注册过账号的情况下，才需要访问磁盘进行复核。

这种情况下就可以使用布隆过滤器，将所有注册过的手机号全部添加到布隆过滤器当中，当我们需要用手机号注册账号时，就可以直接去布隆过滤器当中进行查找。
如果在布隆过滤器中查找后发现该手机号不存在，则说明该手机号没有被注册过，此时就可以让用户进行注册，并且避免了磁盘IO。
如果在布隆过滤器中查找后发现该手机号存在，此时还需要进一步访问磁盘进行复核，确认该手机号是否真的被注册过，因为布隆过滤器在判断元素存在时可能会误判。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/763105

位图bitset ，布隆过滤器详解及模拟实现[C++]_布隆过滤器 位图原理

位图

问题引入

位图概念

bitset类各函数接口总览

bitset类的实现

构造函数

set、reset、flip、test

size、count

any、none、all

打印函数

bitset实现代码

布隆过滤器

实现原理

布隆过滤器的实现

如何选择哈希函数个数和布隆过滤器长度

布隆过滤器的插入

布隆过滤器的查找

布隆过滤器的删除

布隆过滤器的优点

布隆过滤器的缺陷

布隆过滤器使用场景

位图bitset ，布隆过滤器详解及模拟实现[C++]_布隆过滤器位图原理