【C++】哈希与布隆过滤器

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

🌇个人主页:平凡的小苏
📚学习格言:命运给你一个低的起点,是想看你精彩的翻盘,而不是让你自甘堕落,脚下的路虽然难走,但我还能走,比起向阳而生,我更想尝试逆风翻盘
🛸C++专栏C++内功修炼基地
> 家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我真重要,各位路 过的友友麻烦多多点赞关注。 欢迎你们的私信提问,感谢你们的转发! 关注我,关注我,关注我,你们将会看到更多的优质内容!!

【C++】哈希与布隆过滤器,C++修炼内功,c++,哈希算法,开发语言

一、位图的概念

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

1、位图的面试题

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

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

【C++】哈希与布隆过滤器,C++修炼内功,c++,哈希算法,开发语言

2、位图模拟实现

#include <iostream>
#include <vector>
using std::cout;
using std::endl;
namespace sqy
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 8 + 1);
		}
		void set(size_t n)
		{
			size_t i = n / 8;//算出n属于_bits的哪一个下标
			size_t j = n % 8;//算出属于_bits下标的哪一个比特位
			_bits[i] |= 1 << j;
		} 

		void reset(size_t n)
		{
			size_t i = n / 8;//算出n属于_bits的哪一个下标
			size_t j = n % 8;//算出属于_bits下标的哪一个比特位
			_bits[i] &= (~(1 << j));
		}

		bool test(size_t n)
		{
			size_t i = n / 8;//算出n属于_bits的哪一个下标
			size_t j = n % 8;//算出属于_bits下标的哪一个比特位
			return _bits[i] & (1 << j);
		}
	private:
		std::vector<char> _bits;
	};

3、位图的应用

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

我们可以使用两个位图,如果是00则表示没有出现一次,01表示出现一次,10往后的就可以不用实现了。

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

使用两个位图,将两个文件的数据分别映射到对应的位图中,在进行遍历按位与,如果为1,则为交集,否则,反之。

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

我们可以使用两个位图,如果是00则表示没有出现一次,01表示出现一次,10表示出现两次,11往后的就可以不用实现了。

代码示例

template<size_t N>
	class twobitset
	{
	public:
		void set(size_t n)
		{
			if (b1.test(n) == false && b2.test(n) == false) //00 -> 01
			{
				b1.set(n);
			}
			else if (b1.test(n) == true && b2.test(n) == false) //01 -> 10
			{
				b1.reset(n);
				b2.set(n);
			}
		}

		void printOnce()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (!b2.test(i) && b1.test(i))
				{
					cout << i << " ";
				}
			}
			cout << endl;
		}
	private:
		bitset<N> b1;
		bitset<N> b2;
	};

4、位图的优缺点

优点:节省空间,查找速度快

缺点:要求范围相对集中,范围特别分散的,空间消耗大;

位图只对整型使用,浮点数、string等等其他类型无法使用。

如果要判断其他类型,该类型如果可以使用哈希函数转换为整型的,可以考虑布隆过滤器

二、布隆过滤器

1、布隆过滤器的概念

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

【C++】哈希与布隆过滤器,C++修炼内功,c++,哈希算法,开发语言

我们为了降低误判的概率,解决方法就是对同一个元素使用多组哈希函数进行映射,它能降低误判率,但增加了空间消耗,使用时需要把控号布隆过滤器的哈希函数的个数和布隆过滤器的长度

2、布隆过滤器的使用场景

1、不需要一定准确的场景,例如个人网站注册的时候昵称判重,使用布隆过滤器可以判断某个昵称一定没有被使用过,但会误判某些造成冲突但没有被使用的昵称

2、提高效率。例如客户端查找信息时,先用布隆过滤器筛选一下,如果不在,则直接将未查到的信息反馈给客户端;如果布隆过滤器发现查找信息与位图匹配,则将需要查找的信息推送给服务器中的数据库进行精确查找
【C++】哈希与布隆过滤器,C++修炼内功,c++,哈希算法,开发语言

3、布隆过滤器的删除

单纯的布隆过滤器时不支持删除的,因为一个比特位可能被多个元素所映射。如果非要在布隆过滤器中实现删除,那就只能将位图结构修改未计数器结构。数据set时,每被映射一次,计数器加1,reset时,该位计数器-1,直到该位计数器为0.但是这种操作所需的空间消耗急剧增加。

4、布隆过滤器的优缺点

优点

  1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关

  2. 哈希函数相互之间没有关系,方便硬件并行运算

  3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势

  4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势

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

  6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点

  1. 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中

    (补救方法:再建立一个白名单,存储可能会误判的数据)

  2. 不能获取元素本身

  3. 一般情况下不能从布隆过滤器中删除元素

  4. 如果采用计数方式删除,可能会存在计数回绕问题

5、布隆过滤器面试题

1、给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?

我们可以将它分成100个小文件,使用哈希算法,将ip转换成整型,将它取模, i=HashFunc(ip)%100,i是多少,ip就进入几号小文件。

如果冲突的桶超过1G怎么办?

1、这个桶冲突的IP很多,大多都是不重复的,map统计不下

2、这个桶冲突的IP很多,大多都是重复的,map可以统计

​ 直接使用map中的insert将每一个冲突桶的元素插入到map中。情况一:

如果insert失败,说明空间不足,new节点失败,抛出异常。解决方法是:

换个哈希函数,递归再次对这个桶进行切分。情况二:map可以正常统计

2、给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

精确算法:使用哈希切分,将两个大文件分别切成一个个小文件A0-A99,B0-B99(蛋哥小文件超过1G换一个哈希函数);因为使用的是同一个哈希函数,所以交集必定存在于A0和B0,A1和B1这种相同下标的小文件中。可以先将A0存放至哈希表中,B0去重后与哈希表比对,就能够得到精确交集文章来源地址https://www.toymoban.com/news/detail-713461.html

6、布隆过滤器的实现

#include <iostream>
#include <vector>
#include <bitset>
#include <string>
using namespace std;

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;
	}
};

template<size_t N,
	size_t X = 5,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
	class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;
		/* cout << index1 << endl;
		cout << index2 << endl;
		cout << index3 << endl<<endl;*/
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	bool test(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false)
			return false;
		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false)
			return false;
		size_t index3 = HashFunc3()(key) % len;
		if (_bs.test(index3) == false)
			return false;
		return true;//存在误判的
	}
	// 不支持删除,删除可能会影响其他值。
	void reset(const K& key);
private:
	bitset<X* N> _bs;
};

void test_bloomfilter1()
{
	srand((unsigned int)time(0));
	const size_t N = 100000;
	BloomFilter<N> 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(i));
	}

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

	// v2跟v1是相似字符串集,但是不一样
	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
		url += std::to_string(999999 + 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(i + rand());
		v3.push_back(url);
	}

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

}

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

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

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

相关文章

  • C++:布隆过滤器和哈希切分

    目录 一. 什么是布隆过滤器 二. 布隆过滤器的实现 2.1 数据插入函数set 2.2 判断数据是否存在函数test 2.3 布隆过滤器数据的删除 三. 哈希切分 在我之前的博客C++:使用位图处理海量数据_【Shine】光芒的博客-CSDN博客中,介绍了如何使用位图来处理海量数据,位图的特点为:

    2024年02月09日
    浏览(39)
  • 【C++】哈希位图和布隆过滤器

    哈希位图和布隆过滤器都是常用的概率数据结构,用于高效地判断一个元素是否存在于一个集合当中,但它们在实现方法和各自的优缺点上有所区别。 哈希位图 哈希位图(Hash Bitmap)是由一个位数组构成,每个元素(通常是一个整数)被映射到位数组中的某个位置。对于集合

    2024年02月08日
    浏览(50)
  • C++ 哈希的应用【布隆过滤器】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎃操作环境: Visual Studio 2022 版本 17.6.5 注册账号是进行网络冲浪的第一步操作,而拥有一个具有个性且独一无二的用户昵称是非常重要的,很多人在填写昵称时,常常会看到 此昵称已存在 的提示,系统是如何快速知道当前昵称

    2024年02月14日
    浏览(44)
  • 【C++】哈希应用之布隆过滤器

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.布隆过滤器的提出 2.布隆过滤器的概念 3.布隆过滤器的模拟实现 3.1布隆

    2024年03月27日
    浏览(38)
  • 【C++】哈希的应用——布隆过滤器

    我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的? 用服务器记录了用户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选

    2023年04月22日
    浏览(87)
  • 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日
    浏览(49)
  • [C++]哈希应用之位图&布隆过滤器

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

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

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

    2023年04月09日
    浏览(50)
  • 【数据结构与算法】哈希—— 位图 | 布隆过滤器 | 哈希切割

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希是一种映射思想,这里再讲解两种应用哈希思想的数据结构。 问题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数

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

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

    2024年04月14日
    浏览(61)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包