当前栏目
如何快速检查元素是否存在?
大家好,我是指北君。
如标题一样,我们今天看一下一个经常听到,可能没用到的技术。
Guava BloomFilter
布隆过滤器是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。
基本概念
当需要判断某个元素是否在某个数据集中时,一般会怎么做?
将数据集封装成集合,比如List、Set等
通过集合提供的API判断该元素是否存在于集合
这样的实现比较简单,同时通过现有的JDK都能很快达到目的,但是设想一下,如果上面说到的集合数据量非常的大,这样不仅会耗费较大的存储空间,同时 在集合中检索元素的时间复杂度也会随之增加。那么有没比较好的方法去实现判断元素是否存在这样的情形呢?
也就是布隆过滤器。
通过一系列的Hash函数将元素映射到一个位阵列(Bit Array)中的多个点位上,判断元素是否存在,则是判断所有点位是不是都为1。然而,位阵列上都为1并不一定能够保证该元素一定存在,也有可能是其他元素Hash后落在了该点位上,这就是布隆过滤器的误判。
因此通过布隆过滤器我们可以确定:
- 元素可能在集合中
- 元素一定不在集合中
应用场景
- 网页爬虫时忽略已经判定的URL路径
- 邮箱通过设置过滤垃圾邮件
- 集合重复元素的判别,有效判断元素不在集合中
- 防止数据缓存时的缓存穿透问题
优缺点
- 优点
相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。
布隆过滤器存储空间和插入/查询时间都是常数。
Hash函数相互之间没有关系,方便由硬件并行实现。
布隆过滤器不需要存储元素本身,对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集,其它任何数据结构都不能。
- 缺点
元素存在的误判
一般情况下不支持元素(位阵列)的删除
实现原理
核心其实是元素如何存储?如何判断元素是否存在?核心方法就两个,一个“存”一个检查,里面涉及到了算法相关知识,感兴趣可以深入研究下其实现原理与思想。
- put 将元素放入过滤器中,但不是存储
- mightContain 与put相似,计算的过程相同,不同的是值的判断
我们可以简单第理解其实现原理?比如现在有一个容器,我们定义为String[] bitArray = new String[26]作为位阵列, 现在有一堆由小写英文组成的元素,我们假定Hash算法为a-z到1~26的映射。
- 现在有一个元素abc,hash后为1110000000...,保存到bitArray :1110000000...
- 现在有一个元素cde, hash后为0011100000...,保存到bitArray :1111100000...
- 现在又有一个新的元素ade,hash后同样为100110000...,很明显会认为该元素存在,这就是FFP
为什么判断元素一定不在集合中呢?很显然,如果一个元素存在,则该元素hash后的bit数组必须全部都是1,反之则不存在
示例
流程很简单:
- 根据配置构建BloomFilter对象
- 通过put方法,初始化数据到filter
- 通过方法mightContain判断元素是否存在
结束语
BloomFilter虽然看起来简单,但是其内部的实现包含了很多的数学与算法知识,我们只是通过其简单的API就能各种复杂的功能。关于如何将目前说到的这些在具体的项目中进行实践与集成 后面会来介绍,首先我们能够先了解一些技术一起能解决上面问题,理解了原理与目的,使用也就不是难事。
相关文章
- JDK中内嵌JS引擎介绍及使用
- 49195,npm最后的疯狂?盘点10款最有前途JavaScript构建工具
- 译文:5个增强Node.js应用程序增强功能
- 4个例子,吃透 JavaScript 实现的二叉搜索树 BST
- Vue中使用XML和JSON格式互转插件
- JDK中Jshell简单使用(JDK9版本以上或者JDK9版本)
- shiro中的JSP标签支持
- Java技术点-json转对象,对象转json
- SpringBoot+SpringDataJpa @Query之 JPQL使用书写模板(模糊查询and条件查询)
- Spring Boot中的Freemarker模版引擎引用css和js的正确姿势
- Node.js解压版的环境配置及相关常用命令
- JSP学习笔记(6)—— 自定义MVC框架
- JSP学习笔记(5)——Servlet、监听器、过滤器、MVC模式介绍
- Jsp学习笔记(4)——分页查询
- APIJSON简单使用
- JSP学习笔记(3)——JSTL 标签库
- JSP学习笔记(1)——Jsp指令、动作元素和内置对象
- JavaScript ES6 Promise对象
- Web前端——JavaScript扩展补充
- Web前端——表单提交和Js添加选项