数据结构 - 位图 | 布隆过滤器

文章目录

    • 一、位图
      • 1、位图概念
      • 2、实现一个简略的位
      • 3、位图的优缺点
      • 4、位图的应用场景
    • 二、布隆过滤器
      • 1、提出
      • 2、概念
      • 3、布隆过滤器的实现
    • 三、海量数据处理
      • 1、哈希切割
      • 2、面试题


一、位图

1、位图概念

位图(Bitmap)是一种非常高效的数据结构,主要用于快速查找、去重、排序等操作,特别是在处理大数据集时非常有用。它通过将数据集合中的每个元素映射到一个二进制位(bit)上来工作,每个位表示集合中是否存在该元素。

2、实现一个简略的位


(1)准备
在这里插入图片描述
(2)将pos值映射的位置置为1
在这里插入图片描述

(3)将pos值映射的位置置为0
在这里插入图片描述
(4)判断pos是否存在
在这里插入图片描述
(5)代码实现

template <size_t N = 10>
class bitset
{public:bitset(){_set.resize((N/32+1), 0);}//pos位置的值是否存在bool test(size_t pos) const{int x = pos / 32;int y = pos % 32;return (_set[x] & (1 << y));}//将pos位置置1bitset& set(size_t pos){int x = pos / 32;int y = pos % 32;_set[x] |= (1 << y);return *this;}//将pos位置置0bitset& reset(size_t pos){int x = pos / 32;int y = pos % 32;_set[x] &= (~(1 << y));return *this;}private:vector<int> _set;
};

(6)测试

void test_bitste()
{bitset<100000> bs;//储存一万个元素int arr[10000] = { 0 };for (int i = 1; i < 10000; i++){arr[i] = rand() % 10000 + i;}//将一万个元素置为1for (auto& e : arr){bs.set(e);}//判断这些元素是否都存在for (auto& e : arr){if (bs.test(e))	cout << "OK" << endl;//出错直接终止程序else assert(false);}//将元素全部删除for (auto& e : arr){bs.reset(e);//如果还存在直接终止程序if (!bs.test(e))	cout << "OK" << endl;else	assert(false);}
}

在这里插入图片描述

3、位图的优缺点

(1)优点

空间效率高:由于每个元素只需要一个bit来表示,因此空间占用非常小。
查询速度快:由于是直接通过索引访问位数组,所以查询某个元素是否存在的时间复杂度为O(1)。

(2)缺点

内存占用:虽然位图的空间效率很高,但当数据集非常大时,位向量可能会占用大量的内存。
元素范围:位图通常适用于元素值为连续整数的情况。如果元素值范围很大但实际值很稀疏,那么位图可能会浪费大量的空间。
扩展性:当元素值范围超出预期时,可能需要重新分配位向量,这可能会导致性能下降。

4、位图的应用场景

快速去重:处理大量数据时,可以快速判断一个数据是否已经出现过。
数据排序:通过位图可以快速统计出每个元素的频率,然后据此进行排序。
数据压缩:对于只有两种状态的数据(如布尔值),使用位图可以极大地减少存储空间。
数据库索引:在数据库中,位图索引用于提高查询效率,特别是当查询条件为“是否包含”时。

二、布隆过滤器

1、提出

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

  1. 用哈希表存储用户记录,缺点:浪费空间
  2. 用位图存储用户记录,缺点:位图一般只能处理整形,如果内容编号是字符串,就无法处理 了。
  3. 将哈希与位图结合,即布隆过滤器

2、概念

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

在这里插入图片描述

3、布隆过滤器的实现

(1)位图设置多大?
布隆过滤器(Bloom Filter)设计中位图(BitMap)的大小设计并不是固定不变的,而是根据具体的应用场景和需求来决定的。

这里假设:插入的元素个数n,哈希函数个数k, 那么我们可以设置位图大小为n*k。

(1)插入
在这里插入图片描述

(2)查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找:分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。
注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可 能存在,因为有些哈希函数存在一定的误判。
比如:在布隆过滤器中查找"alibaba"时,假设3个哈希函数计算的哈希值为:1、7,10刚好和其他元素的比特位重叠,此时布隆过滤器告诉该元素存在,但实该元素是不存在的。

(3)删除
布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。
在这里插入图片描述
但是也可以通过一些办法来实现删除操作:

计数器布隆过滤器(Counting Bloom Filter):
计数器布隆过滤器是对传统布隆过滤器的一种扩展,它将位数组中的每个位扩展为一个小的计数器。当插入元素时,对应的k个计数器(k为哈希函数的数量)增加1;当删除元素时,对应的计数器减少1。这样,即使某个位置被多个元素共享,也能通过减少计数器的值来模拟删除操作。然而,这种方法需要更多的存储空间,并且存在计数回绕(counter overflow)的风险。
使用额外的数据结构:
如果删除操作不是非常频繁,且可以接受一定的性能开销,可以考虑在布隆过滤器之外维护一个额外的数据结构(如哈希表)来记录需要删除的元素。在查询元素时,先检查这个额外的数据结构,如果元素在其中,则认为元素不存在于布隆过滤器中,即使布隆过滤器可能误判其存在。这种方法虽然可以模拟删除操作,但会增加额外的存储和查询开销,并且需要定期清理或同步这两个数据结构以保持一致性。
重新构建布隆过滤器:
对于需要频繁删除操作的应用场景,如果元素的数量不是非常大,可以考虑在删除操作较多时重新构建布隆过滤器。即,将当前所有需要保留的元素重新插入到一个新的布隆过滤器中,并丢弃旧的布隆过滤器。这种方法可以彻底清除不再需要的元素,但需要重新计算哈希值和构建位数组,可能会带来较大的性能开销。

(4)简略实现

//哈希函数
struct BKDRHash
{size_t operator()(const string& s){// BKDRsize_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 K = 3,class V = string,class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash>
class BloomFilter
{
public://置为1void set(const V& s){//求出哈希值int hash1 = HashFunc1()(s) % (N * K);int hash2 = HashFunc2()(s) % (N * K);int hash3 = HashFunc3()(s) % (N * K);//将哈希值的映射位置置为1_set.set(hash1);_set.set(hash2);_set.set(hash3);}//是否存在bool test(const  V& s){//求出哈希值int hash1 = HashFunc1()(s) % (N * K);int hash2 = HashFunc2()(s) % (N * K);int hash3 = HashFunc3()(s) % (N * K);//只要有一个不存在就判断为不存在  -- 可能存在误判return _set.test(hash1) && _set.test(hash2) && _set.test(hash3);}private://位图bitset<N* K> _set;
};

(5)优缺点

优点

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

缺点

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

(6)使用场景

  1. 缓存穿透保护 在使用Redis等缓存系统时,用户可能查询大量不在缓存中的数据,导致这些请求直接穿透到数据库,给数据库造成巨大压力。布隆过滤器可以用于提前判断一个元素是否存在于缓存中,如果不存在,则直接返回,避免了对数据库的无效查询。这种方式可以显著降低数据库的访问压力,保护系统免受缓存穿透的影响。

  2. 网页爬虫URL去重 在爬虫系统中,为了避免重复爬取相同的URL地址,通常会使用集合(如HashSet)来存储已经爬取过的URL。然而,当URL数量非常庞大时,集合会占用大量的内存空间。布隆过滤器提供了一种更为节省空间的方法,它允许爬虫系统以较低的误判率快速判断一个URL是否已经被爬取过,从而避免了不必要的重复爬取。

  3. 反垃圾邮件 在反垃圾邮件系统中,布隆过滤器可以用于判断一个邮箱地址是否存在于垃圾邮件列表中。由于垃圾邮件列表可能包含数亿个邮箱地址,使用传统的数据结构会占用大量的内存和存储空间。而布隆过滤器通过其高效的插入和查询性能,可以在较低误判率的前提下,实现对垃圾邮件列表的快速检索。

  4. 数据库查询优化 在数据库查询中,布隆过滤器可以用于过滤掉大量不存在的数据行,从而减少对磁盘的访问次数,提高查询效率。例如,在NoSQL数据库中,可以使用布隆过滤器在内存中快速判断某个row是否存在于数据库中,如果不存在,则无需进一步访问磁盘进行查询。

  5. 网络安全 在网络安全领域,布隆过滤器可以用于识别恶意IP地址、URL等。通过将已知的恶意实体加入到布隆过滤器中,系统可以快速判断一个请求是否来自恶意实体,从而采取相应的安全措施。

  6. 推荐系统 在推荐系统中,布隆过滤器可以用于过滤掉用户已经阅读或观看过的内容,确保推荐的内容是新颖的。虽然布隆过滤器存在一定的误判率,但在大多数情况下,这种误判是可以接受的,因为它能够显著降低系统的计算复杂度和存储需求。

  7. 消息队列去重 在消息队列中,为了防止消息重复消费,可以使用布隆过滤器对消息的key进行去重。当消息发送时,将消息的key加入到布隆过滤器中;当消息消费时,先检查消息的key是否存在于布隆过滤器中,如果存在,则认为是重复消息,进行相应处理。

三、海量数据处理

1、哈希切割

哈希切割通过哈希函数将大数据集中的每个元素映射到一个较小的、有限的值域范围内,通常是整数集合。这个映射过程可以使得具有相同哈希值的元素被分配到同一个集合或文件中,所以相同的元素一定会被分到一组,而不同哈希值的元素则被分配到不同的集合或文件中,。由于哈希函数的性质,不同的输入可能产生相同的输出(即哈希冲突),但在实际应用中,这种冲突可以通过合理设计哈希函数和分配策略来减少其影响。如:有100g储存ip地址的文件,我们只有1个g的内存,此时我们需要用哈希函数将大文件分割为500个小文件,再进行处理。

在这里插入图片描述

2、面试题

(1)给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?
与上题条件相同,如何找到top K的IP?
在这里插入图片描述
(2)1. 给定100亿个整数,设计算法找到只出现一次的整数?
在这里插入图片描述
(3)给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
在这里插入图片描述
(4) 位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数。
在这里插入图片描述
(5) 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL基础练习题38-每位教师所教授的科目种类的数量

目录 题目 准备数据 分析数据 总结 题目 查询每位老师在大学里教授的科目种类的数量。 准备数据 ## 创建库 create database db; use db;## 创建表 Create table If Not Exists Teacher (teacher_id int, subject_id int, dept_id int)## 向表中插入数据 Truncate table…

[Megagon Labs] Annotating Columns with Pre-trained Language Models

Annotating Columns with Pre-trained Language Models 任务定义 输入&#xff1a;一张数据表&#xff0c;但没有表头&#xff0c;只有表中的数据。 输出&#xff1a;每一列数据的数据类型&#xff0c;以及两列数据之间的关系。 数据类型和数据关系都是由训练数据决定的固定…

自建Gitlab和Gitlab runner并推送镜像到Harbor

1. 创建虚拟机 整体规划如下 1.1 创建3台虚拟机 系统版本Centos7.9 设置IP分别为 192.168.200.201 、192.168.200.202、 192.168.200.203 1.2 安装docker 3台虚拟机都安装docker&#xff0c;参考文章 安装docker 1.3 修改daemon.json 修改 /etc/docker/daemon.json 文件…

开源异构数据库同步工具DBSyncer

DBSyncer是一款开源的数据同步中间件&#xff0c;它提供了多种数据库和数据源之间的同步解决方案&#xff0c;包括MySQL、Oracle、SqlServer、PostgreSQL、Elasticsearch(ES)、Kafka、File、SQL等同步场景。 以下是对DBSyncer的详细介绍&#xff1a; 一、主要功能与特点 多种…

业界首个OpenTelemetry结合eBPF的向导式可观测性平台APO正式开源

AutoPilot Observability (简称APO&#xff09;是什么&#xff1f; 开箱即用的可观测性平台&#xff1a;APO 致力于提供一键安装、开箱即用的可观测性平台。APO 的 OneAgent 支持一键免配置安装 Tracing 探针&#xff0c;支持采集应用的故障现场日志、基础设施指标、应用和下游…

Unity物理模块 之 ​2D碰撞器

本文仅作笔记学习和分享&#xff0c;不用做任何商业用途 本文包括但不限于unity官方手册&#xff0c;unity唐老狮等教程知识&#xff0c;如有不足还请斧正 1.碰撞器是什么 在 Unity 中&#xff0c;碰撞器&#xff08;Collider&#xff09;是一种组件&#xff0c;用于检测物体之…

P37-数据存储

数据类型介绍 前面学习了基本的内置类型&#xff1a; 以及它们所占存储空间的大小。 类型的意义&#xff1a; 1.使用这些类型开辟空间的大小&#xff08;大小决定了使用范围&#xff09; 2.如何看带内存空间的视角 类型的基本归类 整形家族 之所以char也分类在其中是因为实…

【图形验证和AI智能及CHATGPT对抗影响的是用户体验】

验证码本质上自带一层答案的语义&#xff0c;这原本是天然的区分人和自动程序的地方&#xff0c;但在今日却未必&#xff0c;由于AI智能及CHATGPT的发展机器要识别也变得容易。 一 &#xff1a;攻防思路 黑产对于验证码图片答案的获取主要有两种手段——图片穷举破解和图片模…

ComfyUI - 在服务器中部署 AIGC 绘画的 ComfyUI 工具 教程

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/141140498 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 ComfyU…

分布式知识总结(基本概念)

文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 基本概念 吞吐量 指系统在单位时间能够处理多少个请求 QPS 每秒…

Android 13 GMS 内置壁纸

如图&#xff0c;原生系统上&#xff0c;设备上的壁纸 显示系统内置壁纸。如果没有添加内置壁纸&#xff0c;就显示默认的壁纸。点击进去就是预览页面 扩展下&#xff0c;默认壁纸在 frameworks/base/core/res/res/drawable-sw720dp-nodpi/default_wallpaper.png frameworks/b…

vue3中ref、reactive的理解

本文主要介绍了vue3中ref、reactive的使用。文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧。 在讲解这两个api工具之前&#xff0c;我们得先了解下watch和watchEffect这两个函数的使用方法和它…

通过es+ Kibana+ LogStash收集日志

架构 服务产生的日志&#xff0c;通过logstash收集到es中&#xff0c;并通过kibana展示出来&#xff0c;这里不再介绍三者的作用 部署esKibana 这三个的版本尽量要保持一致&#xff0c;我使用的是7.13.4 通过docker部署es 命令&#xff1a; docker run --name elasticsea…

2024.8.12(LVS)

一、LVS 1、描述以及工作原理 1. 什么是LVS linux virtural server的简称,也就是linxu虚拟机服务器,这是一个由章文嵩博士发起的开源项目,官网是http://www.linuxvirtualserver.org,现在lvs已经是linux内核标准的一部分,使用lvs可以达到的技术目标是:通过linux达到负载均衡技…

C#压缩和解压文件

这里用两种方法实现C#压缩和解压文件 1、使用System.IO.Compression名称空间下的相关类(需引用 System.IO.Compression.FileSystem和System.IO.Compression程序集) 创建zip压缩文件 使用ZipFile类CreateFromDirectory()方法来创建zip压缩文件。它有3种重载形式&#xff0c;这…

【Java数据结构】---Queue

乐观学习&#xff0c;乐观生活&#xff0c;才能不断前进啊&#xff01;&#xff01;&#xff01; 我的主页&#xff1a;optimistic_chen 我的专栏&#xff1a;c语言 &#xff0c;Java 欢迎大家访问~ 创作不易&#xff0c;大佬们点赞鼓励下吧~ 文章目录 前言队列Queue队列的模拟…

机器学习——第十一章 特征选择与稀疏学习

11.1 子集搜索与评价 对一个学习任务来说&#xff0c;给定属性集&#xff0c;其中有些属性可能很关键、很有用&#xff0c;另一些属性则可能没什么用.我们将属性称为"特征" (feature) &#xff0c;对当前学习任务有用的属性称为"相关特征" (relevant featu…

World of Warcraft [CLASSIC] 80 WLK [Gundrak] BUG

World of Warcraft [CLASSIC] 80 WLK [Gundrak] BUG 魔兽世界怀旧版&#xff0c;80级&#xff0c;5人副本古达克&#xff0c;科技队伍&#xff08;BUG队伍&#xff09; 副本有两个门口 这样看&#xff0c;是不是觉得很怪。是的&#xff0c;和图1刚好相反的。 因此应该翻转180…

Ubuntu视频工具

1. VLC VLC Media Player&#xff08;VLC多媒体播放器&#xff09;&#xff0c;最初命名为VideoLAN客户端&#xff0c;是VideoLAN品牌产品&#xff0c;是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式&#xff0c;并支持DVD影音光盘&#xff0c;VCD影音光…

《学会 SpringBoot · 优雅停机方案》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…