常见的数据结构和算法 (3)

(1) 网页黑名单系统，垃圾邮件过滤系统，爬虫的网址判断重复系统，容忍一定程度的失误率，但对空间要求较严格 。
布隆过滤器：可精确地代表一个集合；可精确判断某一元素是否在此集合中；精确程度由用户的具体设计决定；做到100%的精确即正确是不可能的。 布隆过滤器的优势在于，利用很少的空间可以做到精确率较高。

布隆过滤器的bitarray大小如何确定？
大小为m(过小)，样本数量为n(相较于m过大)，失误率为p(过大)。

举例输入：n = 100亿，p = 0.01%

1

1. m = - n x lnp / (ln2) 2 得到m = 19.19n 向上取整为20n，2000亿bit，约为25G。 2. k = ln2 x m/n = 0.7 x m/n = 14 因此需要14个彼此独立的哈希函数。 3. 此时失误率为(1 - e -nk/m) k = 0.006%，其中m = 20n, k = 14。