C++:Hash应用【位图与布隆过滤器】

什么是位图?

我们先来看一个问题:
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在
这40亿个数中。【腾讯】
如果我们使用unordered_set容器来解决,40亿个数据,每个数据占4个字节,那么一共需要16G内存,对于内存消耗太大了,而如果存储的不是整形数据,那么只会消耗更大。

这个时候我们可以引出位图,每个整数是否存在可以使用一个对应比特位的0或者1来表示,这样原来32位才能表示一个数,现在只需要1位就可以解决,40亿个数据只需要0.5G。

位图:

位图是一种用于表示集合的数据结构,通常用一个二进制数组来表示。每个元素在位图中对应于数组中的一个位(bit),位图中的每一位表示集合中的一个元素是否存在。
位图通常用于处理大量的布尔型数据,例如标记某些元素是否出现过,或者记录某些状态的信息。由于位图中的每一位只占用一个比特(bit),因此它可以非常紧凑地表示大量的信息。
位图在存储和检索方面的效率都非常高,但是它的缺点是无法直接支持范围查询,只能用于表示离散的集合。

位图的模拟实现

我们先来看一下库中实现的位图
在这里插入图片描述
我们接下来主要实现位图中三个主要的功能函数

1.set
将一个数据放入位图
2.reset
将一个数据移出位图
3.test
检测一个数据在不在位图中
在这里插入图片描述
如上图所示,假如以一个字节为单位,那么which/8就是在第几块中,which%8就是在第几块的第几位。改变对应比特位上的0或1就可以表示该元素是否存在。

模拟实现代码


```cpp
#pragma once
template<size_t N>
class bitset
{
public:
	bitset(size_t bitcount=N)
		:_bits((bitcount>>5)+1,0)  //为vector数组开辟大小初始化
	{
	}

	void set(size_t which)
	{
		if (which > N)
			return;
		size_t i = which >> 5;
		size_t pos = which % 32;
		_bits[i] |= (1 << pos);//将对应的比特位置为1
	}
	void reset(size_t which)
	{
		if (which > N)
			return;
		size_t i = which >> 5;
		size_t pos = which % 32;
		_bits[i] &= ~(1 << pos);//将对应的比特位置为0
	}

	bool test(size_t which)
	{
		if (which > N)
			return false;
		size_t i = which >> 5;
		size_t pos = which % 32;
		return _bits[i] & (1 << pos);//如果不存在则结果为0,如果存在则非0
	}
private:
	vector<int> _bits;
};

``

布隆过滤器

  1. 用哈希表存储用户记录,缺点:浪费空间
  2. 用位图存储用户记录,缺点:位图一般只能处理整形,如果内容编号是字符串,就无法处理了。
  3. 将哈希与位图结合,即布隆过滤器 布隆过滤器(Bloom Filter)是一种数据结构,用于判断一个元素是否可能存在于一个集合中。它通过利用一系列哈希函数和一个位数组来实现快速的成员存在查询。

具体来说,布隆过滤器通常包含以下几个要素:

一个位数组(通常用0和1表示),长度为m,初始化时所有位都被置为0。
一组哈希函数,用于将元素映射到位数组的不同位置。

在将一个元素加入布隆过滤器时,该元素会经过多个哈希函数的映射,对应的位数组位置被置为1。在查询一个元素是否存在于布隆过滤器时,同样进行多次哈希映射,若所有映射对应的位都为1,则说明该元素可能存在于集合中,若存在任何一个位为0,则可以确定该元素不存在于集合中。
在这里插入图片描述
如上图所示,假设有三个哈希函数,映射出三个比特位 ,孙悟空与孙行者各自对应三个,而这些比特位有可能重合,所以比特位为1不一定在,而比特位为0一定不在。

也就是说,如果该元素映射的所有位都为1,则该元素不一定在;
如果所有映射位中有一个为0,则该元素一定不在。

布隆过滤器的模拟实现

首先我们先来选择几个哈希映射函数:

//三个不同的将字符串映射成整数的函数
struct HashBKDR
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}
		return val;
	}
};
struct HashAP
{
	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
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
			hash += (hash << 5) + ch;
		return hash;
	}
};

布隆过滤器模拟实现
布隆过滤器的实现还是基于位图实现的,不过是把字符串映射为size_t的key值。

template<size_t N,class K=string,class Hash1=HashAP,class Hash2=HashBKDR,class Hash3=HashDJB>
class bloomfilter
{
public:
	void set(const K& str)
	{
		size_t hash1 = Hash1()(str) % (_ratio * N);
		_bits->set(hash1);
		size_t hash2 = Hash2()(str) % (_ratio * N);
		_bits->set(hash2);
		size_t hash3 = Hash3()(str) % (_ratio * N);
		_bits->set(hash3);
	}

	//支持删除可能会删除其他值
	/*void reset(const K& str)
	{
		size_t hash1 = Hash1(str) % (_ratio * N);
		_bits->reset(hash1);
		size_t hash2 = Hash2(str) % (_ratio * N);
		_bits->reset(hash2);
		size_t hash3 = Hash3(str) % (_ratio * N);
		_bits->reset(hash3);
	}*/

	bool test(const K& str)
	{
		size_t hash1 = Hash1()(str) % (_ratio * N);
		if (!_bits->test(hash1))
		{
			return false;
		}
		size_t hash2 = Hash2()(str) % (_ratio * N);
		if (!_bits->test(hash2))
		{
			return false;
		}
		size_t hash3 = Hash3()(str) % (_ratio * N);
		if (!_bits->test(hash3))
		{
			return false;
		}
		return true;
	}


private:
	const static size_t _ratio = 5;//空间开的越大,误判率越小
	wjc::bitset<_ratio*N>* _bits=new wjc::bitset<_ratio*N>;
};

以上就是布隆过滤器的模拟实现
布隆过滤器的优点在于其空间效率和查询速度都很高,但缺点是可能存在误判,即布隆过滤器判断某个元素存在于集合中,但实际上并不存在(false positive)。这种误判的概率可以通过合适选择位数组长度和哈希函数数量来控制。

布隆过滤器可以从以下几个方面优化

1.选择合适的哈希函数:
哈希函数的选择对布隆过滤器的性能影响很大。理想的哈希函数应该具有良好的均匀性,能够将元素均匀地映射到位数组的各个位置,从而降低碰撞的概率。常见的哈希函数包括MurmurHash、MD5和SHA等。

2.适当调整位数组长度: 增加位数组的长度可以降低误判率,但也会增加内存消耗。根据误判率的要求和可用内存的限制,选择适当的位数组长度。

3.增加哈希函数数量:
使用多个独立的哈希函数可以减少冲突的概率,进而降低误判率。但增加哈希函数数量也会增加计算成本。通常情况下,选择适量的哈希函数数量以在减少误判的同时保持较低的计算成本。

4.监控和调整误判率: 在实际应用中,可以通过监控布隆过滤器的误判率来评估其性能,并根据需要调整位数组长度和哈希函数数量以达到最优性能。

5.考虑动态调整: 在一些场景中,集合的特征可能随时间变化,可以考虑动态地调整布隆过滤器的参数,以适应集合的变化。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547769.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

FastGPT+ChatGLM3本地部署

FastGPTChatGLM本地部署 本地部署硬性要求&#xff1a;显存13g以上 关于环境的安装就不多赘述&#xff0c;conda pip 可以解决大部分问题 ChatGLM本地运行 m3e-basechatglm3-6b 在huggingface上可以下载上述模型&#xff0c;如果没有梯子可以使用huggingface镜像 从git…

OpenHarmony轻量系统开发【8】其它驱动开发示例

8.1代码示例 OpenHarmony代码中&#xff0c;Hi3861提供了绝大部分的驱动示例代码&#xff0c;文件路径&#xff1a; device\soc\hisilicon\hi3861v100\sdk_liteos\app\demo\src 开发者可以参考&#xff0c;文件如下&#xff1a; 8.2如何使用 &#xff08;1&#xff09;创建文…

springMVC理解

springMVC是一种思想&#xff0c;将软件划分为&#xff0c;模型Model&#xff0c;视图View&#xff0c;控制器Controller。 MVC的工作原理&#xff1a;用户通过前端视图页面&#xff0c;发送请求到服务器&#xff0c;在服务器中请求被Controller接收&#xff0c;Controller调用…

科技助力上亿用户隐私安全保护,合合信息两款产品再获CCIA PIA星级标识

随着互联网技术的飞速发展&#xff0c;个人信息的收集、存储、使用和传输变得日益频繁&#xff0c;其泄露和滥用的风险也随之增加&#xff0c;个人信息保护已成为社会共同关注的热点议题。近期&#xff0c;“中国网络安全产业联盟&#xff08;CCIA&#xff09;数据安全工作委员…

2024/4/15 网络编程day3

一、TCP机械臂测试 通过w(红色臂角度增大)s&#xff08;红色臂角度减小&#xff09;d&#xff08;蓝色臂角度增大&#xff09;a&#xff08;蓝色臂角度减小&#xff09;按键控制机械臂 注意&#xff1a;关闭计算机的杀毒软件&#xff0c;电脑管家&#xff0c;防火墙 1&#…

居中问题:line-height、基线

html5CSS3的居中专题 完整链接&#xff1a; https://pan.baidu.com/s/16IhFoBC2gNPZwosyS6UXxQ 密码: ft2j –来自百度网盘超级会员V7的分享 居中问题 a. 行内元素 水平居中&#xff1a;父标签设置text-align:center&#xff0c; 垂直居中&#xff1a;父标签设置line-heigh…

电脑技巧:Bandicam班迪录屏介绍

目录 一、 软件简介 二、软件功能 2.1 屏幕录制 2.2 游戏录制 2.3 设备录制 2.4实时编辑与截图 2.5 轻量级软件 三、软件用途 3.1 教育培训 3.2 游戏直播与分享 3.3 企业办公 3.4 在线教学与知识分享 四、总结 今天给大家推荐一款非常实用的电脑录屏软件&#xf…

深入浅出学习切片LOD——ArcGIS server模拟缓存切片(影像快显)

一、第一次实践 原理 免切片实现影像服务的模拟切片&#xff0c;主要原理是接收前端传过来的xyz(行列层级)以及切片方案&#xff0c;计算出该请求的切片的四至经纬度信息&#xff0c;通过mapserver的exportImage接口&#xff0c;传入每个模拟切片的四至经纬度信息得到图片返回…

nginxWebUI配置conf

在左边相应位置写入要修改的语句后&#xff0c;依次点击“校验文件”、“替换文件”、“重新装载”即可重启conf

柴油发电机负载原理是怎样的

柴油发电机负载原理是指当发电机在运行过程中&#xff0c;通过外部负载设备&#xff08;如电动机、照明设备等&#xff09;从发电机输出电能&#xff0c;从而使发电机内部的转子产生旋转磁场&#xff0c;进而驱动发电机的定子绕组产生交流电压的过程。这个过程涉及到发电机的工…

Leetcode - 128双周赛

目录 一&#xff0c;3110. 字符串的分数 二&#xff0c;3111. 覆盖所有点的最少矩形数目 三&#xff0c;3112. 访问消失节点的最少时间​编辑 写法一&#xff1a;朴素 Dijkstra&#xff08;适用于稠密图&#xff0c;即边比较多的图&#xff09; 写法二&#xff1a;堆优化 …

海思Hi3519 DV500 部署yolov5并加速优化

本项目代码已开源&#xff0c;见文末 导出onnx模型 yolov5官方地址 利用官方命令导出python export.py --weights yolov5n.pt --include onnx 或者自写代码导出 import os import sys os.chdir(sys.path[0]) import onnx import torch sys.path.append(..) from models.co…

Maui 显示当前时间

1、MainPage.xaml.cs 代码 using System.Threading;namespace Mauitime {public partial class MainPage : ContentPage{private Timer _timer;public MainPage(){InitializeComponent();_timer new Timer(_ > UpdateCurrentTime(), null, 0, 1000);}// 在页面显示时更新当…

CMC学习系列 (10):CMC计算方法介绍

CMC计算方法介绍 0. 引言1. 主要贡献2. 方法2.1 普通CMC2.2 小波CMC2.3 其余方法2.4 预处理增强型CMC 3. 总结欢迎来稿 论文地址&#xff1a;https://www.frontiersin.org/articles/10.3389/fnhum.2019.00100/full 论文题目&#xff1a;Corticomuscular Coherence and Its Appl…

基于springboot的高校教师教学质量评价系统

基于springboot的高校教师教学质量评价系统 前言 随着社会的发展&#xff0c;高校教师教学质量评价系统的管理形势越来越严峻。越来越多的用户利用互联网获得信息&#xff0c;但高校教师教学质量评价系统信息鱼龙混杂&#xff0c;信息真假难以辨别。为了方便用户更好的获得高…

2.SG90舵机模块

当我们输出一段脉冲信号的时候就可以调节舵机的角度 我们可以从原理图可以看到舵机的脚在PA6 从芯片手册我们又可以看到PA6对应TIM3_CH1,并且不用开启部分重映像就能使用 新建Servo.c存放PWM初始化 配置PWM void Servo_TIM3_Init(u16 arr,u16 psc) {//开启TIM3的时钟RCC_APB1…

Docker部署SpringBoot服务(Jar包映射部署)

介绍 项目在docker部署运行以后&#xff0c;每次需更新jar包时&#xff0c;都得重新制作镜像&#xff0c;再重新制作容器。流程及其繁琐&#xff0c;效率极低。 以下步骤是在不更新镜像和容器的前提下&#xff0c;直接更新jar完成项目更新的操作。 不重新制作镜像部署 1. 创…

基于单片机的智能模拟路灯控制系统

摘 要: 随着电力资源的紧缺,以及光污染和雾霾天气的影响,更智能化的路灯设计对人们的日常生活意义重大。本文的智能路灯控制系统是基于单片机的控制器,通过介绍该系统相应的硬件设计和软件设计,实现定时开关和依具体情况是否需要来开关路灯和进行亮度调节,并且具有自检功能…

CESS 受邀出席香港Web3.0标准化协会第一次理事会议,共商行业未来

2024 年 4 月 5 日&#xff0c;CESS&#xff08;Cumulus Encrypted Storage System&#xff09;作为香港 Web3.0 标准化协会的副理事会成员&#xff0c;于香港出席了 2024 年度第一次理事会会议。此次会议汇聚了来自不同领域的知名企业和专家&#xff08;参会代表名单见文末&am…

PaddleOCR训练自己模型(1)----数据准备

一、下载地址&#xff1a; PaddleOCR开源代码&#xff08;下载的是2.6RC版本的&#xff0c;可以根据自己需求下载&#xff09; 具体环境安装就不详细介绍了&#xff0c; 挺简单的&#xff0c;也挺多教程的。 二、数据集准备及制作 &#xff08;1&#xff09;下载完代码及配置…