• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

布隆过滤器(Bloom Filter)的原理和实现

admin

11月 28, 2021

 

前言

看下下面几个问题:

  • 字处理软件中,需要检查一个英语单词是否拼写正确
  • 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上
  • 在网络爬虫里,一个网址是否被访问过
  • yahoo, gmail等邮箱垃圾邮件过滤功能

以上这些场景有个共同的问题:如何查看一个东西是否在有大量数据的池子里。

Bloom Filter介绍

  • 一个很长的二进制向量 (位数组)
  • 一系列随机函数 (哈希)
  • 空间效率和查询效率高
  • 不会漏判,但是有一定的误判率(哈希表是精确匹配)

原理

布隆过滤器(Bloom Filter)的核心实现是一个超大的bit数组和几个hash函数

假设:位数组的长度为m,哈希函数的个数为k 。

 

以上图为例,具体的操作流程:

  1. 假设集合里面有3个元素{x, y, z},哈希函数的个数为3。
  2. 首先将位数组进行初始化,将里面每个位都设置位0。
  3. 对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。
  4. 查询W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点。
  5. 如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。
  6. 反之,如果3个点都为1,则该元素可能存在集合中。

注意:此处不能判断该元素是否一定存在集合中,可能存在一定的误判率。

可以从图中可以看到:假设某个元素通过映射对应下标为4,5,6这3个点。

虽然这3个点都为1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都是1,这是误判率存在的原因。

添加元素

  • 将要添加的元素给k个哈希函数
  • 得到对应于位数组上的k个位置
  • 将这k个位置设为1

查询元素

  • 将要查询的元素给k个哈希函数
  • 得到对应于位数组上的k个位置
  • 如果k个位置有一个为0,则肯定不在集合中
  • 如果k个位置全部为1,则可能在集合中

简易实现

 

import java.util.BitSet;


public class SimpleBloomFilter {

    private static final int DEFAULT_SIZE = 2 << 24;
    private static final int[] seeds = new int[] {7, 11, 13, 31, 37, 61,};

    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public static void main(String[] args) {
        String value = " [email protected] ";
        SimpleBloomFilter filter = new SimpleBloomFilter();
        System.out.println(filter.contains(value));
        filter.add(value);
        System.out.println(filter.contains(value));
    }

    public SimpleBloomFilter() {
        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;
        }

        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;
        }

    }
}

发表评论

您的电子邮箱地址不会被公开。