布隆过滤器和哈希表的区别

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

可以在此处找到散列的一些应用。

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

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

Google Chrome 网络浏览器曾经使用 Bloom 过滤器来识别恶意 URL。首先根据本地 Bloom 过滤器检查任何 URL，并且只有当 Bloom 过滤器返回肯定结果时，才会对 URL 进行全面检查(如果也返回肯定结果，用户会发出警告)。

下面来看看哈希表和布隆过滤器之间的区别：

S No.	哈希表	布隆过滤器
1	在哈希表中，对象被存储到哈希函数映射到的桶(哈希表中的索引位置)。	布隆过滤器不存储关联的对象，只是告诉它是否存在于布隆过滤器中。
2	哈希表的空间效率较低。布隆过滤器更节省空间。	布隆过滤器的大小甚至小于它正在映射的关联对象。
3	支持删除。	无法从布隆过滤器中删除元素。
4	哈希表给出了准确的结果。	布隆过滤器的误报概率很小(误报意味着它可能在布隆过滤器中，但实际上不是。)
5	在哈希表中，要么应该实现多个哈希函数，要么有一个强大的哈希函数来最小化冲突。	布隆过滤器使用许多散列函数。无需处理冲突。
6	哈希表用于编译器操作、编程语言(基于哈希表的数据结构)、密码验证等。	布隆过滤器在网络路由器、Web 浏览器(检测恶意 url)、密码检查器(不是一组)中找到应用弱密码或可猜测密码或禁止密码列表)等。