如何在亿级数据中判断一个元素是否存在?

前言

在日常工作中,经常要判断一个元素是否在一个集合中。假设你要向浏览器添加一项功能,该功能可以通知用户输入的网址是否是恶意网址,此时你手上有大约 1000 万个恶意 URL 的数据集,你该如何实现该功能。按我之前的思维,要判断一个元素在不在当前的数据集中,首先想到的就是使用 hash table,通过哈希函数运行所有的恶意网址以获取其哈希值,然后创建出一个哈希表(数组)。这个方案有个明显的缺点,就是需要存储原始元素本身,内存占用大,而我们其实主要是关注 当前输入的网址在不在我们的恶意 URL 数据集中,也就是之前的恶意 URL 数据集的具体值是什么并不重要,通过吴军老师的《数学之美》了解到,对于这种场景大数据领域有个用于在海量数据情况下判断某个元素是否已经存在的算法很适合,关键的一点是该算法并不存储元素本身,这个算法就是 — 布隆过滤器(Bloom filter)。

原理

布隆过滤器是由巴顿.布隆于一九七零年提出的,在 维基百科 中的描述如下:

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set.


布隆过滤器是一个数据结构,它可以用来判断某个元素是否在集合内,具有运行快速,内存占用小的特点,它由一个很长的二进制向量和一系列随机映射函数组成。而高效插入和查询的代价就是,它是一个基于概率的数据结构,只能告诉我们一个元素绝对不在集合内,布隆过滤器的好处在于快速,省空间,但是有一定的误判率。布隆过滤器的基础数据结构是一个比特向量,假设有一个长度为 16 的比特向量,下面我们通过一个简单的示例来看看其工作原理,:

bloom-filter-bit-array.png

上图比特向量中的每一个空格表示一个比特, 空格下面的数字表示当前位置的索引。只需要简单的对输入进行多次哈希操作,并把对应于其结果的比特置为 1,就完成了向 Bloom filter 添加一个元素的操作。下图表示向布隆过滤器中添加元素 https://www.mghio.cnhttps://www.abc.com 的过程,它使用了 func1func2 两个简单的哈希函数。

bloom-filter-add-item.png

当我们往集合里添加一个元素的时候, 可以检查该元素在应用对应哈希函数后的哈希值对比特向量的长度取余后的位置是否为 1,图中用 1 表示最新添加的元素对应位置。然后当我们要判断添加元素是否存在集合中的话,只需要简单的通过对该元素应用同样的哈希函数,然后看比特向量里对应的位置是否为 1 的方式来判断一个元素是否在集合里。如果不是,则该元素一定不再集合中,但是需要注意的是,如果是,你只知道元素可能在里面, 因为这些对应位置有可能恰巧是由其它元素或者其它元素的组合所引起的。以上就是布隆过滤器的实现原理。

如何自己实现

布隆过滤器的思想比较简单,首先在构造方法中初始化了一个指定长度的 int 数组,在添加元素的时候通过哈希函数 func1func2 计算出对应的哈希值,对数组长度取余后将对应位置置为 1,判断元素是否存在于集合中时,同样也是对元素用同样的哈希函数进行两次计算,取到对应位置的哈希值,只要存在位置的值为 0,则认为元素不存在。下面使用 Java 语言实现了上面示例中简单版的布隆过滤器:

public class BloomFilter {

  /**
   * 数组长度
   */
  private int size;

  /**
   * 数组
   */
  private int[] array;

  public BloomFilter(int size) {
    this.size = size;
    this.array = new int[size];
  }

  /**
   * 添加数据
   */
  public void add(String item) {
    int firstIndex = func1(item);
    int secondIndex = func2(item);
    array[firstIndex % size] = 1;
    array[secondIndex % size] = 1;
  }

  /**
   * 判断数据 item 是否存在集合中
   */
  public boolean contains(String item) {
    int firstIndex = func1(item);
    int secondIndex = func2(item);
    int firstValue = array[firstIndex % size];
    int secondValue = array[secondIndex % size];
    return firstValue != 0 && secondValue != 0;
  }

  /**
   * hash 算法 func1
   */
  private int func1(String key) {
    int hash = 7;
    hash += 61 * hash + key.hashCode();
    hash ^= hash >> 15;
    hash += hash << 3;
    hash ^= hash >> 7;
    hash += hash << 11;
    return Math.abs(hash);
  }

  /**
   * hash 算法 func2
   */
  private int func2(String key) {
    int hash = 7;
    for (int i = 0, len = key.length(); i < len; i++) {
      hash += key.charAt(i);
      hash += (hash << 7);
      hash ^= (hash >> 17);
      hash += (hash << 5);
      hash ^= (hash >> 13);
    }
    return Math.abs(hash);
  }
} 

自己实现虽然简单但是有一个问题就是检测的误判率比较高,通过其原理可以知道,可我们可以提高数组长度以及 hash 计算次数来降低误报率,但是相应的 CPU、内存的消耗也会相应的提高;这需要我们根据自己的业务需要去权衡选择。

扎心一问

哈希函数该如何设计?

布隆过滤器里的哈希函数最理想的情况就是需要尽量的彼此独立且均匀分布,同时,它们也需要尽可能的快 (虽然 sha1 之类的加密哈希算法被广泛应用,但是在这一点上考虑并不是一个很好的选择)。

布隆过滤器应该设计为多大?

个人认为布隆过滤器的一个比较好特性就是我们可以修改过滤器的错误率。一个大的过滤器会拥有比一个小的过滤器更低的错误率。假设在布隆过滤器里面有 k 个哈希函数,m 个比特位(也就是位数组长度),以及 n 个已插入元素,错误率会近似于 (1-ekn/m)k,所以你只需要先确定可能插入的数据集的容量大小 n,然后再调整 k 和 m 来为你的应用配置过滤器。

应该使用多少个哈希函数?

显然,布隆过滤器使用的哈希函数越多其运行速度就会越慢,但是如果哈希函数过少,又会遇到误判率高的问题。所以这个问题上需要认真考虑,在创建一个布隆过滤器的时候需要确定哈希函数的个数,也就是说你需要提前预估集合中元素的变动范围。然而你这样做了之后,你依然需要确定比特位个数和哈希函数的个数的值。看起来这似乎这是一个十分困难的优化问题,但幸运的是,对于给定的 m(比特位个数)和 n(集合元素个数),最优的 k(哈希函数个数)值为: (m/n)ln(2)(PS:需要了解具体的推导过程的朋友可以参考维基百科)。也就是我们可以通过以下步骤来确定布隆过滤器的哈希函数个数:

  1. 确定 n(集合元素个数)的变动范围。
  2. 选定 m(比特位个数)的值。
  3. 计算 k(哈希函数个数)的最优值

对于给定的 n、m 和 k 计算错误率,如果这个错误率不能接受的话,可以继续回到第二步。

布隆过滤器的时间复杂度和空间复杂度?

对于一个 m(比特位个数)和 k(哈希函数个数)值确定的布隆过滤器,添加和判断操作的时间复杂度都是 O(k),这意味着每次你想要插入一个元素或者查询一个元素是否在集合中,只需要使用 k 个哈希函数对该元素求值,然后将对应的比特位标记或者检查对应的比特位即可。

总结

布隆过滤器的实际应用很广泛,特别是那些要在大量数据中判断一个元素是否存在的场景。可以看到,布隆过滤器的算法原理比较简单,但要实际做一个生产级别的布隆过滤器还是很复杂的,谷歌的开源库 GuavaBloomFilter 提供了 Java 版的实现,用法很简单。最后留给大家一个问题:布隆过滤器支持元素删除吗?

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

推荐阅读更多精彩内容