布隆过滤器

布隆过滤器介绍和原理

布隆过滤器是由：位数组和一系列随机映射函数（哈希函数）两部分组成的数据结构，主要来检索元素是否在给定大集合中的数据结构，

特点是 ：布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。

布隆过滤器会使用一个较大的 bit 数组来保存所有的数据，数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1（代表 false 或者 true），这也是 Bloom Filter 节省内存的核心所在。

布隆过滤器使用多个哈希函数的主要原因是为了降低误判率

在布隆过滤器中，**当一个元素被加入到过滤器中时，会使用多个哈希函数对该元素进行哈希，得到多个哈希值。这些哈希值会分别映射到位图（Bit Array）中的不同位置，将对应位置置为 1。当要查询一个元素是否在布隆过滤器中时，同样会使用多个哈希函数对该元素进行哈希，检查对应的位图位置是否都为 1。如果有任何一个位置为 0，则可以确定该元素一定不在布隆过滤器中。如果所有位置都为 1，则可能存在误判，**需要进一步确认。

使用多个哈希函数的好处在于，**即使其中某个哈希函数发生了冲突，即两个不同的元素映射到了相同的位图位置，其他哈希函数仍然会起作用，有助于降低误判率。**如果只使用一个哈希函数，那么冲突的可能性就会增加，导致误判率升高。

因此，通过使用多个哈希函数，布隆过滤器可以更好地平衡性能和误判率之间的关系，提高过滤器的准确性和可靠性。