目录

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

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

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

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

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

  • 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。

  • 根据得到的哈希值，在位数组中把对应下标的值置为 1。
    当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：

  • 对给定元素再次进行相同的哈希计算；

  • 得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

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

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

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

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

  • 判断给定数据是否存在：比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，5亿以上！）、 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤、黑名单功能等等。
  • 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。
  1. import java.util.BitSet;
  3. public class MyBloomFilter {
  5.     /**
  6.      * 位数组的大小
  7.      */
  8.     private static final int DEFAULT_SIZE = 2 << 24;
  9.     /**
  10.      * 通过这个数组可以创建 6 个不同的哈希函数
  11.      */
  12.     private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
  14.     /**
  15.      * 位数组。数组中的元素只能是 0 或者 1
  16.      */
  17.     private BitSet bits = new BitSet(DEFAULT_SIZE);
  19.     /**
  20.      * 存放包含 hash 函数的类的数组
  21.      */
  22.     private SimpleHash[] func = new SimpleHash[SEEDS.length];
  24.     /**
  25.      * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
  26.      */
  27.     public MyBloomFilter() {
  28.         // 初始化多个不同的 Hash 函数
  29.         for (int i = 0; i < SEEDS.length; i++) {
  30.             func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
  31.         }
  32.     }
  34.     /**
  35.      * 添加元素到位数组
  36.      */
  37.     public void add(Object value) {
  38.         for (SimpleHash f : func) {
  39.             bits.set(f.hash(value), true);
  40.         }
  41.     }
  43.     /**
  44.      * 判断指定元素是否存在于位数组
  45.      */
  46.     public boolean contains(Object value) {
  47.         boolean ret = true;
  48.         for (SimpleHash f : func) {
  49.             ret = ret && bits.get(f.hash(value));
  50.         }
  51.         return ret;
  52.     }
  54.     /**
  55.      * 静态内部类。用于 hash 操作！
  56.      */
  57.     public static class SimpleHash {
  59.         private int cap;
  60.         private int seed;
  62.         public SimpleHash(int cap, int seed) {
  63.             this.cap = cap;
  64.             this.seed = seed;
  65.         }
  67.         /**
  68.          * 计算 hash 值
  69.          */
  70.         public int hash(Object value) {
  71.             int h;
  72.             return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
  73.         }
  75.     }
  76. }

版权声明：本文为xhj928675426原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/xhj928675426/p/14589443.html