当前位置: 首页 > news >正文

哈希表应用(位图和布隆过滤器)

目录

1.位图

1.1 位图概念

1.2 位图的应用

1.3 位图的实现     

1.4 完整代码

2. 布隆过滤器

2.1 布隆过滤器的概念

2.2 布隆过滤器的优缺点

  2.3 实现

2.4 完整代码

1.位图

1.1 位图概念

       位图,是用比特位来表示某种状态。一个位有两种状态0和1,0可以表示一种状态,1可以表示一种状态。通常是用来判断某个数据存不存在。比如:判断一个数据是否保存,可以用一个位图来表示,数据对应位为1表示保存了,对应位为0表示未保存。如果想知道某个数是否存在,直接找该数对应位的状态即可。

       注意:位图没有保存数据,而是保存的状态。

1.2 位图的应用

位图适用于海量数据,和数据无重复的情况。因为用的是比特位,占据空间会比较小。

  1. 快速查找某个数据是否在集合中
  2. 排序+去重。
  3. 求两个集合的交集,并集等
  4. 操作系统中的磁盘标记

优点:空间小

确定:只能处理整形

1.3 位图的实现     

我们用一个数组来保存整形,一个整形4个字节。一个字节8位。所以数组一个元素占32位。

查找数据对应位

 保存数据将某一位置1,删除数据将某一位置0。查找数据有保存。都需要查找数对应的位。如何查找呢?

        1.先找到数据在数组中保存在哪个下标。

        2.再找到数据在该下标的哪一位。

//找到这数在第几个整形里
int i = N / 32;//找到这个数在这个整形的第几位
int j = N % 32;

将某一位置记为1

可以使用按位或操作'|'。按位或,有1为1,全0为0。

这样就需要得到一个相应为为1,其它位为0的数。可以使用移位操作,将1左移pos位。

将数组当前元素按位或上1左移pos位,就将相应位置1了。

//找到这个数的比特位,将其变为1void set(size_t N){//找到这数在第几个整形里int i = N / 32;//找到这个数在这个整形的第几位int j = N % 32;//"或",有1为1,将该比特位变为1_a[i] |= (1 << j);}

将某一位置记为0

 可以使用按位与操作'&'。按位与,全1为1,有0为0。

这样就需要得到一个相应为为0,其它位为1的数。可以使用移位操作,将1左移pos位,然后按位取反。将数组当前元素按位与上这个数,就将相应位置1了。

//找到这个数的比特位,将其变为0
void retset(size_t N)
{//找到这数在第几个整形里int i = N / 32;//找到这个数在这个整形的第几位int j = N % 32;//"与",有0为0,将该比特位变为0_a[i] &= (~(1 << j));
}

检查该位置是否为1

可以使用按位&,用对应位为1,其它位为0与上数组元素

 按位或不行,用对应位为0,其它位为1。会改变其它位的状态。

//检查该位置是否为1
bool test(size_t N)
{int i = N / 32;int j = N % 32;//"与",右0为0,如果该位置为1时,则该整形不为空,返回真//如果该位置为0时,则该整形为空,返回假return _a[i] & (1 << j);
}

1.4 完整代码

#pragma once
#include<vector>
#include<iostream>
using namespace std;namespace CH1
{//N代表多少比特位template<size_t N>class bitset{public:bitset(){_a.resize(N / 32 + 1);//开空间}//找到这个数的比特位,将其变为1void set(size_t N){//找到这数在第几个整形里int i = N / 32;//找到这个数在这个整形的第几位int j = N % 32;//"或",有1为1,将该比特位变为1_a[i] |= (1 << j);}//找到这个数的比特位,将其变为0void retset(size_t N){//找到这数在第几个整形里int i = N / 32;//找到这个数在这个整形的第几位int j = N % 32;//"与",有0为0,将该比特位变为0_a[i] &= (~(1 << j));}//检查该位置是否为1bool test(size_t N){int i = N / 32;int j = N % 32;//"与",右0为0,如果该位置为1时,则该整形不为空,返回真//如果该位置为0时,则该整形为空,返回假return _a[i] & (1 << j);}private:vector<int> _a;};
}

2. 布隆过滤器

2.1 布隆过滤器的概念

       由上我们知道位图的缺点是只能记录是否保存整数数据,布隆过滤器则是针对这一缺点,还可以记录除整数以外的其它类型的数据。

       布隆过滤器底层是通过位图实现的,通过哈希函数将其它类型转化成整形。但是这样会有一个缺点,可能不同的数据可能会通过哈希函数转化成相同的值。比如:string类型的"abcd"和"aadd"哈希函数是将所有字符ASCII码值加起来,这两个字符串就会得到相同的值。

       这样就会导致误判,已经保存了的数据一定不会再保存。但是,没有保存的数据,通过哈希函数求出来的值与其中一个已经保存的值的整形值一样时,也不会保存了。

        这种误判并不能得到实质性的解决,但是可以通过一些方法来降低误判。

        布隆过滤器是通过,将需要保存的值通过多个哈希函数,得到多个值,将位图中的多个位置置1。将测在不在时,需要检测所有的位置是否为1。

比如:

2.2 布隆过滤器的优缺点

优点:

  • 增加和查询元素时间复杂度为O(K),(K为哈希函数的个数,一般比较小),与数据量无关。
  • 哈希函数之间没有关系,方便硬件并行计算。
  • 布隆过滤器不需要保存函数本身,在某些保密要求严格的场合由很大优势。
  • 节省空间,高效

缺点:

  • 存在误判,不支持删除。

  2.3 实现

  • 布隆过滤器时参数
bitset _bloom;//位图
size_t _count = 0;//数据个数
  • 布隆过滤器时初始化
bloomfilter(size_t num)//这个是开辟的空间的大小————单位比特:_bloom(num * 5)//长度太小起不到过滤作用,也不能太大,研究出来乘5最好, _count(0)
{}

        位图为的个数可以通过数据的个数来确定,通过上面我们知道,一个数据对应多个位,如果布隆过滤器的位图的位数正好是数据的个数,很快,布隆过滤器就满了。数据不好保存,起不到过滤的作用。但是位数太大,空间有太大。于是有人研究出来,一般位数开辟元素个数的5倍最好。

  • 布隆过滤器的插入

插入通过哈希函数转化成整形后,在位图中,将对应位置1。

void insert(const K& num)
{//先转成整形int index1 = KToInt1()(num) % _bloom.bitcount();//余上所有位数,防止越界std::cout << index1 << std::endl;int index2 = KToInt2()(num) % _bloom.bitcount();std::cout << index2 << std::endl;int index3 = KToInt3()(num) % _bloom.bitcount();std::cout << index3 << std::endl;//将对应位置1_bloom.set(index1);_bloom.set(index2);_bloom.set(index3);
}
  • 布隆过滤器的查找

查找通过哈希函数转化成整形后,在位图中,检测每一位是否为1,有一位不为1,则不存在。

	//只要有一位为0,就不存在bool IsBloomFilter(const K& num){int index1 = KToInt1()(num) % _bloom.bitcount();//余上所有位数,防止越界if (!_bloom.test(index1)){return false;}int index2 = KToInt2()(num) % _bloom.bitcount();if (!_bloom.test(index2)){return false;}int index3 = KToInt3()(num) % _bloom.bitcount();if (!_bloom.test(index3)){return false;}return true;}
  • 布隆过滤器的删除

       布隆过滤器不支持删除,因为不同的数据,可能通过多个哈希函数,在多个位上置1。但是可能不同数据,通过不同哈希函数的多个位有相同的位置。

比如:

      如果删除了abcd,对应位图2位置会被置0,相应aadd会被检测为不存在,实际时存在的。所以不能有删除操作。

 注意:布隆过滤器是通过多个哈希函数将多个位置1,来降低误判,并没有解决误判。

2.4 完整代码

#pragma once
//布隆过滤器是用位图实现的
#include"bitset.h"
#include<string>template<class T>
struct KeyToInt1{T& operator()(const T& k){return k;}
};template<>
struct KeyToInt1<std::string>
{size_t operator()(const std::string& s){if (s.size() == 0){return 0;}size_t hash = 0;for (size_t i = 0; i < s.size(); i++){hash *= 131;hash += s[i];}return hash;}
};template<class T>
struct KeyToInt2{T& operator()(const T& k){return k;}
};template<>
struct KeyToInt2<std::string>
{size_t operator()(const std::string& s){if (s.size() == 0){return 0;}size_t hash = 0;for (size_t i = 0; i < s.size(); i++){hash *= 65599;hash += s[i] ;}return hash;}
};template<class T>
struct KeyToInt3{T& operator()(const T& k){return k;}
};template<>
struct KeyToInt3<std::string>
{size_t operator()(const std::string& s){if (s.size() == 0){return 0;}int magic = 63689;size_t hash = 0;for (size_t i = 0; i < s.size(); i++){hash *= magic;hash += s[i];magic *= 378551;}return hash;}
};//KToInt是K类型转化成int,多个函数,将一个数据转成多个整形,多个位保存一个数据的状态
template<class K, class KToInt1 = KeyToInt1<K>, class KToInt2 = KeyToInt2<K>, class KToInt3 = KeyToInt3<K>>
class bloomfilter{
public:bloomfilter(size_t num):_bloom(num * 5)//长度太小起不到过滤作用,也不能太大,研究出来乘5最好, _count(0){}void insert(const K& num){//先转成整形int index1 = KToInt1()(num) % _bloom.bitcount();//余上所有位数,防止越界std::cout << index1 << std::endl;int index2 = KToInt2()(num) % _bloom.bitcount();std::cout << index2 << std::endl;int index3 = KToInt3()(num) % _bloom.bitcount();std::cout << index3 << std::endl;//将对应位置1_bloom.set(index1);_bloom.set(index2);_bloom.set(index3);}//只要有一位为0,就不存在bool IsBloomFilter(const K& num){int index1 = KToInt1()(num) % _bloom.bitcount();//余上所有位数,防止越界if (!_bloom.test(index1)){return false;}int index2 = KToInt2()(num) % _bloom.bitcount();if (!_bloom.test(index2)){return false;}int index3 = KToInt3()(num) % _bloom.bitcount();if (!_bloom.test(index3)){return false;}return true;}private:bitset _bloom;size_t _count = 0;//数据个数
};


http://www.mrgr.cn/news/62642.html

相关文章:

  • AI赛道盈利模式揭秘——以AIStarter为例【AI数字人、大模型、工作流...】
  • 制作安装k8s需要的离线yum源
  • pdfkit | 利用python实现html文件转pdf
  • 2024 Rust现代实用教程 流程控制与函数
  • mongodb指定引擎并设置内存使用大小
  • 服务器宝塔安装哪吒监控
  • HTB-Cicada 靶机笔记
  • ETL处理全流程
  • Linux 命令解释器-shell
  • stm32入门教程--USART外设 超详细!!!
  • Linux:线程池
  • qt QSlider详解
  • 软设每日打卡——折半查找二叉判定树、平衡二叉树
  • 多线程案例---单例模式
  • 2024年NSSCTF秋季招新赛-WEB
  • Convolution 卷积
  • 前端笔面试查漏补缺
  • 鸿蒙系统:核心特性、发展历程与面临的机遇与挑战
  • JSP水果商城管理系统WEB项目
  • Vue中path和component属性
  • 宠物空气净化器是否有用?五大高性价比宠物空气净化器种草推荐
  • 前端如何安全存储密钥,防止信息泄露
  • 高级SQL技巧:优化查询与提升性能(附11个示例代码)
  • #HarmonyOS:名词
  • Leetcode 198. 打家劫舍 动态规划
  • 拆分PPOCRLabel标注的数据集并生成识别数据集