布隆过滤器

布隆过滤器解决的问题是:在大量数据中,判断一个元素是否存在,并且能够容忍存在较小的误判。

该算法的核心是一个比特数组和 K 个不同的 Hash 函数[1]

Bloom Filter

如图,一共有 3 个 Hash 函数。初始化的时候,将整个数组都置为 0。

添加元素

对于xx 元素,计算 3 次 Hash 函数得到 3 个 HashCode,并将数组中对应的位置上的比特置为 1 即可。

查询元素

对于ww 元素,同样是得到 3 个 HashCode,如果这 3 个位置上的数字都是 1,那么说明该元素存在。很明显这里会出现误判,因为其他数字的组合可能正好也等于ww 计算出来的 HashCode,后面会计算错误率是多少。

删除元素

如果是上面说的数组,是无法删除元素的,因为会影响到其他元素。目前有的改进方案是将数组改成计数,然后删除的话把对应位置的数字减去 1 即可[2]

误判率

假设 Hash 函数是等概率的取数组中的某一个点,数组的大小是 m,Hash 函数的个数是 k 个。

插入一个值时,某一位没有被选中的概率是:

11m1 - \frac{1}{m}

计算一个数,得到 K 个 HashCode,那么插入一个数,某一位没有被置为 1 的概率是:

(11m)k\left(1 - \frac{1}{m}\right)^k

插入了 n 个数,某一位没有被置为 1 的概率是:

(11m)n×k\left(1 - \frac{1}{m}\right)^{n\times k}

插入了 n 个数,某一位被置为 1 的概率是:

1(11m)n×k1 - \left(1 - \frac{1}{m}\right)^{n\times k}

新来的一个数字ww 被错误的以为已经存在数组的概率是:

(1(11m)n×k)k(1eknm)k\left(1 - \left(1 - \frac{1}{m}\right)^{n\times k}\right)^k \approx \left(1 - \mathrm{e}^{\frac{-kn}{m}}\right)^k

在给定mmnn 的情况下,对上面的公式求导易得,当k=mnln2k = \frac{m}{n}\ln2 的时候错误率最小。

Bloom_filter_fp_probability.svg


  1. Bloom Filter ↩︎

  2. Counting Filters ↩︎

0%