精华内容
下载资源
问答
  • 2021-02-28 14:37:25

    /**

    * 项目名:SpiderCrawler

    * 文件名:BloomFilterTest.java

    * 作者:zhouyh

    * 时间:2014-8-29 下午02:54:56

    * 描述:TODO(用一句话描述该文件做什么)

    */

    package com.utilTest;

    import java.io.BufferedReader;

    import java.io.File;

    import java.io.FileInputStream;

    import java.io.IOException;

    import java.io.InputStream;

    import java.io.InputStreamReader;

    import java.util.BitSet;

    /**

    * 类名: BloomFilterTest

    * 包名: com.utilTest

    * 作者: zhouyh

    * 时间: 2014-8-29 下午02:54:56

    * 描述: 布隆过滤器,传统的布隆过滤器不支持从集合中删除成员

    */

    public class BloomFilterTest {

    //DEFAULT_SIZE为2的29次方,即此处的左移28位

    private static final int DEFAULT_SIZE = 2<<28;

    /*

    * 不同哈希函数的种子,一般取质数

    * seeds数组共有8个值,则代表采用8种不同的哈希函数

    */

    private int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61};

    /*

    * 初始化一个给定大小的位集

    * BitSet实际是由“二进制位”构成的一个Vector。

    * 假如希望高效率地保存大量“开-关”信息,就应使用BitSet.

    */

    private BitSet bitSets = new BitSet(DEFAULT_SIZE);

    //构建hash函数对象

    private SimpleHash[] hashFuns = new SimpleHash[seeds.length];

    //布隆过滤器配置文件存放路径

    private String path = "";

    public BloomFilterTest(String path){

    /**

    *  给出所有的hash值,共计seeds.length个hash值。共8位。

    *  通过调用SimpleHash.hash(),可以得到根据8种hash函数计算得出hash值。

    *  传入DEFAULT_SIZE(最终字符串的长度),seeds[i](一个指定的质数)即可得到需要的那个hash值的位置。

    */

    for(int i=0; i

    hashFuns[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);

    }

    //配置文件路径地址

    this.path = path;

    }

    /**

    *

    * 方法名:add

    * 作者:zhouyh

    * 创建时间:2014-8-30 下午02:07:35

    * 描述:将给定的字符串标记到bitSets中,即设置字符串的8个函数值的位置为1

    * @param value

    */

    public synchronized void add(String value){

    for(SimpleHash hashFun : hashFuns){

    bitSets.set(hashFun.hash(value), true);

    }

    }

    /**

    *

    * 方法名:isExit

    * 作者:zhouyh

    * 创建时间:2014-8-30 下午02:12:30

    * 描述:判断给定的字符串是否已经存在在bloofilter中,如果存在返回true,不存在返回false

    * @param value

    * @return

    */

    public synchronized boolean isExit(String value){

    //判断传入的值是否为null

    if(null == value){

    return false;

    }

    for(SimpleHash hashFun : hashFuns){

    if(!bitSets.get(hashFun.hash(value))){

    //如果判断8个hash函数值中有一个位置不存在即可判断为不存在Bloofilter中

    return false;

    }

    }

    return true;

    }

    /**

    *

    * 方法名:init

    * 作者:zhouyh

    * 创建时间:2014-8-30 下午02:28:49

    * 描述:读取配置文件

    */

    public void init(){

    File file = new File(path);

    FileInputStream in = null;

    try {

    in = new FileInputStream(file);

    long lt = System.currentTimeMillis();

    read(in);

    System.out.println(System.currentTimeMillis()-lt);

    System.out.println(Runtime.getRuntime().totalMemory());

    }catch(Exception e){

    e.printStackTrace();

    }finally{

    try {

    if(in!=null){

    in.close();

    in = null;

    }

    } catch (IOException e) {

    // TODO Auto-generated catch block

    e.printStackTrace();

    }

    }

    }

    /**

    *

    * 方法名:read

    * 作者:zhouyh

    * 创建时间:2014-8-30 下午02:26:59

    * 描述:根据传入的流,初始化bloomfilter

    * @param in

    */

    private void read(InputStream in){

    if(null == in){ //如果in为null,则返回

    return;

    }

    int i = 0;

    InputStreamReader reader = null;

    try {

    //创建输入流

    reader = new InputStreamReader(in, "UTF-8");

    BufferedReader buffReader = new BufferedReader(reader, 512);

    String theWord = null;

    do {

    i++;

    theWord = buffReader.readLine();

    //如果theWord不为null和空,则加入Bloomfilter中

    if(theWord!=null && !theWord.trim().equals("")){

    add(theWord);

    }

    if(i%10000 == 0){

    System.out.println(i);

    }

    } while (theWord != null);

    } catch (IOException e){

    e.printStackTrace();

    } finally{

    //关闭流

    try {

    if(reader != null){

    reader.close();

    reader = null;

    }

    if(in != null){

    in.close();

    in = null;

    }

    } catch (IOException e) {

    // TODO: handle exception

    e.printStackTrace();

    }

    }

    }

    /**

    * 方法名:main

    * 作者:zhouyh

    * 创建时间:2014-8-29 下午02:54:56

    * 描述:TODO(这里用一句话描述这个方法的作用)

    * @param args

    */

    public static void main(String[] args) {

    // TODO Auto-generated method stub

    BloomFilterTest bloomFilterTest = new BloomFilterTest("f:/fetchedurls.txt");

    bloomFilterTest.init();

    System.out.println(bloomFilterTest.isExit("http://www.plating.org/news_info.asp?pid=28&id=2857"));

    }

    public static class SimpleHash {

    /*

    * cap为DEFAULT_SIZE,即用于结果的最大字符串的值

    * seed为计算hash值的一个key值,具体对应上文中的seeds数组

    */

    private int cap;

    private int seed;

    /**

    *

    * 构造函数

    * 作者:zhouyh

    * @param cap

    * @param seed

    */

    public SimpleHash(int cap, int seed){

    this.cap = cap;

    this.seed = seed;

    }

    /**

    *

    * 方法名:hash

    * 作者:zhouyh

    * 创建时间:2014-8-30 下午01:47:10

    * 描述:计算hash的函数,用户可以选择其他更好的hash函数

    * @param value

    * @return

    */

    public int hash(String value){

    int result = 0;

    int length = value.length();

    for(int i=0; i

    result = seed*result + value.charAt(i);

    }

    return (cap-1) & result;

    }

    }

    }

    更多相关内容
  • 布隆过滤器是可以用于判断一个元素是不是在一个集合里,并且相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。下面这篇文章主要给大家介绍了关于Java实现布隆过滤器的相关资料,需要的朋友可以参考下
  • 布隆过滤器 java实现代码

    热门讨论 2012-06-29 11:16:23
    布隆过滤器 源码 java版 /** * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software ...
  • Java实现布隆过滤器

    千次阅读 2022-01-28 16:09:47
    布隆过滤器 海量数据处理以及缓存穿透这两个场景让我认识了 布隆过滤器 ...通过 Java 编程手动实现布隆过滤器。 利用 Google 开源的 Guava 中自带的布隆过滤器。 Redis 中的布隆过滤器。 什么是布隆过滤器? 首先,我

    布隆过滤器

    海量数据处理以及缓存穿透这两个场景让我认识了 布隆过滤器 ,我查阅了一些资料来了解它,但是很多现成资料并不满足我的需求,所以就决定自己总结一篇关于布隆过滤器的文章。希望通过这篇文章让更多人了解布隆过滤器,并且会实际去使用它!

    下面我们将分为几个方面来介绍布隆过滤器:

    1. 什么是布隆过滤器?
    2. 布隆过滤器的原理介绍。
    3. 布隆过滤器使用场景。
    4. 通过 Java 编程手动实现布隆过滤器。
    5. 利用 Google 开源的 Guava 中自带的布隆过滤器。
    6. Redis 中的布隆过滤器。

    什么是布隆过滤器?

    首先,我们需要了解布隆过滤器的概念。

    布隆过滤器(Bloom Filter)是一个叫做 Bloom 的老哥于 1970 年提出的。我们可以把它看作由二进制向量(或者说位数组)和一系列随机映射函数(哈希函数)两部分组成的数据结构。相比于我们平时常用的的 List、Map 、Set 等数据结构,它占用空间更少并且效率更高,但是缺点是其返回的结果是概率性的,而不是非常准确的。理论情况下添加到集合中的元素越多,误报的可能性就越大。并且,存放在布隆过滤器的数据不容易删除。

    布隆过滤器示意图

    位数组中的每个元素都只占用 1 bit ,并且每个元素只能是 0 或者 1。这样申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间。

    总结:一个名叫 Bloom 的人提出了一种来检索元素是否在给定大集合中的数据结构,这种数据结构是高效且性能很好的,但缺点是具有一定的错误识别率和删除难度。并且,理论情况下,添加到集合中的元素越多,误报的可能性就越大。

    布隆过滤器的原理介绍

    当一个元素加入布隆过滤器中的时候,会进行如下操作:

    1. 使用布隆过滤器中的哈希函数对元素值进行计算,得到哈希值(有几个哈希函数得到几个哈希值)。
    2. 根据得到的哈希值,在位数组中把对应下标的值置为 1。

    当我们需要判断一个元素是否存在于布隆过滤器的时候,会进行如下操作:

    1. 对给定元素再次进行相同的哈希计算;
    2. 得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值在布隆过滤器中,如果存在一个值不为 1,说明该元素不在布隆过滤器中。

    举个简单的例子:

    布隆过滤器hash计算

    如图所示,当字符串存储要加入到布隆过滤器中时,该字符串首先由多个哈希函数生成不同的哈希值,然后将对应的位数组的下标设置为 1(当位数组初始化时,所有位置均为 0)。当第二次存储相同字符串时,因为先前的对应位置已设置为 1,所以很容易知道此值已经存在(去重非常方便)。

    如果我们需要判断某个字符串是否在布隆过滤器中时,只需要对给定字符串再次进行相同的哈希计算,得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值在布隆过滤器中,如果存在一个值不为 1,说明该元素不在布隆过滤器中。

    不同的字符串可能哈希出来的位置相同,这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。

    综上,我们可以得出:布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不在,那么这个元素一定不在。

    布隆过滤器使用场景

    1. 判断给定数据是否存在:比如判断一个数字是否存在于包含大量数字的数字集中(数字集很大,5 亿以上!)、 防止缓存穿透(判断请求的数据是否有效避免直接绕过缓存请求数据库)等等、邮箱的垃圾邮件过滤、黑名单功能等等。
    2. 去重:比如爬给定网址的时候对已经爬取过的 URL 去重。

    编码实战

    通过 Java 编程手动实现布隆过滤器

    我们上面已经说了布隆过滤器的原理,知道了布隆过滤器的原理之后就可以自己手动实现一个了。

    如果你想要手动实现一个的话,你需要:

    1. 一个合适大小的位数组保存数据
    2. 几个不同的哈希函数
    3. 添加元素到位数组(布隆过滤器)的方法实现
    4. 判断给定元素是否存在于位数组(布隆过滤器)的方法实现。

    下面给出一个我觉得写的还算不错的代码(参考网上已有代码改进得到,对于所有类型对象皆适用):

    import java.util.BitSet;
    
    public class MyBloomFilter {
    
        /**
         * 位数组的大小
         */
        private static final int DEFAULT_SIZE = 2 << 24;
        /**
         * 通过这个数组可以创建 6 个不同的哈希函数
         */
        private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
    
        /**
         * 位数组。数组中的元素只能是 0 或者 1
         */
        private BitSet bits = new BitSet(DEFAULT_SIZE);
    
        /**
         * 存放包含 hash 函数的类的数组
         */
        private SimpleHash[] func = new SimpleHash[SEEDS.length];
    
        /**
         * 初始化多个包含 hash 函数的类的数组,每个类中的 hash 函数都不一样
         */
        public MyBloomFilter() {
            // 初始化多个不同的 Hash 函数
            for (int i = 0; i < SEEDS.length; i++) {
                func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
            }
        }
    
        /**
         * 添加元素到位数组
         */
        public void add(Object value) {
            for (SimpleHash f : func) {
                bits.set(f.hash(value), true);
            }
        }
    
        /**
         * 判断指定元素是否存在于位数组
         */
        public boolean contains(Object value) {
            boolean ret = true;
            for (SimpleHash f : func) {
                ret = ret && bits.get(f.hash(value));
            }
            return ret;
        }
    
        /**
         * 静态内部类。用于 hash 操作!
         */
        public static class SimpleHash {
    
            private int cap;
            private int seed;
    
            public SimpleHash(int cap, int seed) {
                this.cap = cap;
                this.seed = seed;
            }
    
            /**
             * 计算 hash 值
             */
            public int hash(Object value) {
                int h;
                return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
            }
    
        }
    }
    

    测试:

    String value1 = "https://javaguide.cn/";
    String value2 = "https://github.com/Snailclimb";
    MyBloomFilter filter = new MyBloomFilter();
    System.out.println(filter.contains(value1));
    System.out.println(filter.contains(value2));
    filter.add(value1);
    filter.add(value2);
    System.out.println(filter.contains(value1));
    System.out.println(filter.contains(value2));
    

    Output:

    false
    false
    true
    true
    

    测试:

    Integer value1 = 13423;
    Integer value2 = 22131;
    MyBloomFilter filter = new MyBloomFilter();
    System.out.println(filter.contains(value1));
    System.out.println(filter.contains(value2));
    filter.add(value1);
    filter.add(value2);
    System.out.println(filter.contains(value1));
    System.out.println(filter.contains(value2));
    

    Output:

    false
    false
    true
    true
    

    利用 Google 开源的 Guava 中自带的布隆过滤器

    自己实现的目的主要是为了让自己搞懂布隆过滤器的原理,Guava 中布隆过滤器的实现算是比较权威的,所以实际项目中我们不需要手动实现一个布隆过滤器。

    首先我们需要在项目中引入 Guava 的依赖:

    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>28.0-jre</version>
    </dependency>
    

    实际使用如下:

    我们创建了一个最多存放 最多 1500 个整数的布隆过滤器,并且我们可以容忍误判的概率为百分之(0.01)

    // 创建布隆过滤器对象
    BloomFilter<Integer> filter = BloomFilter.create(
        Funnels.integerFunnel(),
        1500,
        0.01);
    // 判断指定元素是否存在
    System.out.println(filter.mightContain(1));
    System.out.println(filter.mightContain(2));
    // 将元素添加进布隆过滤器
    filter.put(1);
    filter.put(2);
    System.out.println(filter.mightContain(1));
    System.out.println(filter.mightContain(2));
    

    在我们的示例中,当 mightContain() 方法返回 true 时,我们可以 99%确定该元素在过滤器中,当过滤器返回 false 时,我们可以 100%确定该元素不存在于过滤器中。

    Guava 提供的布隆过滤器的实现还是很不错的(想要详细了解的可以看一下它的源码实现),但是它有一个重大的缺陷就是只能单机使用(另外,容量扩展也不容易),而现在互联网一般都是分布式的场景。为了解决这个问题,我们就需要用到 Redis 中的布隆过滤器了。

    Redis 中的布隆过滤器

    介绍

    Redis v4.0 之后有了 Module(模块/插件) 功能,Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 :https://redis.io/modules

    另外,官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module,地址:https://github.com/RedisBloom/RedisBloom
    其他还有:

    • redis-lua-scaling-bloom-filter(lua 脚本实现):https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
    • pyreBloom(Python 中的快速 Redis 布隆过滤器) :https://github.com/seomoz/pyreBloom

    RedisBloom 提供了多种语言的客户端支持,包括:Python、Java、JavaScript 和 PHP。

    使用 Docker 安装

    如果我们需要体验 Redis 中的布隆过滤器非常简单,通过 Docker 就可以了!我们直接在 Google 搜索 docker redis bloomfilter 然后在排除广告的第一条搜素结果就找到了我们想要的答案(这是我平常解决问题的一种方式,分享一下),具体地址:https://hub.docker.com/r/redislabs/rebloom/ (介绍的很详细 )。

    具体操作如下:

    ➜  ~ docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
    ➜  ~ docker exec -it redis-redisbloom bash
    root@21396d02c252:/data# redis-cli
    127.0.0.1:6379>
    

    常用命令一览

    注意: key : 布隆过滤器的名称,item : 添加的元素。

    1. BF.ADD:将元素添加到布隆过滤器中,如果该过滤器尚不存在,则创建该过滤器。格式:BF.ADD {key} {item}
    2. BF.MADD : 将一个或多个元素添加到“布隆过滤器”中,并创建一个尚不存在的过滤器。该命令的操作方式BF.ADD与之相同,只不过它允许多个输入并返回多个值。格式:BF.MADD {key} {item} [item ...]
    3. BF.EXISTS : 确定元素是否在布隆过滤器中存在。格式:BF.EXISTS {key} {item}
    4. BF.MEXISTS : 确定一个或者多个元素是否在布隆过滤器中存在格式:BF.MEXISTS {key} {item} [item ...]

    另外, BF. RESERVE 命令需要单独介绍一下:

    这个命令的格式如下:

    BF. RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]

    下面简单介绍一下每个参数的具体含义:

    1. key:布隆过滤器的名称
    2. error_rate : 期望的误报率。该值必须介于 0 到 1 之间。例如,对于期望的误报率 0.1%(1000 中为 1),error_rate 应该设置为 0.001。该数字越接近零,则每个项目的内存消耗越大,并且每个操作的 CPU 使用率越高。
    3. capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后,性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长,性能将线性下降。

    可选参数:

    • expansion:如果创建了一个新的子过滤器,则其大小将是当前过滤器的大小乘以expansion。默认扩展值为 2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。

    实际使用

    127.0.0.1:6379> BF.ADD myFilter java
    (integer) 1
    127.0.0.1:6379> BF.ADD myFilter javaguide
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter java
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter javaguide
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter github
    (integer) 0
    
    展开全文
  • 使用java实现布隆过滤器算法,jdk-1.7,使用java实现布隆过滤器算法,jdk-1.7,使用java实现布隆过滤器算法,jdk-1.7,
  • Java 实现的高性能布隆过滤器!.zip,Advanced Bloom Filter Based Algorithms for Efficient Approximate Data De-Duplication in Streams
  • java 实现布隆过滤器

    2021-05-18 10:50:13
    布隆过滤器 在日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的...

    参考

    https://www.jianshu.com/p/7634eaea3e26

    布隆过滤器

    在日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新元素时,将它和集合中的元素直接比较即可。一般来讲,计算机中的集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显著,但是当集合巨大时,哈希表存储效率低的问题就显现出来了。比如说,一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。如果用哈希表,每存储一亿个 email 地址, 就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹 ,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机,一般服务器是无法存储的。
    今天,我们介绍一种称作布隆过滤器的数学工具,它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。
    布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。
    假定我们存储一亿个电子邮件地址,我们先建立一个十六亿二进制(比特),即两亿字节的向量,然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X,我们用八个不同的随机数产生器(F1,F2, …,F8) 产生八个信息指纹(f1, f2, …, f8)。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, …,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。(见下图)
    在这里插入图片描述

    现在,让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器(F1, F2, …, F8)对这个地址产生八个信息指纹 s1,s2,…,s8,然后将这八个指纹对应到布隆过滤器的八个二进制位,分别是 t1,t2,…,t8。如果 Y 在黑名单中,显然,t1,t2,…,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址,我们都能准确地发现。
    布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是,它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中,因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中,误识概率在万分之一以下。
    布隆过滤器的好处在于快速,省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单,存储那些可能别误判的邮件地址。

    使用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分别为不同的值得情况下的假阳性概率:

    书上的表,直接拍下来的
    在这里插入图片描述

    书上的表,直接拍下来的
    在这里插入图片描述

    展开全文
  • 在查redis缓存之前往往先经过布隆过滤器,达到防止缓存穿透的作用 布隆过滤器原理以及优缺点可以看博客 布隆过滤器的原理,优缺点_m0_53611007的博客-CSDN博客_布隆过滤器的优缺点 看代码: /** * @author:...

    在查redis缓存之前往往先经过布隆过滤器,达到防止缓存穿透的作用

    布隆过滤器原理以及优缺点可以看博客

     布隆过滤器的原理,优缺点_m0_53611007的博客-CSDN博客_布隆过滤器的优缺点

    看代码:

    /**
     * @author:yuze
     * @description:我的极简布隆过滤器
     * @data:2022/2/13
     */
    public class MyBloomFilter {
        private int[] bloomFilter = new int[1024];//存放标志的数组
    
        public void add(String key){//添加缓存key的函数
            int hash = key.hashCode() % bloomFilter.length > 0 ? key.hashCode() % bloomFilter.length : -key.hashCode() % bloomFilter.length;//计算hash
            if (bloomFilter[hash] == 1){//当前位置已经为1说明缓存过了
                return ;
            }else {
                bloomFilter[hash] = 1;
                return;
            }
        }
        public boolean findKey(String key){//查看key是否在过滤器中
            int hash = key.hashCode() % bloomFilter.length > 0 ? key.hashCode() % bloomFilter.length : -key.hashCode() % bloomFilter.length;
            if(bloomFilter[hash] == 1){
                return true;
            }
            return false;
        }
    
        public static void main(String[] args) {
            String s = "yuze";
            String s1 = "zhangsan";
            MyBloomFilter bloomFilter = new MyBloomFilter();
            bloomFilter.add(s);
            System.out.println(bloomFilter.findKey(s));
            System.out.println(bloomFilter.findKey(s1));
        }
    }

    结果:

     

    展开全文
  • 布隆过滤器以及java实现

    万次阅读 2019-06-12 11:23:18
    Java实现简单的布隆过滤器 //https://blog.csdn.net/u014653197/article/details/76397037 public class BloomFilter implements Serializable{ private final int[] seeds; private final int size; ...
  • 布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的,布隆过滤器可以用于检索一个元素是否在一个集合中,因此它是一个空间效率极高的概率型算法;它实际上是一个很长的二进制向量和一系列随机映射函数; 优缺点 ...
  • JAVA实现较完善的布隆过滤器

    万次阅读 多人点赞 2017-07-30 17:17:22
    布隆过滤器是可以用于判断一个元素是不是在一个集合里,并且相比于其它的数据结构,布隆过滤器...简单来说,布隆过滤器实现方法就是:利用内存中一个长度为M的位数组B并初始化里面的所有位都为0,如下面的表格所示:
  • 下面小编就为大家带来一篇布隆过滤器(Bloom Filter)的Java实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 主要介绍了JAVA实现较完善的布隆过滤器的示例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 自动清空过滤器内部信息的使用比率,传null则表示不会自动清理,当过滤器使用率达到100%时,则无论传入什么数据,都会认为在数据已经存在了当希望过滤器使用率达到80%时自动清空重新使用,则传入0.8
  • Java实现布隆过滤器

    千次阅读 2020-05-11 15:47:03
    Java 实现布隆过滤器 1.什么是布隆过滤器布隆过滤器(Bloom Filter)是一个叫做 Bloom 的老哥于1970年提出的。 实际上可以把它看作由二进制向量(或者说位数组)和一系列随机映射函数(哈希函数)两部分组成的...
  • java实现布隆过滤器
  • bitmap布隆过滤器实现方式降低布隆过滤器误判率的方式总结布隆过滤器实现方式谷歌Guava实现布隆过滤器基于Redisson的布隆过滤器基于rebloom的布隆过滤器布隆过滤器的使用场景 布隆过滤器是啥? 布隆过滤器是一...
  • 本博文介绍了布隆过滤器的使用场景,以及google布隆过滤器和redis布隆过滤器分别的使用方法。当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在 流量攻击:故意访问不存在的数据,...
  • Java 布隆过滤器

    2021-12-06 21:35:42
    Java 布隆过滤器
  •  * @Description: 简单的布隆过滤器 用户大数据量的有限空间的快速识别  * @author: songqinghu  * @date: 2017年1月6日 下午6:26:42  * Version:1.0  */ public class SimpleBloomFilter {  p
  • 布隆过滤器java

    2021-07-30 22:30:00
    布隆过滤器java) 概述 布隆过滤器概念:https://www.cnblogs.com/liyulong1982/p/6013002.html 布隆过滤器主要用于: 判断数据是否存在(有误判率,但不会出现假反例的情况,即不存在的数据一定会被过滤掉) ...
  • Java redis 模拟布隆过滤器

    千次阅读 2018-12-13 16:21:40
    基本概念 如果想判断一个元素是不是在一个集合里,...首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。   redis对bitmaps的解释: ...
  • Redis实现布隆过滤器(下)Redis4.0通过模块化的形式集成了布隆过滤器,后续通过下面的命令就可以操作布隆过滤器,路径https://redis.io/commands/?group=bf那么我们怎么通过Java代码去操作布隆过滤器呢?...
  • java实现布隆过滤器

    千次阅读 2018-11-25 10:16:51
    之前去头条面试,被问及一个问题,当时直接懵逼:有100亿个url,怎么能过滤出重复的url? 接到这个问题的时候,头一个念头就是拆文件,然后用hashmap,接着转念一想,如果这100亿个url都不重复,那hashmap也不够存,...
  • 布隆过滤器是指通过维护一张散列表对数据进行校验从而快速判定该数据是否存在于表中。在实际应用场景中主要用于预防恶意缓存击穿,一般在频繁查询的场景下,若大量恶意数据强行进行查询则会导致数据库和服务器压力过...
  • 针对该问题,提出了采用Bloom Filter(布隆过滤器)进行字符串模糊匹配方式,利用Bloom Filter将信息流中大部分正常流量过滤掉,从而减轻了后端的字符串精确匹配的压力,降低了系统功耗,大大提高了处理速度。
  • 布隆过滤器原理以及java/redis使用

    千次阅读 2020-08-05 17:55:30
    文章目录布隆过滤器布隆过滤器原理使用场景利用Google开源的 Guava中自带的布隆过滤器Redis 中的布隆过滤器使用Docker安装命令 布隆过滤器 布隆过滤器是用于判断一个元素是否在集合中。通过一个位数组和N个hash函数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,176
精华内容 5,670
关键字:

布隆过滤器java实现

java 订阅
友情链接: 245121viterbi_decoder.rar