布隆过滤器用少量的误报换来了极小的内存占用

当集合中的条目数量巨大时，存储每个键是不可能的，但你仍然需要知道某个东西是否在集合中。布隆的例子是一个50万词的词典，其中只有10%的词使用昂贵的连字符规则：合理的检查是避免磁盘访问，但词典太大，无法在可用内存中进行无错误的哈希。

布隆过滤器使用一个位数组和几个哈希函数解决这个问题。添加一个元素会将这些位置上的位设置为1，测试时检查这些位是否都为1。如果任何一个位为0，则该元素肯定不在，因此没有假阴性；如果所有位都为1，则该元素可能在集合中，也可能只是与其他元素冲突，产生假阳性。

因为错误是单向的且可调，结构保持很小，同时消除了大部分不必要的磁盘读取。一个错误率仅为18%的哈希区域，就能消除87%的磁盘访问，而每个元素不到10个位就能达到约1%的假阳性率。