布隆过滤器
布卢姆过滤器是一种数据结构，它允许计算机查看一个给定元素是否出现在一个集合中。布卢姆过滤器使用哈希函数来实现这一点。对于每一个被添加的元素，都会计算一个哈希值。当一个新元素被添加时，它的哈希值会与集合中的其他元素进行比较。布鲁姆过滤器是一种概率数据结构。有可能得到一个假阳性，但不可能得到一个假阴性。换句话说，一个查询的结果要么是"可能在集合中"，要么是"绝对不在集合中"。元素可以被添加到集合中，但不能被删除。每增加一个元素，得到假阳性的概率就会增加。
爱德华-布鲁姆在1970年提出了布鲁姆过滤器。在文章中，Bloom假设有一种算法可以在行末连词。根据这个例子，大多数单词都有简单的连字符模式。但约有10%的单词需要耗时的查找来获取正确的规则。他的案例是，大约50万个单词的连字符。他看到，使用"普通"的无误哈希技术，存储连字符模式，需要大量的内存。他发现，使用他的技术，可以消除大部分查找。例如，一个只有理想的无误哈希所需的15%大小的哈希区，仍然可以消除85%的磁盘访问。
更一般来说，每个元素的假阳性概率为1%时需要少于10位，与集合中元素的大小或数量无关。
问题和答案
问：什么是布鲁姆过滤器？答：布隆过滤器是一种数据结构，允许计算机查看某个元素是否出现在一个集合中。它使用哈希函数来实现这一目的，计算所添加的每个元素的哈希值，并将其与集合中的其他元素进行比较。
问：布隆过滤器是什么类型的数据结构？
答：布隆过滤器是一种概率数据结构，意味着有可能得到假阳性结果，但没有假阴性结果。
问：谁提出了布鲁姆过滤器？
答：爱德华-布鲁姆在1970年提出了布鲁姆过滤器。
问：爱德华使用其技术的例子是什么？
答：爱德华的例子是对大约50万个单词进行连字符处理；他发现，使用他的技术，他可以消除大多数查找，并将磁盘访问量减少15%。
问：每个元素需要多少比特才能达到1%的假阳性概率？
答：1%的假阳性概率，每个元素需要少于10比特，与集合的大小或元素的数量无关。
问：一旦添加了元素，是否可以将其从Bloom filter中删除？
答：不能，元素只能被添加到集合中，不能被删除。
问：添加更多的元素是否会增加或减少得到假阳性结果的概率？
答：添加更多元素会增加获得假阳性结果的概率。
