本文还是对《区块链：原理、设计与应用》的一个基础技术的总结和摘录。

散列的本质，是把任意内容，映射成固定长度的内容域里的某一个内容。

布隆过滤器的本质，是在常数时间内回答，“一个元素是否在一个集合内”的问题。

直观的方法及其缺陷

假设我们总可以把任意内容映射到某一个数组的 item 上，那么只要看看那个数组的 item 是否为空，就可以确认某一个内容是否存在。然而现实之中，一个数组总是会产生冲突，操作性能会因为局部冲突而产生退化。

多重散列的布隆过滤器

布隆过滤器的原理很简单，就是插入元素时，在一个容量为 m 的bit数组上， 用 k 个散列函数对一个输入标记 k 个 bit，而查找元素时，再用 k 个散列函数来寻找 k 个 bit，若这 k 个 bit 都被标记过了，则这个内容存在。

普通的布隆过滤器是不应该支持删除的，因为删除一个 bit 可能顺便删除掉其他内容的 bit。但如果把 bit 换成一个计数器，那么就可以考虑删除了。这也就会产生 counter bloom filter。

当hash函数个数k=(ln2)*(m/n)时错误率最小。

实际上，不管是散列算法，还是布隆过滤器，基本思想是一致的，都是基于内容的编址。Hash 函数存在冲突，布隆过滤器同样存在冲突。这就造成了两种方法都存在着假阳性误报问题（false positive），但绝不会存在假阴性漏报的问题（false negative）。布隆过滤器的误报率比单纯的散列算法低得多。

一个布隆过滤器相关的面试题

问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。