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

布隆过滤器(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;
  2. public class MyBloomFilter {
  3. /**
  4. * 位数组的大小
  5. */
  6. private static final int DEFAULT_SIZE = 2 << 24;
  7. /**
  8. * 通过这个数组可以创建 6 个不同的哈希函数
  9. */
  10. private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
  11. /**
  12. * 位数组。数组中的元素只能是 0 或者 1
  13. */
  14. private BitSet bits = new BitSet(DEFAULT_SIZE);
  15. /**
  16. * 存放包含 hash 函数的类的数组
  17. */
  18. private SimpleHash[] func = new SimpleHash[SEEDS.length];
  19. /**
  20. * 初始化多个包含 hash 函数的类的数组,每个类中的 hash 函数都不一样
  21. */
  22. public MyBloomFilter() {
  23. // 初始化多个不同的 Hash 函数
  24. for (int i = 0; i < SEEDS.length; i++) {
  25. func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
  26. }
  27. }
  28. /**
  29. * 添加元素到位数组
  30. */
  31. public void add(Object value) {
  32. for (SimpleHash f : func) {
  33. bits.set(f.hash(value), true);
  34. }
  35. }
  36. /**
  37. * 判断指定元素是否存在于位数组
  38. */
  39. public boolean contains(Object value) {
  40. boolean ret = true;
  41. for (SimpleHash f : func) {
  42. ret = ret && bits.get(f.hash(value));
  43. }
  44. return ret;
  45. }
  46. /**
  47. * 静态内部类。用于 hash 操作!
  48. */
  49. public static class SimpleHash {
  50. private int cap;
  51. private int seed;
  52. public SimpleHash(int cap, int seed) {
  53. this.cap = cap;
  54. this.seed = seed;
  55. }
  56. /**
  57. * 计算 hash 值
  58. */
  59. public int hash(Object value) {
  60. int h;
  61. return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
  62. }
  63. }
  64. }

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