布隆过滤器就是这样一个数据结构，在使用更少空间的情况下，可以给出一个元素是否位于给定的集合的功能。根据布隆过滤器的设计，它的结果有可能会是“假阳性”（ false positive ）的，但不可能出现“假阴性”（ false negative ）。换句话说，给定一个元素 X ，如果布隆过滤器说它存在于集合中，那么它有可能真的存在，而如果布隆过滤器说它不存在，那么就一定不存在。
布隆过滤器的原理
布隆过滤器的设计基于我们已经很熟悉的哈希函数，显然，对于同一个元素，不同的哈希函数会得出不同的哈希值，根据这一特性，就可以着手设计布隆过滤器了。首先，在一段长度为 m 的比特数组（ bit array ）中，将所有的比特置为 0 ，然后根据某种规则挑选 k 个哈希函数。当往布隆过滤器里添加一个元素 X 时，通过这 k 个哈希函数计算出 k 个哈希值，这也就对应着比特数组中的 k 个位置，将这 k 个位置的值置为 1 ，到此元素 X 添加完成。而判断一个元素是否存在于集合中也是同样的过程，计算出 k 个哈希值，然后去数组中对应的这 k 个位置检查是否都为 1 ，如果有 0 存在，那么意味着这个元素不可能存在于集合中。
parkma99
commented
11 months ago
布隆过滤器的作用
我们经常能遇到判断一个元素是否在一个给定的集合中的需求，使用哈希表就可以解决这个需求，并且查询的时间复杂度是常数级。然而，如果集合上了规模，我们就不得不考虑这样一个集合将要占用多少空间了。假如里面存的都是整数，按一个整数四个字节计算，十亿个整数就要用掉大约 4GB 的内存。
布隆过滤器就是这样一个数据结构，在使用更少空间的情况下，可以给出一个元素是否位于给定的集合的功能。根据布隆过滤器的设计，它的结果有可能会是“假阳性”（ false positive ）的，但不可能出现“假阴性”（ false negative ）。换句话说，给定一个元素 X ，如果布隆过滤器说它存在于集合中，那么它有可能真的存在，而如果布隆过滤器说它不存在，那么就一定不存在。
布隆过滤器的原理
布隆过滤器的设计基于我们已经很熟悉的哈希函数，显然，对于同一个元素，不同的哈希函数会得出不同的哈希值，根据这一特性，就可以着手设计布隆过滤器了。首先，在一段长度为 m 的比特数组（ bit array ）中，将所有的比特置为 0 ，然后根据某种规则挑选 k 个哈希函数。当往布隆过滤器里添加一个元素 X 时，通过这 k 个哈希函数计算出 k 个哈希值，这也就对应着比特数组中的 k 个位置，将这 k 个位置的值置为 1 ，到此元素 X 添加完成。而判断一个元素是否存在于集合中也是同样的过程，计算出 k 个哈希值，然后去数组中对应的这 k 个位置检查是否都为 1 ，如果有 0 存在，那么意味着这个元素不可能存在于集合中。