布隆过滤器的实现

╰+哭是因爲堅強的太久メ 2022-11-07 04:12 166阅读 0赞

## 布隆过滤器的实现 ##

1.原理请参考：https://blog.csdn.net/jiaomeng/article/details/1495500

#### java实现 ####

package com.ls.data.bloom;
    
    import java.util.BitSet;
    
    /** * Created by ls on 2021/3/9. * * @desc: 布隆过滤器的实现 */
    public class MyBloomFilter { 
    
      // 初始化BitSet的大小
      private static final int DEFAULT_SIZE = 2 << 24;
    
      // 使用质数数组
      private static final int[] ARR = { 5, 7, 11, 13, 31, 37, 61};
    
      private static final BitSet BIT_SET = new BitSet(DEFAULT_SIZE);
    
      public static boolean check(Object value) { 
        if (null == value) { 
          return false;
        }
        boolean flag = true;
        for (int ar : ARR) { 
          flag = flag && BIT_SET.get(hash(value, ar));
        }
        return flag;
      }
    
    
      public static void add(Object value) { 
    
        for (int ar : ARR) { 
          BIT_SET.set(hash(value, ar), true);
        }
      }
    
    
      private static int hash(Object value, int item) { 
        int ha;
        item = item * (DEFAULT_SIZE - 1);
        return (value == null) ? 0 : (item & ((ha = value.hashCode()) ^ (ha >>> 16)));
      }
    
      
      public static void main(String[] args) { 
        MyBloomFilter bloomFilter = new MyBloomFilter();
        bloomFilter.add("张学友");
        System.out.println(bloomFilter.check("张学友"));
        System.out.println(bloomFilter.check("刘德华"));
    
    //插入数据
        for (int i = 0; i < 10000000; i++) { 
          bloomFilter.add(i);
        }
        int count = 0;
        for (int i = 10000000; i < 20000000; i++) { 
          if (bloomFilter.check(i)) { 
            count++;
            System.out.println(i + "误判了");
          }
        }
        System.out.println("总共的误判数:" + count);
      }
    }

#### Guava的实现 ####

/** * Created by ls on 2021/3/9. * * @desc: */
    public class GuavaBloomTest { 
    
      private static int size = 100000000;//预计要插入多少数据
    
      private static double fpp = 0.00001;//期望的误判率
    
      private static BloomFilter<Integer> bloomFilter = BloomFilter
          .create(Funnels.integerFunnel(), size, fpp);
    
      public static void main(String[] args) { 
    //插入数据
        for (int i = 0; i < 10000000; i++) { 
          bloomFilter.put(i);
        }
        int count = 0;
        for (int i = 10000000; i < 20000000; i++) { 
          if (bloomFilter.mightContain(i)) { 
            count++;
            System.out.println(i + "误判了");
          }
        }
        System.out.println("总共的误判数:" + count);
      }
    
    }

#### redis的实现 ####

setbit key offset value

![在这里插入图片描述][20210310220009565.png]

getbit key offset

![在这里插入图片描述][20210310220035217.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70]  
参考：https://www.cnblogs.com/ysocean/p/12594982.html

[20210310220009565.png]: /images/20221023/b79f6e03a13f48249d2a52e794c41484.png
[20210310220035217.png]: /images/20221023/836a882ad8654a49998c7a497a627cd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMTk4MDA0_size_16_color_FFFFFF_t_70]: /images/20221023/feadd481134c424fb42487e82f58fa34.png