【C++】哈希应用之布隆过滤器

这篇具有很好参考价值的文章主要介绍了【C++】哈希应用之布隆过滤器。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】哈希应用之布隆过滤器,C++,c++,哈希算法,开发语言

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

1.布隆过滤器的提出

2.布隆过滤器的概念

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

3.1布隆过滤器的插入

3.2布隆过滤器的查找

3.3布隆过滤器不能删除

4.布隆过滤器的优点

5.布隆过滤器的缺陷

6.使用场景

7.源码


前言

布隆过滤器是哈希的又一重要应用,上篇文章我们谈到位图只能处理整型数据的问题,那么对于布隆过滤器来说它结合了哈希与位图,使数据处理扩展到了字符串甚至其他数据类型上。


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。 

=========================================================================文章来源地址https://www.toymoban.com/news/detail-843695.html

GITEE相关代码:🌟樊飞 (fanfei_c) - Gitee.com🌟

=========================================================================


1.布隆过滤器的提出

在面对海量数据时,红黑树等数据结构虽然查找效率高效,但不可避免的有空间上的巨大开销,所以我们提出了位图这种概念。

但对于位图来说,只能处理整型数据,因为数字采用『 直接定址法』计算哈希值几乎不会产生哈希冲突的问题,而假若是一个字符串呢?虽然我们可以通过不同的哈希函数将字符串转换为整型,但是字符串的组合形式复杂多样,无论通过哪种哈希函数都不可避免地会出现大量哈希冲突。

这里的哈希冲突就是不同的昵称最终被转换成了相同的整型,此时就可能会引发误判,即某个字符串明明不在数据中,却被系统判定为在,于是就出现了布隆过滤器。


2.布隆过滤器的概念

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

布隆过滤器其实就是位图的一个变形和延申,虽然无法避免存在哈希冲突,但我们可以想办法降低误判的概率。

原理:当一个数据映射到位图中时,『 布隆过滤器』会用多个哈希函数将其映射到多个比特位,当判断一个数据是否在位图当中时,需要分别根据这些哈希函数计算出对应的比特位,如果这些比特位都被设置为1则判定为该数据存在,否则则判定为该数据不存在。

布隆过滤器使用多个哈希函数进行映射,目的就在于『 降低哈希冲突的概率』,一个哈希函数产生冲突的概率可能比较大,但多个哈希函数同时产生冲突的概率可就没那么大了。

例子:假设布隆过滤器使用三个哈希函数进行映射,那么“张三”这个昵称被使用后位图中会有三个比特位会被置1,当有人要使用“李四”这个昵称时,就算前两个哈希函数计算出来的位置都产生了冲突,但由于第三个哈希函数计算出的比特位的值为0,此时系统就会判定“李四”这个昵称没有被使用过。


虽然布隆过滤器已经极大的降低了哈希冲突的概率,但是仍然可能会产生误判:

  • 当布隆过滤器判断一个数据存在可能是不准确的,因为这个数据对应的比特位可能被其他一个数据或多个数据占用了。
  • 当布隆过滤器判断一个数据不存在是准确的,因为如果该数据存在那么该数据对应的比特位都应该已经被设置为1了。

显然布隆过滤器的效率与哈希函数的个数与过滤器长度息息相关,那么他们之间究竟存在怎样的关系呢?

网上有大佬经过计算得到如下图这样的结论:

【C++】哈希应用之布隆过滤器,C++,c++,哈希算法,开发语言

感兴趣的这是原文链接->详解布隆过滤器的原理,使用场景和注意事项 - 知乎 (zhihu.com)


 为了简化,我们取k为3,即设计3个哈希函数,最终得到m与n的关系:『 m≈4*n』。

注意:为了简化计算我们取ln2≈0.7。


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

注意这里我们需要三个哈希函数,所以需要三个仿函数设计:

//布隆过滤器
template<size_t N, 
    class K = string,         //默认为字符串(常用)
    class Hash1 = BKDRHash,   //三种哈希函数
    class Hash2 = APHash, 
    class Hash3 = DJBHash>
class BloomFilter
{
public:
	//...
private:
	bitset<N> _bs;
};

这三种哈希函数的实现如下,原理感兴趣的自行研究:

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				value ^= ((value << 7) ^ s[i] ^ (value >> 3));
			}
			else
			{
				value ^= (~((value << 11) ^ s[i] ^ (value >> 5)));
			}
		}
		return value;
	}
};
struct DJBHash
{
	size_t operator()(const string& s)
	{
		if (s.empty())
			return 0;
		size_t value = 5381;
		for (auto ch : s)
		{
			value += (value << 5) + ch;
		}
		return value;
	}
};

3.1布隆过滤器的插入

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

代码如下:

void Set(const K& key)
{
	//计算出key对应的三个位
	size_t i1 = Hash1()(key) % N;
	size_t i2 = Hash2()(key) % N;
	size_t i3 = Hash3()(key) % N;

	//设置位图中的这三个位
	_bs.set(i1);
	_bs.set(i2);
	_bs.set(i3);
}

3.2布隆过滤器的查找

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

只要这三个比特位当中有一个比特位未被设置则说明该元素一定不存在。

如果这三个比特位全部被设置,则返回true表示该元素存在。

注意:判断存在的情况可能是误判。

代码如下:

bool Test(const K& key)
{
	//依次判断key对应的三个位是否被设置
	size_t i1 = Hash1()(key) % N;
	if (_bs.test(i1) == false)
	{
		return false; //key一定不存在
	}

	size_t i2 = Hash2()(key) % N;
	if (_bs.test(i2) == false)
	{
		return false; //key一定不存在
	}

	size_t i3 = Hash3()(key) % N;
	if (_bs.test(i3) == false)
	{
		return false; //key一定不存在
	}

	return true; //key对应的三个位都被设置,key存在(可能误判)
}

3.3布隆过滤器不能删除

为什么布隆过滤器不能删除呢?

  • 首先我们在布隆过滤器的概念部分已经提到过,布隆过滤器判断一个元素在时可能会出现误判,既然会出现误判,我们如何删除这个可能不存在的元素呢?
  • 其次就算要删除的元素确实在布隆过滤器当中,也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的,此时将这些比特位清0也会影响其他元素。

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

  • 首先要保证要删除的元素在布隆过滤器当中,简单的通过布隆过滤器判断存在后,再确认该昵称是否真正存在,比如通过遍历的方式(这也是布隆过滤器为什么叫过滤器,只能简单过滤,要确保严谨还得加其他手段)。
  • 其次保证删除后不会影响到其他元素。可以为位图中的每一个比特位设置一个类似引用计数,当插入元素映射到该比特位时将该比特位的计数值++,当删除元素时将该元素对应比特位的计数值--即可。

那么我们要不要让布隆过滤器支持删除?

  • 答案是不要!!
  • 布隆过滤器的提出就是为了高效,快速过滤。在删除时还需要遍历文件或磁盘中确认待删除元素确实存在,而文件IO和磁盘IO的速度相对内存来说是很慢的,并且为位图中的每个比特位额外设置一个计数器,就需要多用原位图几倍的存储空间,本末倒置。

4.布隆过滤器的优点

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

5.布隆过滤器的缺陷

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

6.使用场景

当我们在某网站注册账号需要填入信息时,比如昵称,往往很快地在输入框的右面显示✅或❎以此提示我们该条昵称是否被人注册过。

但是用户的数据往往存储在数据库中,通过网络查询数据库的延迟不会这么快,所以这里一般都是使用了布隆过滤器。

当用户输入信息后,优先到布隆过滤器中查找:

  • 如果在布隆过滤器中查找后发现该昵称不存在,则说明该昵称没有被注册过,此时就可以让用户进行注册,并且避免了磁盘IO或者数据库查询。
  • 如果在布隆过滤器中查找后发现该昵称存在,此时还需要进一步访问数据库进行复核,确认该昵称是否真的被注册过,因为布隆过滤器在判断元素存在时可能会误判。

通过布隆过滤器的过滤作用,我们可以减轻服务器和数据库的压力,从而提升用户体验。


7.源码

#include<bitset>
struct HashFuncBKDR
{
	// BKDR
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

struct HashFuncAP
{
	// AP
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (size_t 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 HashFuncDJB
{
	// DJB
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash = hash * 33 ^ ch;
		}

		return hash;
	}
};

template<size_t N, 
	class K = string,
	class Hash1 = HashFuncBKDR,
	class Hash2 = HashFuncAP,
	class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = Hash1()(key) % M;
		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 size_t M = 10 * N;
    //STL库中位图实现为静态数组(即int arr[]这种),存储在对象中,数据量大时可能会导致栈溢出,所以这里我们new一个,使用堆空间避免栈溢出
	std::bitset<M>* _bs = new std::bitset<M>;
};

=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

=========================================================================

到了这里,关于【C++】哈希应用之布隆过滤器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 哈希思想应用:位图,布隆过滤器,哈希切分

    1.问题 给你40亿个不重复的无符号整数,没排过序.给一个无符号整数,如何快速判断一个数是否在这40亿个数中? 2.分析 1 Byte = 8 bit 1KB = 1024 Byte 1MB = 1024KB = 1024 1024 大约= 10的6次方Byte 1GB = 1024MB = 1024 10的6次方 大约= 10的9次方Byte = 10亿字节 因此4GB 约等于40亿字节 其实最快的方式就是

    2024年04月17日
    浏览(3)
  • [C++]哈希应用之位图&布隆过滤器

               主厨:邪王真眼 主厨的主页:Chef‘s blog   所属专栏:c++大冒险        我们之前学习了哈希表,哈希表通过映射关系,实现了O(1)的复杂度来查找数据,哈希在实践中是一个非常重要的思想,今天要学习的就是哈希思想的两大应用:位图与布隆过滤器 给 40 亿个

    2024年04月15日
    浏览(3)
  • 【C++】哈希的应用:位图、哈希切分与布隆过滤器

    需要云服务器等云产品来学习Linux的同学可以移步/--腾讯云--/--阿里云--/--华为云--/官网,轻量型云服务器低至112元/年,新用户首次下单享超低折扣。   目录 一、位图 1、位图的概念 2、大厂面试题 2.1位图应用(腾讯) 2.2位图应用 3、位图的优缺点 二、哈希切分 三、布隆过滤

    2023年04月09日
    浏览(10)
  • 【C++高阶(六)】哈希的应用--位图&布隆过滤器

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 哈希最常用的应用是unordered 系列的容器,但是当面对海量数据 如100亿个数据中找有没有100这 个数时,使用无序容器的话内存放不下 所以哈希

    2024年02月05日
    浏览(7)
  • 【C++学习】哈希的应用—位图与布隆过滤器

    文章简介 : 在这篇文章中,你会学习到关于哈希思想的最常见的两个应用,也就是 位图 与 布隆过滤器 , 文章会讲解位图和布隆过滤器的概念,底层实现,对应的适应的场景,以及相关经典 海量数据面试题 及解析。 所谓位图,就是用每一位来存放某种状态,适用于 海量

    2024年04月14日
    浏览(10)
  • C++进阶--哈希的应用之位图和布隆过滤器

    哈希是一种映射的思想。 先来看一道题:给40亿个不重复的无符号整数,没排序过。给一个无符号整数,如何 快速判断 一个数 是否在 这40亿个数中。 首先想到的解法可能有这几种: 解法1 :遍历40亿个数,O(N) 解法2 :先排序,快排O( N l o g 2 N Nlog_2N Nl o g 2 ​ N ),再利

    2024年02月22日
    浏览(8)
  • 【C++杂货铺】再谈哈希算法:位图 | 布隆过滤器 | 哈希切分

    给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 解决方案 : 遍历 :遍历这40亿个整数,去判断该数是否在这40亿个整数中。时间复杂度是 O ( N ) O(N) O ( N ) 。 set :用 set 将这40亿个整数存起来,然后去判断这个数是否在

    2024年02月08日
    浏览(6)
  • C++哈希hash:位图、布隆过滤器的实现及应用

    所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用 来判断某个数据存不存在的。 当我们想查找某一个数据是否存在或者是否处于某种状态时,相比于直接对存放数据的容器进行遍历查找,与原存放数据的容器所建立映射关系的位图来

    2024年04月11日
    浏览(9)
  • 哈希思想应用【C++】(位图,布隆过滤器,海量数据处理面试题)

       目录 一,位图 1. 位图概念 2.实现 3. 测试题 位图的优缺点 二,布隆过滤器 1). 布隆过滤器提出 2). 概念 3). 布隆过滤器的查找 4). 布隆过滤器删除(了解) 5). 布隆过滤器优点 6). 布隆过滤器缺陷 三,海量数据面试题 1)哈希切割 我们首先由一道面试题来理解位图 给40亿个不

    2024年02月04日
    浏览(8)
  • 哈希的应用——布隆过滤器

    上一篇文章,我们学习了位图,位图在某些场景下是非常适用的,非常快捷方便。 但是,在文章的最后,我们也提出了位图的一些缺陷——比如位图只能映射整型数据,其它类型的数据则不行。 因为位图里面的元素去映射的其实就是下标嘛,而下标的话都是整型啊。 那有没

    2024年02月09日
    浏览(7)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包