位运算相关知识

网页黑名单系统 垃圾软件过滤系统 爬虫的网址判断重复系统 容易一定程度的失误率 对空间要求严格

布隆过滤器： 布隆过滤器可精确代表一个集合，可精确判断某一元素是否在此集合中 精确程度由用户的具体设计决定 做到%100精确是不可能的

布隆过滤器的优势在于，利用很到的空间可以做到准确率较高 如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。 Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。

布隆过滤器的生成过程： 1、注意到题目允许有一定程度的失误率 2、根据样本个数n，和允许的失误率p，结合一下公式 m=−n∗lnp(ln2)2 $$m=-/frac{n*lnp}{(ln2)^2}$$ 求出m 3、根据已经求得的m，以及以下公式： k=ln2∗mn=0.7∗mn $$k=ln2*/frac{m}{n}=0.7*/frac{m}{n}$$ 求得哈希函数的个数k 4 根据向上取整后的m，n，k根据一下公式： (1−e−nkm)k $$(1-e^{-/frac{nk}{m}})^k$$ 求得真实的失误率p。 布隆过滤器较详细介绍和公式推导