前言
记得前段时间的文章么？ 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实现布隆过滤器
先实现一个简单的布隆过滤器
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
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分别为不同的值得情况下的假阳性概率：
书上的表，直接拍下来的
书上的表，直接拍下来的
布隆过滤器就为大家说到这里，欢迎大家来交流，指出文中一些说错的地方，让我加深认识。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对的支持。
原文链接：https://HdhCmsTestjianshu测试数据/p/7634eaea3e26
查看更多关于Java实现布隆过滤器的方法步骤的详细内容...