布隆过滤器

本来只是作为笔记的，还是和大家分享下吧 O.O

简单写下听课记录，没有具体的实现。

如果面试官问道这种分布式抗压问题，可以先扯一下hash分流，如果他说太耗内存，然后可以问他可不可以允许一部分的失误率，如果可以，就可以讲布隆过滤器了。

前导知识：

进来一个url，现在需要检查它是否在黑名单中存在，存在就返回true

假设有个黑名单url有100亿个url，假设每个url有64个字节，辣么如果使用hash至少需要在内存中放6400亿个字节。这个开销太大了，引入布隆过滤器，假设我定义的是int数组，辣么一个int就4字节，一个字节就是8位，也就是一个int就是32位。每一位都可以表示0，1，这个没问题

现在准备k个hash函数，黑名单中的url都用这些hash函数算出位置，然后将这个位置的0改为1，也就是左肾所说的描黑，然后要判断的那个url也用同样的方法算出来，如果每一个位置都被描黑，说明这个url在这个黑名单中。

失误率：在黑名单中的url一定可以得出正确结果，而不在黑名单中的url有一定的可能性也误认为也在这个黑名单中

公式：看图

1：m表示内存开多大(多少位)，n表示样本量，比如上面提到的100亿，p表示预期失误率，也就是面试官给你说的允许多少的失误率

2：k表示hash函数的个数，比如经典的13个，计算之后向上取整

3：w表示真实失误率