布隆过滤器与哈希表之间的区别

原文：https://www.geeksforgeeks.org/difference-between-bloom-filters-and-hashtable/

哈希表：

哈希表设计为使用一种称为哈希函数的特殊函数，该函数用于使用特定键映射给定值，以更快地访问元素。 它用于需要快速查找的地方。（在合理的假设下，哈希表中元素查找的平均时间为O(1)）。 Python 中的字典是使用哈希表实现的。 Java 还实现了HashTable类。

可以在中找到一些哈希应用。

布隆过滤器：

布隆过滤器是一种节省空间的概率数据结构，用于测试元素是否为集合的成员。 它用于只需要知道元素是否属于对象的地方。 布隆过滤器使用k个哈希函数和n位数组，其中数组位设置为 0，表示元素不存在，而 1 表示存在该元素。 布隆过滤器的一些应用是：

• Google Bigtable，Apache HBase，Apache Cassandra 和 PostgreSQL 使用布隆过滤器来减少对不存在的行或列的磁盘查找。 避免进行昂贵的磁盘查找，可大大提高数据库查询操作的性能。




• Google Chrome 浏览器曾经使用布隆过滤器来识别恶意网址。 首先会针对本地布隆过滤器检查所有 URL，只有在布隆过滤器返回肯定结果的情况下，才对执行的 URL 进行全面检查（如果该结果也返回肯定结果，则用户会发出警告）。

让我们看看哈希表和布隆过滤器之间的区别：

哈希表和布隆过滤器彼此密切相关，因此，比较这两个数据结构并根据您的应用/需求明智地使用它们是明智的。