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

一、应用场景

  • 网页爬虫对 URL 去重,避免爬取相同的 URL 地址;

  • 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱;

  • Google Chrome 使用布隆过滤器识别恶意 URL;

  • Medium 使用布隆过滤器避免推荐给用户已经读过的文章;

  • Google BigTable,Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。除了上述的应用场景之外,布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据,这样每次服务调用都会到数据库中进行查询,如果这类请求比较多的话,就会导致数据库压力增大,这样缓存就失去了意义。

  • 字处理软件中,需要检查一个英语单词是否拼写正确

  • 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上

  • 利用布隆过滤器我们可以预先把数据查询的主键,比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候,我们先判断该 ID 是否存在,若存在的话,则进行下一步处理。若不存在的话,直接返回,这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决,我们只能将其控制在一个可以容忍的范围内

二、原理分析

1、简介

  • 是一个很长的二进制向量和一系列随机映射函数

  • 空间效率和查询时间都比一般的算法要好的多

  • 不会漏判,但是有一定的误判率(哈希表是精确匹配)

2、原理

  • 若将大数据量放到array中 那么查询某一个值 需要遍历所有的元素

  • 若将一个值进行hash计算定位到某一个索引 然后将该值放到该索引里 查询某一个值时可以直接从计算出来的索引位置找 提高索引效率

  • hash表是单个函数 只能对应一个索引位置 而布隆过滤器对应多个函数 将对应多个索引位置

简述流程

假设集合里面有3个元素{x, y, z},哈希函数的个数为3。

首先将位数组进行初始化,将里面每个位都设置位0。

对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。

查询W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点。

如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。

反之,如果3个点都为1,则该元素可能存在集合中。

注意:此处不能判断该元素是否一定存在集合中,可能存在一定的误判率。可以从图中可以看到:假设某个元素通过映射对应下标为4,5,6这3个点。虽然这3个点都为1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都是1,这是误判率存在的原因

3、误判率

a、为什么存在误判率?

当值为semlinker时 计算的索引为 2、4、6

当值为semlinker时 计算的索引为 3、4、7

当值为fullstack时 计算的索引为 2、3、7

相应的索引位都被置为 1,这意味着我们可以说 ”fullstack“ 可能已经插入到集合中

b、误判率可以预测?

  • n 是已经添加元素的数量

  • k 哈希的次数

  • m 布隆过滤器的长度(如比特数组的大小)

布隆过滤器的长度 m 可以根据给定的误判率(FFP)的和期望添加的元素个数 n 的通过如下公式计算

结论:

当我们搜索一个值的时候,若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“,那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“,则只能说该搜索的值可能存在集合中

三、实战练习

1、 Guava 库就提供了布隆过滤器

布隆过滤器有很多实现和优化,由 Google 开发著名的 Guava 库就提供了布隆过滤器(Bloom Filter)的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器,只需要引入以下坐标:

<dependency>

<groupId>com.google.guava</groupId>

<artifactId>guava</artifactId>

<version>28.0-jre</version>

</dependency>

在导入 Guava 库后,我们新建一个 BloomFilterDemo 类,在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器,接着我们初始化 1 百万条数据到过滤器中,然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中

package com.jeesite.test.bloom;import com.google.common.base.Charsets;import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;/** * Created by ferrari.meng on 14/04/2020. * @公众号 平凡人笔记 * @author mengfanxiao * @date 2020/04/14 */public class BloomFilterDemo {
public static void main(String[] args) {
int total = 1000000; // 总数量 BloomFilter<CharSequence> bf =
BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total); // 初始化 1000000 条数据到过滤器中 for (int i = 0; i < total; i++) {
bf.put("" + i); }
// 判断值是否存在过滤器中 int count = 0; for (int i = 0; i < total + 10000; i++) {
if (bf.mightContain("" + i)) {
count++; }
}
System.out.println("已匹配数量 " + count); }
}

以上代码运行后,控制台会输出以下结果:

已匹配数量 1000309

很明显以上的输出结果已经出现了误报,因为相比预期的结果多了 309 个元素,误判率为:

309/(1000000 + 10000) * 100 ≈ 0.030594059405940593

如果要提高匹配精度的话,我们可以在创建布隆过滤器的时候设置误判率 fpp:

BloomFilter<CharSequence> bf = BloomFilter.create(  Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002 );

在 BloomFilter 内部,误判率 fpp 的默认值是 0.03:

// com/google/common/hash/BloomFilter.class public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {  return create(funnel, expectedInsertions, 0.03D); }

在重新设置误判率为 0.0002 之后,我们重新运行程序,这时控制台会输出以下结果:

已匹配数量 1000003

通过观察以上的结果,可知误判率 fpp 的值越小,匹配的精度越高。当减少误判率 fpp 的值,需要的存储空间也越大,所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

2、简易版布隆过滤器

package com.jeesite.test.bloom;import java.util.BitSet;/** * Created by ferrari.meng on 14/04/2020. * @公众号 平凡人笔记 * @author mengfanxiao * @date 2020/04/14 */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 = "test@qq.com"; 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; }

}}
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,132评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,802评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,566评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,858评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,867评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,695评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,064评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,705评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,915评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,677评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,796评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,432评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,041评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,992评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,223评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,185评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,535评论 2 343

推荐阅读更多精彩内容