Java实现布隆过滤器的方法步骤

前言

记得前段时间的文章么?redis使用位图法记录在线用户的状态,还是需要自己实现一个IM在线用户状态的记录,今天来讲讲另一方案,布隆过滤器

布隆过滤器的作用是加快判定一个元素是否在集合中出现的方法。因为其主要是过滤掉了大部分元素间的精确匹配,故称为过滤器。

布隆过滤器

在日常生活工作,我们会经常遇到这的场景,从一个Excel里面检索一个信息在不在Excel表中,还记得被CTRL+F支配的恐惧么,不扯了,软件开发中,一般会使用散列表来实现,Hash Table也叫哈希表,哈希表的优点是快速准确,缺点是浪费储存空间,我们这个场景,储存登录的userId到哈希表,当用户规模十分巨大的时候,哈希表的储存效率低的问题就显示出来了,今天介绍一种数学工具:布隆过滤器,它只需要哈希表1/8到1/4的大小就能解决同样的问题。

背书中

布隆过滤器(Bloom Filter)是由伯顿·布隆(Burton Bloom)于1970年提出来的,它实际上是一个很长的二进制向量和一系列随机映射函数。

原理

使用我们这个场景,来讲原理吧,假设我们的个人网站同时在线人数达到1亿(意淫一下),要存储这一亿人的在线状态,先构建一个16亿比特位即两亿字节的向量,然后把这16亿个比特位都记为0。对于每一个登录用的userId,使用8个不同的算法产出8个不同信息指纹,在用一个算法把这8个信息隐身到这16亿个比特位的8个位置上,把这8个位置都设置成1,这样就构建成了一个记录一亿用户在线状态的布隆过滤器。


1亿在线用户的布隆过滤器

检索就是同样的原理,使用相同的算法对要检索的userId产生8个信息指纹,然后在看这八个信息指纹在这16亿比特位对应的值是否为1,都为1就说明这个userId在线,下面就用java代码来实现一个布隆过滤器。

Java实现布隆过滤器

先实现一个简单的布隆过滤器

package edu.se;

import java.util.BitSet;

/**
 * @author ZhaoWeinan
 * @date 2018/10/28
 * @description
 */
public class BloomFileter {

 //使用加法hash算法,所以定义了一个8个元素的质数数组
 private static final int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
 //用八个不同的质数,相当于构建8个不同算法
 private Hash[] hashList = new Hash[primes.length];
 //创建一个长度为10亿的比特位
 private BitSet bits = new BitSet(256 << 22);

 public BloomFileter() {
 for (int i = 0; i < primes.length; i++) {
  //使用8个质数,创建八种算法
  hashList[i] = new Hash(primes[i]);
 }
 }

 //添加元素
 public void add(String value) {
 for (Hash f : hashList) {
  //算出8个信息指纹,对应到2的32次方个比特位上
  bits.set(f.hash(value), true);
 }
 }

 //判断是否在布隆过滤器中
 public boolean contains(String value) {
 if (value == null) {
  return false;
 }
 boolean ret = true;
 for (Hash f : hashList) {
  //查看8个比特位上的值
  ret = ret && bits.get(f.hash(value));
 }
 return ret;
 }

 //加法hash算法
 public static class Hash {

 private int prime;

 public Hash(int prime) {
  this.prime = prime;
 }

 public int hash(String key) {
  int hash, i;
  for (hash = key.length(), i = 0; i < key.length(); i++) {
  hash += key.charAt(i);
  }
  return (hash % prime);
 }
 }

 public static void main(String[] args) {

 BloomFileter bloomFileter = new BloomFileter();
 System.out.println(bloomFileter.contains("5324512515"));
 bloomFileter.add("5324512515");

 //维护1亿个在线用户
 for (int i = 1 ; i < 100000000 ; i ++){
  bloomFileter.add(String.valueOf(i));
 }

 long begin = System.currentTimeMillis();
 System.out.println(begin);
 System.out.println(bloomFileter.contains("5324512515"));
 long end = System.currentTimeMillis();
 System.out.println(end);
 System.out.println("判断5324512515是否在线使用了:" + (begin - end));
 }
}

这段代码是构建了一个10亿位的bitSet,然后把一亿个userId加入到了我们的布隆过滤器中,最近判断5324512515这个userId是否登录,打出代码的执行时间


维护了1亿个userId以后检索5324512515是否登录,代码执行时间很短

在让我们来看看内存占用的情况


jvm整个的内存情况

再来看看BloomFileter这个类的实例,就占用了100多MB

实例的大小

看来布隆过滤器对于储存的效率确实很高

布隆过滤器的误识别问题

布隆过滤器的好处在于快速、省空间,但是有一定的误识别率,这个概率很小,要计算出现误识别的概率并不难,下面贴一段书上的话

假定布隆过滤器有m比特,里面有n个元素,每个元素对应k个信息指纹的hash函数,在这个布隆过滤器插入一个元素,那么比特位被设置成1的概率为1/m,它依然为0的概率为1-1/m,那么k个哈希函数都没有把他设置成1的概率为1-1/m的k次方,一个比特在插入了n个元素后,被设置为1的概率为1减1-1/m的kn次方,最后书上给出了一个公式,在这里就不贴了,就贴一个表吧,是m/n比值不同,以及K分别为不同的值得情况下的假阳性概率:


书上的表,直接拍下来的

书上的表,直接拍下来的

布隆过滤器就为大家说到这里,欢迎大家来交流,指出文中一些说错的地方,让我加深认识。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

时间: 2018-11-03

布隆过滤器(Bloom Filter)的Java实现方法

布隆过滤器原理很简单:就是把一个字符串哈希成一个整数key,然后选取一个很长的比特序列,开始都是0,在key把此位置的0变为1:下次进来一个字符串,哈希之后的值key,如果在此比特位上的值也是1,那么就说明这个字符串存在了. 如果按照上面的做法,那就和哈希算法没有什么区别了,哈希算法还有重复的呢. 布隆过滤器是将一个字符串哈希成多个key,我还是按照书上的说吧. 先建立一个16亿二进制常量,然后将这16亿个二进制位全部置0.对于每个字符串,用8个不同的随机产生器(F1,F2,.....,F8)产

JAVA实现较完善的布隆过滤器的示例代码

布隆过滤器是可以用于判断一个元素是不是在一个集合里,并且相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势.布隆过滤器存储空间和插入/查询时间都是常数.但是它也是拥有一定的缺点:布隆过滤器是有一定的误识别率以及删除困难的.本文中给出的布隆过滤器的实现,基本满足了日常使用所需要的功能. 0 0 0 0 0 0 0 0 0 0 先简单来说一下布隆过滤器.其实现方法就是:利用内存中一个长度为M的位数组B并初始化里面的所有位都为0,如下面的表格所示: 然后我们根据H个不同的散列函数,对传进来

Java 添加Word目录的2种方法示例代码详解

目录是一种能够快速.有效地帮助读者了解文档或书籍主要内容的方式.在Word中,插入目录首先需要设置相应段落的大纲级别,根据大纲级别来生成目录表.本文中生成目录分2种情况来进行: 1.文档没有设置大纲级别,生成目录前需要手动设置 2.文档已设置大纲级别,通过域代码生成目录 使用工具: •Free Spire.Doc for Java 2.0.0 (免费版) •IntelliJ IDEA 工具获取途径1:通过官网下载jar文件包,解压并导入jar文件到IDEA程序. 工具获取途径2:通过Maven仓

Java spring boot 实现支付宝支付功能的示例代码

一.准备工作: 1.登陆支付宝开发者中心,申请一个开发者账号. 地址:https://openhome.alipay.com/ 2.进入研发服务: 3.点击链接进入工具下载页面: 4.点击下载对应版本的RSA公钥生成器: 5.生成公钥密钥(记录你的应用私钥): 6.在支付宝配置公钥(点击保存): 二.搭建demo 1.引入jia包: <dependency> <groupId>com.alipay.sdk</groupId> <artifactId>alip

java中的前++和后++的区别示例代码详解

java中的前加加++和后加加++,有很多人搞的很晕,不太明白!今天我举几个例子说明下前++和后++的区别! 其实大家只要记住一句话就可以了,前++是先自加再使用而后++是先使用再自加! 前++和后++总结:其实大家只要记住一句话就可以了,前++是先自加再使用而后++是先使用再自加! 请大家看下面的例子就明白了! public class Test { public static void main(String[] args) { //测试,前加加和后加加 //前++和后++总结:其实大家只要

JAVA Netty实现聊天室+私聊功能的示例代码

功能介绍 使用Netty框架实现聊天室功能,服务器可监控客户端上下限状态,消息转发.同时实现了点对点私聊功能.技术点我都在代码中做了备注,这里不再重复写了.希望能给想学习netty的同学一点参考. 服务器代码 服务器入口代码 package nio.test.netty.groupChat; import io.netty.bootstrap.ServerBootstrap; import io.netty.channel.ChannelFuture; import io.netty.chann

Java实现md5和base64加密解密的示例代码

import java.io.IOException; import java.security.MessageDigest; import sun.misc.BASE64Encoder; import sun.misc.BASE64Decoder; public class MD5Util { /** * MD5加密 */ public static String md5Encryption(String str) { MessageDigest md5 = null; try { md5 =

Java批量写入文件和下载图片的示例代码

很久没有在WhitMe上写日记了,因为觉着在App上写私密日记的话肯定是不安全的,但是想把日记存下来.,然后看到有导出日记的功能,就把日记导出了(还好可以直接导出,不然就麻烦点).导出的是一个html文件.可以直接打开,排版都还在. 看了下源码,是把日记存在一个json数组里了,图片还是在服务器,利用url访问,文字是在本地了. 但是想把图片下载到本地,然后和文字对应,哪篇日记下的哪些图片. 大概是如下的json数组. 大概有几百条,分别是头像.内容:文字||内容:图片.时间. 简单明了的jso

Java如何获取Date的“昨天”与“明天”示例代码

前言 相信大家在java中用到的最多的时间类莫过于 java.util.Date了,由于Date类中将getYear() , getMonth()等获取年.月.日的方法都废弃了,所以本文的问题要借助于Calendar来实现了,下面来直接看示例代码吧. 使用日历类:Calendar @Test public void dateTest() { Date today = new Date(); for(int i=0;i<10;i++) { today = yesterday(today); Sys

java高并发锁的3种实现示例代码

初级技巧 - 乐观锁 乐观锁适合这样的场景:读不会冲突,写会冲突.同时读的频率远大于写. 以下面的代码为例,悲观锁的实现: public Object get(Object key) { synchronized(map) { if(map.get(key) == null) { // set some values } return map.get(key); } } 乐观锁的实现: public Object get(Object key) { Object val = null; if((

Java利用POI实现导入导出Excel表格示例代码

介绍 Jakarta POI 是一套用于访问微软格式文档的Java API.Jakarta POI有很多组件组成,其中有用于操作Excel格式文件的HSSF和用于操作Word的HWPF,在各种组件中目前只有用于操作Excel的HSSF相对成熟.官方主页http://poi.apache.org/index.html,API文档http://poi.apache.org/apidocs/index.html 实现 已经在代码中加入了完整的注释. import java.io.FileInputSt