布隆过滤器*中文说明.7z下载

布隆过滤器是空间高效的概率 数据结构，通过设想伯顿霍华德布卢姆于1970年，是用于测试一个是否元件是一个的成员组。可能会出现假阳性匹配，但否定否定匹配-换句话说，查询返回“可能在集合中”或“绝对不在集合中”。元素可以添加到集合中，但不能删除（尽管可以通过计数Bloom过滤器变体来解决）；添加的项目越多，误报的可能性越大。 Bloom提出了一种应用技术，如果应用了“常规”的无错误哈希技术，则源数据量将需要不切实际的大量内存。他举了一个针对500,000个单词的字典的断字算法的示例，其中90％遵循简单的断字规则，但是其余的10％需要昂贵的磁盘访问来检索特定的断字模式。有了足够的核心内存，可以使用无错误的哈希来消除所有不必要的磁盘访问；另一方面，由于核心内​​存有限，Bloom的技术使用较小的哈希区域，但仍消除了大多数不必要的访问。例如，仅理想无错误哈希所需大小的15％的哈希区域仍可消除85％的磁盘访问。[1] 更一般地，对于1％的误报概率，每个元素需要少于10位，而与集合中元素的大小或数量无关