布隆过滤器简介

hiyayiji 发布于2019-08-08 14:04 / 1031人阅读

摘要：布隆过滤器可以用于检索一个元素是否在一个集合中。举个栗子，比如第一次将存入布隆过滤器，将数组的，位置置为了，只要下次再有存入布隆过滤器，发现已经是全是了，所以可知该字符串已经保存过。

最近做爬虫项目过滤重复的url的时候,了解到一个东西,叫布隆过滤器,然后也学习了一下,写下这篇博客记录一下.
下面我们将分为几个专题来介绍布隆过滤器:
1.什么是布隆过滤器;
2.布隆过滤器的使用场景和缺陷;
3.布隆过滤器java实现;
4.guava中使用布隆过滤器;
5.布隆过滤器的变体

1.什么是布隆过滤器?

首先我们得知道布隆过滤器的概念是什么,采自wiki百科:
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
tips:看完这个我们可以知道是一个叫布隆的人提出的一个用来检索一个元素是否在一个集合中的算法，效率高，性能好。

1.1 图解布隆过滤器

很长的二进制向量（这里可以理解为很长的bit数组）

一系列的随机映射函数（hash函数）

如图所示，将一个字符串存入布隆过滤器的时候，这个字符串会先被多个hash函数生成不同的hash值，然后在对应的bit数组的位置，将0置为1（bit数组初始化的时候，全部位置都是0）；然后第二次在有相同的字符串存入的时候，因为之前已经对应的位置都被置为1了，所以可以很轻松的知道这个值已经存在了。
举个栗子，比如第一次将abc@gmail.com存入布隆过滤器，将bit数组的1，3,5位置置为了1，只要下次再有abc@gmail.com存入布隆过滤器，发现1,3,5已经是全是1了，所以可知该字符串已经保存过。（简单来说就是bit数组中对应的值只要全是1就存在，其他情况就是不存在，但是因为存在hash冲突，所以会有误判，有可能存在abc和xyz的hash值在bit数组中映射的位置是相同的。这种情况我们可以增加班名单，或者调整hash函数来减少误判情况。）

2.布隆过滤器的使用场景

知道了布隆过滤器的概念，我们再来看看在实际工作中，它主要使用在哪些地方。

2.1使用场景：

1.网络爬虫可以通过布隆过滤器判断当前的url是否已经爬取过；

2.防止恶意链接或者垃圾邮件，短信之类的，从数十亿个链接或者垃圾邮件中判断该链接（邮件发件人，短信发信人是否是在黑名单中），
平时手机上来电提示写着对方式恶意推销，外卖，这种场景也是可以用布隆过滤器来判断；

3.防止缓存击穿，将已存在的缓存放到布隆中，当使用缓存的时候，可以先访问布隆过滤器，存在则访问缓存，不存在则访问数据库；

4.检索系统查询当前的输入信息是否存在于数据库中，也可以使用布隆过滤器。

3.布隆过滤器java实现

public class BloomFilter {


    /**
     * bitSet的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 选取的hash函数
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * bitSet每一位只能是true或false  其实就是bit数组说的0或者1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    public static void main(String[] args) {
        String value = "wxwwt@gmail.com";
        BloomFilter filter = new BloomFilter();
        System.out.println(filter.contains(value));
        filter.add(value);
        System.out.println(filter.contains(value));
    }

    public BloomFilter() {
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    public void add(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    public static class SimpleHash {

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 计算hash值
         *
         * @param value
         * @return
         */

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }

    }
}

4.使用guava带的布隆过滤器

google的java工具包中已经编写了布隆过滤器的代码，可以直接拿来用，具体使用可以google一下，这里只简单的提一下：

public static void main(String[] args) {
      // 创建布隆过滤器
      BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 1000);

      // 添加数据
      for (int index = 0; index < 100000; index++) {
          bloomFilter.put("wxwwt-" + index);
      }

      //  查看数据是否存在
      if (bloomFilter.mightContain("wxwwt-" + 9999)) {
          System.out.println("存在");
      }
      // 误判元素
      if (bloomFilter.mightContain("不存在的元素")) {
          System.out.println("误判啦");
      } else {
          System.out.println("不存在");
      }
  }

运行结果：

5.总结：

在数据量很大的时候使用布隆过滤器非常方便，占用的内存空间很小（因为使用的是bit数组，空间使用非常小，空间开销就是bit数组的大小），查询效率也很高（直接通过计算hash函数的出来的），唯一的问题就是可能会有误判，不过概率也是比较小的，也可以通过增加白名单和增加hash函数的数量来减少这个问题的产生，总的来说利大于弊，在仅判断元素是否存在而不涉及到删除的情况下非常好用（最基本的bloomfilter是无法删除元素的，置为0就没法判断存在情况了，有bloom过滤器的变体是支持删除的）。

参考资料：

1.https://nick-weixx.github.io/...
2.https://zh.wikipedia.org/wiki...
3.https://zhangluncong.com/2018...

专线服务私有云布隆过滤器布隆去重使用简介函数简介

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/63757.html

布隆过滤器简介

摘要：布隆过滤器可以用于检索一个元素是否在一个集合中。举个栗子，比如第一次将存入布隆过滤器，将数组的，位置置为了，只要下次再有存入布隆过滤器，发现已经是全是了，所以可知该字符串已经保存过。最近做爬虫项目过滤重复的url的时候,了解到一个东西,叫布隆过滤器,然后也学习了一下,写下这篇博客记录一下.下面我们将分为几个专题来介绍布隆过滤器:1.什么是布隆过滤器;2.布隆过滤器的使用场景和...

Vixb 2019-08-01 13:57 评论0 收藏0
布隆过滤器简介

摘要：布隆过滤器可以用于检索一个元素是否在一个集合中。举个栗子，比如第一次将存入布隆过滤器，将数组的，位置置为了，只要下次再有存入布隆过滤器，发现已经是全是了，所以可知该字符串已经保存过。最近做爬虫项目过滤重复的url的时候,了解到一个东西,叫布隆过滤器,然后也学习了一下,写下这篇博客记录一下.下面我们将分为几个专题来介绍布隆过滤器:1.什么是布隆过滤器;2.布隆过滤器的使用场景和...

shuibo 2019-08-16 17:30 评论0 收藏0
大白话布隆过滤器

摘要：可以看出，仅仅从布隆过滤器本身而言，根本没有存放完整的数据，只是运用一系列随机映射函数计算出位置，然后填充二进制向量。也就是说布隆过滤器只能判断数据是否一定不存在，而无法判断数据是否一定存在。我向布隆过滤器插入了，然后用来测试误判率。本文是站在小白的角度去讨论布隆过滤器，如果你是科班出身，或者比较聪明，又或者真正想完全搞懂布隆过滤器的可以移步。不知道从什么时候开始，本来默默无闻的布隆过滤器...

meteor199 2019-05-23 16:22 评论0 收藏0
布隆过滤器的Python实现(标准、计数、标准扩容、计数扩容)

摘要：布隆过滤器的实现，包括标准计数标准扩容计数扩容。计数扩容布隆过滤器标准扩容布隆过滤器的子类，功能继承自标准扩容布隆过滤器，但支持删除元素的操作。 bloompy github:bloompy 布隆过滤器的Python3实现，包括标准、计数、标准扩容、计数扩容。更新自pybloom。安装 pip install bloompy 使用通过bloompy你可以使用四种布隆过滤器标准布...

Pocher 2019-07-30 18:35 评论0 收藏0
说一说布隆过滤器

摘要：介绍布隆过滤器在上的介绍布隆过滤器是年由布隆提出的。通过介绍已经知晓布隆过滤器的作用是检索一个元素是否在集合中。控制布隆过滤器的误判率如果集合的大小相比于输入对象的个数过小，失误率就会变高。介绍布隆过滤器在wiki上的介绍: 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集...

terasum 2019-08-16 12:38 评论0 收藏0