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

布隆过滤器是可以用于判断一个元素是不是在一个集合里,并且相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。但是它也是拥有一定的缺点:布隆过滤器是有一定的误识别率以及删除困难的。本文中给出的布隆过滤器的实现,基本满足了日常使用所需要的功能。

0 0 0 0 0 0 0 0 0 0

先简单来说一下布隆过滤器。其实现方法就是:利用内存中一个长度为M的位数组B并初始化里面的所有位都为0,如下面的表格所示:

然后我们根据H个不同的散列函数,对传进来的字符串进行散列,并且每次的散列结果都不能大于位数组的长度。布隆过滤器的误判率取决于你使用多少个不同的散列函数,下面给出的代码中,给出了一些参考的误判率(参考代码中的枚举类:MisjudgmentRate)。现在我们先假定有4个不同散列函数,传入一个字符串并进行一次插入操作,这时会进行4次散列,假设到了4个不同的下标,这个时候我们就会去数组中,将这些下标的位置置为1,数组变更为:

0 1 0 1 1 0 0 0 0 1

如果接下来我们再传入同一个字符串时,因为4次的散列结果都是跟上一次一样的,所以会得出跟上面一样的结果,所有应该置1的位都已经置1了,这个时候我们就可以认为这个字符串是已经存在的了。因此不难发现,这是会存在一定的误判率的,具体由你采用的散列函数质量,以及散列函数的数量确定。

代码如下:

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;

public class BloomFileter implements Serializable {
 private static final long serialVersionUID = -5221305273707291280L;
 private final int[] seeds;
 private final int size;
 private final BitSet notebook;
 private final MisjudgmentRate rate;
 private final AtomicInteger useCount = new AtomicInteger(0);
 private final Double autoClearRate;

 /**
 * 默认中等程序的误判率:MisjudgmentRate.MIDDLE 以及不自动清空数据(性能会有少许提升)
 *
 * @param dataCount
 *      预期处理的数据规模,如预期用于处理1百万数据的查重,这里则填写1000000
 */
 public BloomFileter(int dataCount) {
 this(MisjudgmentRate.MIDDLE, dataCount, null);
 }

 /**
 *
 * @param rate
 *      一个枚举类型的误判率
 * @param dataCount
 *      预期处理的数据规模,如预期用于处理1百万数据的查重,这里则填写1000000
 * @param autoClearRate
 *      自动清空过滤器内部信息的使用比率,传null则表示不会自动清理,
 *      当过滤器使用率达到100%时,则无论传入什么数据,都会认为在数据已经存在了
 *      当希望过滤器使用率达到80%时自动清空重新使用,则传入0.8
 */
 public BloomFileter(MisjudgmentRate rate, int dataCount, Double autoClearRate) {
 long bitSize = rate.seeds.length * dataCount;
 if (bitSize < 0 || bitSize > Integer.MAX_VALUE) {
  throw new RuntimeException("位数太大溢出了,请降低误判率或者降低数据大小");
 }
 this.rate = rate;
 seeds = rate.seeds;
 size = (int) bitSize;
 notebook = new BitSet(size);
 this.autoClearRate = autoClearRate;
 }

 public void add(String data) {
 checkNeedClear();

 for (int i = 0; i < seeds.length; i++) {
  int index = hash(data, seeds[i]);
  setTrue(index);
 }
 }

 public boolean check(String data) {
 for (int i = 0; i < seeds.length; i++) {
  int index = hash(data, seeds[i]);
  if (!notebook.get(index)) {
  return false;
  }
 }
 return true;
 }

 /**
 * 如果不存在就进行记录并返回false,如果存在了就返回true
 *
 * @param data
 * @return
 */
 public boolean addIfNotExist(String data) {
 checkNeedClear();

 int[] indexs = new int[seeds.length];
 // 先假定存在
 boolean exist = true;
 int index;

 for (int i = 0; i < seeds.length; i++) {
  indexs[i] = index = hash(data, seeds[i]);

  if (exist) {
  if (!notebook.get(index)) {
   // 只要有一个不存在,就可以认为整个字符串都是第一次出现的
   exist = false;
   // 补充之前的信息
   for (int j = 0; j <= i; j++) {
   setTrue(indexs[j]);
   }
  }
  } else {
  setTrue(index);
  }
 }

 return exist;

 }

 private void checkNeedClear() {
 if (autoClearRate != null) {
  if (getUseRate() >= autoClearRate) {
  synchronized (this) {
   if (getUseRate() >= autoClearRate) {
   notebook.clear();
   useCount.set(0);
   }
  }
  }
 }
 }

 public void setTrue(int index) {
 useCount.incrementAndGet();
 notebook.set(index, true);
 }

 private int hash(String data, int seeds) {
 char[] value = data.toCharArray();
 int hash = 0;
 if (value.length > 0) {

  for (int i = 0; i < value.length; i++) {
  hash = i * hash + value[i];
  }
 }

 hash = hash * seeds % size;
 // 防止溢出变成负数
 return Math.abs(hash);
 }

 public double getUseRate() {
 return (double) useCount.intValue() / (double) size;
 }

 public void saveFilterToFile(String path) {
 try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(path))) {
  oos.writeObject(this);
 } catch (Exception e) {
  throw new RuntimeException(e);
 }

 }

 public static BloomFileter readFilterFromFile(String path) {
 try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream(path))) {
  return (BloomFileter) ois.readObject();
 } catch (Exception e) {
  throw new RuntimeException(e);
 }
 }

 /**
 * 清空过滤器中的记录信息
 */
 public void clear() {
 useCount.set(0);
 notebook.clear();
 }

 public MisjudgmentRate getRate() {
 return rate;
 }

 /**
 * 分配的位数越多,误判率越低但是越占内存
 *
 * 4个位误判率大概是0.14689159766308
 *
 * 8个位误判率大概是0.02157714146322
 *
 * 16个位误判率大概是0.00046557303372
 *
 * 32个位误判率大概是0.00000021167340
 *
 * @author lianghaohui
 *
 */
 public enum MisjudgmentRate {
 // 这里要选取质数,能很好的降低错误率
 /**
  * 每个字符串分配4个位
  */
 VERY_SMALL(new int[] { 2, 3, 5, 7 }),
 /**
  * 每个字符串分配8个位
  */
 SMALL(new int[] { 2, 3, 5, 7, 11, 13, 17, 19 }), //
 /**
  * 每个字符串分配16个位
  */
 MIDDLE(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 }), //
 /**
  * 每个字符串分配32个位
  */
 HIGH(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
  101, 103, 107, 109, 113, 127, 131 });

 private int[] seeds;

 private MisjudgmentRate(int[] seeds) {
  this.seeds = seeds;
 }

 public int[] getSeeds() {
  return seeds;
 }

 public void setSeeds(int[] seeds) {
  this.seeds = seeds;
 }

 }

 public static void main(String[] args) {
 BloomFileter fileter = new BloomFileter(7);
 System.out.println(fileter.addIfNotExist("1111111111111"));
 System.out.println(fileter.addIfNotExist("2222222222222222"));
 System.out.println(fileter.addIfNotExist("3333333333333333"));
 System.out.println(fileter.addIfNotExist("444444444444444"));
 System.out.println(fileter.addIfNotExist("5555555555555"));
 System.out.println(fileter.addIfNotExist("6666666666666"));
 System.out.println(fileter.addIfNotExist("1111111111111"));
 fileter.saveFilterToFile("C:\\Users\\john\\Desktop\\1111\\11.obj");
 fileter = readFilterFromFile("C:\\Users\\john\\Desktop\\111\\11.obj");
 System.out.println(fileter.getUseRate());
 System.out.println(fileter.addIfNotExist("1111111111111"));
 }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2018-10-17

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

前言 记得前段时间的文章么?redis使用位图法记录在线用户的状态,还是需要自己实现一个IM在线用户状态的记录,今天来讲讲另一方案,布隆过滤器 布隆过滤器的作用是加快判定一个元素是否在集合中出现的方法.因为其主要是过滤掉了大部分元素间的精确匹配,故称为过滤器. 布隆过滤器 在日常生活工作,我们会经常遇到这的场景,从一个Excel里面检索一个信息在不在Excel表中,还记得被CTRL+F支配的恐惧么,不扯了,软件开发中,一般会使用散列表来实现,Hash Table也叫哈希表,哈希表的优点是快速准确

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

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

布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法

引言 在介绍布隆过滤器之前我们首先引入几个场景. 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了.那么如何避免频繁访问数量为0的key而导致的缓存被击穿? 有人说, 将这个key的值置为0存入缓存不就行了吗?确实,这是一个好的方案.大部分情况我们都是这样做的,当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存.不过这样做的缺点也很明显,浪费内存和无法抵御随机key攻击. 场景二 在一个黑名

布隆过滤器的概述及Python实现方法

布隆过滤器 布隆过滤器是一种概率空间高效的数据结构.它与hashmap非常相似,用于检索一个元素是否在一个集合中.它在检索元素是否存在时,能很好地取舍空间使用率与误报比例.正是由于这个特性,它被称作概率性数据结构(probabilistic data structure). 空间效率 我们来仔细地看看它的空间效率.如果你想在集合中存储一系列的元素,有很多种不同的做法.你可以把数据存储在hashmap,随后在hashmap中检索元素是否存在,hashmap的插入和查询的效率都非常高.但是,由于ha

python实现布隆过滤器及原理解析

在学习redis过程中提到一个缓存击穿的问题, 书中参考的解决方案之一是使用布隆过滤器, 那么就有必要来了解一下什么是布隆过滤器.在参考了许多博客之后, 写个总结记录一下. 一.布隆过滤器简介 什么是布隆过滤器? 本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 "某样东西一定不存在或者可能存在". 相比于传统的 Set.Map 等数据结构,它更高效

python使用布隆过滤器的实现示例

使用库pybloom_live from pybloom_live import ScalableBloomFilter,BloomFilter # 可自动伸缩的布隆过滤器 bloom = ScalableBloomFilter(initial_capacity=100,error_rate=0.001) # 添加内容 bloom.add('daqi') print('daqi'in bloom) # 定长的布隆过滤器 bloom1 = BloomFilter(capacity=10000) b

Redis实现布隆过滤器的方法及原理

布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器. 应用场景 1.50亿个电话号码,现有10万个电话号码,如何判断这10万个是否已经存在在50亿个之中?(可能方案:数据库,set, hyperloglog) 2.新闻客户端看新闻时,它会不

java过滤器中Filter的ChainFilter过滤链

1.什么是过滤器? 在客户端到服务器的过程中,当发送请求时,如果有不符合的信息将会被filter进行拦截,如果符合则会进行放行,在服务器给客户端响应时也会进行判断 如果有不符合的信息将会被filter进行拦截,如果符合则会进行放行. OOP:Java面向对象编程,抽象.封装.继承.多态. AOP:面向切面编程,过滤器就是一个面向切面的编程思想. AOP是sun公司srvlet2.3版本之后推出的新功能,在2.3之前的版本没有该功能,定义一个过滤器需要实现(implement)Filter接口,这

java 过滤器模式(Filter/Criteria Pattern)详细介绍

java 过滤器模式(Filter/Criteria Pattern) 过滤器模式(Filter Pattern)或标准模式(Criteria Pattern)是一种设计模式,这种模式允许开发人员使用不同的标准来过滤一组对象,通过逻辑运算以解耦的方式把它们连接起来.这种类型的设计模式属于结构型模式,它结合多个标准来获得单一标准. 过滤器模式(Filter Pattern)或标准模式(Criteria Pattern)是一种设计模式,这种模式允许开发人员使用不同的标准来过滤一组对象,通过逻辑运算以