布隆过滤器

news/2024/10/30 21:21:51/

1.概念

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

2.演示一下布隆过滤器的插入 

 插入baidu

 

插入tenxun

 

3.具体实现 

package test;import java.util.BitSet;class Hash {public int cap;//容量public int seed;//种子public Hash(int cap, int seed) {this.cap = cap;this.seed = seed;}//把当前字符串变成一个hash值public int hash(String key) {int h;return (key == null) ? 0 : (seed * (cap - 1)) & ((h = key.hashCode()) ^ (h >>> 16));}
}public class MyBloomFilter {public static final int DEFAULT_SIZE = 1 << 20;public BitSet bitSet;public int usedSize;public static final int[] seeds = {5, 7, 11, 13, 27, 33};public Hash[] hashes;public MyBloomFilter() {bitSet = new BitSet(DEFAULT_SIZE);hashes = new Hash[seeds.length];for (int i = 0; i < hashes.length; i++) {hashes[i] = new Hash(DEFAULT_SIZE, seeds[i]);}}public void add(String val) {for (Hash hash : hashes) {int index = hash.hash(val);bitSet.set(index);}usedSize++;}public boolean contains(String val) {for (Hash hash : hashes) {int index = hash.hash(val);boolean flag = bitSet.get(index);if (!flag) {return false;}}return true;//会误判}public static void main(String[] args) {MyBloomFilter myBloomFilter = new MyBloomFilter();myBloomFilter.add("hello");myBloomFilter.add("hello1");myBloomFilter.add("haha");System.out.println(myBloomFilter.contains("hello"));System.out.println(myBloomFilter.contains("hello1"));System.out.println(myBloomFilter.contains("hello2"));}
}

4.应用场景:

1.网页爬虫对URL的去重,避免爬去相同的URL地址。

2.垃圾邮件过滤,从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮箱。

3.解决数据库缓存击穿,黑客攻击服务器时,会构建大量不存在于缓存中的key向服务器发起请求,在数据量足够大的时候,频繁的数据库查询会导致挂机。

4. 秒杀系统,查看用户是否重复购买。

5. google的guava包中有对Bloom Filter的实现
 

5.优点

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

6.缺点

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

7.误判率

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了,这样就无法判断究竟是哪个输入产生的,因此误判的根源在于相同的 bit 位被多次映射且置 1。这种情况也造成了布隆过滤器的删除问题,因为布隆过滤器的每一个 bit 并不是独占的,很有可能多个元素共享了某一位。如果我们直接删除这一位的话,会影响其他的元素。


http://www.ppmy.cn/news/6059.html

相关文章

Qt QCustomPlot 添加多个坐标系区域

Qt QCustomPlot 添加多个坐标系区域 文章目录Qt QCustomPlot 添加多个坐标系区域摘要1 新建多个坐标系QCPAxisQCPAxisRectQCPLayoutGrid2 多个坐标轴如何更新数据添加数据3 遇到的问题最后关键字&#xff1a; Debian、 Linux、 QCustomPlot、 Qt、 QCPAxisRect内容背景&#xf…

云原生之使用Docker部署Python应用

云原生之使用Docker部署Python应用一、检查系统版本1.检查系统 版本2.检查系统内核二、检查docker状态三、编辑python文件1.创建目录2.编辑test.py文件四、构建镜像1.编辑dockerfile文件2.使用dockerfile构建镜像五、运行镜像容器1.运行python_app容器2.查看容器状态六、访问Py…

云原生之Dockerfile简介和基础实践

dockerfile简介和基础实践一、Dockerfile简介1.1、Dockerfile解决的问题1.2、docker build 构建流程1.3、关键字介绍二、Dockerfile 实践2.1、基本语法实践 --- golang问题检查2.2、基本语法实践 --- gcc总结后言一、Dockerfile简介 Dockerfile是一个创建镜像所有命令的文本文…

华为OD机试真题 Java 实现【分奖金】【2022.11 Q4 新题】

目录 题目 思路 考点 Code 题目 题目描述: 公司老板做了一笔大生意,想要给每位员工分配一些奖金,想通过游戏的方式来决定每个人分多少钱。按照员工的工号顺序,每个人随机抽取一个数字。按照工号的顺序往后排列,遇到第一个数字比自己数字大的,那么,前面的员工就可以获…

前端基础(十七)_HTML5新特性

HTML5新特性 1、在网页上绘制图形的canvas元素 原生JavaScriptcanvas实现五子棋游戏_值得一看 鼠标移动淡入淡出Canvas小球效果_TS版本 JS配合canvas实现贪吃蛇小游戏 canvas基础及太极图案例 2、多媒体相关video和audio元素 html5 video 音频标签: audio 标签 在IE8及更早版本…

SpringBoot:模块探究之spring-boot-devtools

Spring Boot 使我们能够快速设置和运行服务。为了进一步增强开发体验&#xff0c;Spring 发布了 spring-boot-devtools 工具——作为 Spring Boot-1.3 的一部分 spring-boot-devtools 是 Spring Boot 提供的一组开发工具&#xff0c;可以提高开发者的工作效率&#xff0c;开发者…

Simulink代码生成: Switch模块及其代码

本文描述Switch模块的建模并研究生成的代码。 文章目录1 Simulink中的Switch模块2 Switch模块建模及代码生成3 Switch模块其他用法3.1 多重Switch3.2 通过标定量Switch4 总结1 Simulink中的Switch模块 在Simulink中Switch模块时非常常见的&#xff0c;通常用于根据一定地条件选…

漏洞扫描的应用范围和场景

漏洞扫描服务范围 安全漏洞扫描服务可以为客户提供包括网络设备、操作系统、数据库、常见应用服务器以及WEB应用等范围的扫描。 漏洞扫描的详细服务范围如下&#xff1a; 操作系统 Windows、发行版Linux、AIX、UNIX通用、Solaris、FreeBSD、HP-UX、BSD等主流操作系统。 数据…