Cassandra的bloom过滤器是什么？

本文共计701个文字，预计阅读时间需要3分钟。

问题：如何判断一个元素是否存在于一个集合中？最简单直观的方法就是使用常用的数据结构——哈希表。但哈希表的特点是必须存储每个插入的值，因此其空间复杂度与值的数量成正比。

问题：如何判断一个元素是否存在于一个集合中

最简单直观的办法就是常用的数据结构与算法---哈希表。但是哈希表的特点是必须存储每一个加入的值，所以空间复杂度与值的数目成正比，并且一般哈希表是有装载因子这个指标，所以一般空间会大于元素的个数。在海量数据的情况下并不是很合适。

Bloom 过滤器就是针对海量数据情况下查询某一个元素是否存在的一种方法。

其基本的思路是：

找一个很大的bit数组m和k个哈希函数，每一个哈希函数都可以把带存储元素映射到bit数组的每一位。然后每一个待存储的元素x都让这k个哈希函数生成一个值，得到一个序列g1，g2.。。gx。然后g就是m的索引，把m中相应的位置设置为1。这样给定一个数据y，只需要根据k各哈希函数计算出g，只有m中每一个g代表的位置都是1，就认为y是存在的。这个方法的优点是所需要的空间和时间都是常数级别，更加高效。但是缺点也很明显，存在误判而且无法删除。

不过这两个缺点可以改进。

误判的概率是比较小的，据说是万分之一。以下是分析的大致过程：

如果这个元素确实被加入，那么不会误判。如果这个元素没有加入，但是它对应的m数组却恰好被其他的元素设为了1，导致我们认为该元素存在，这是误判的原因，也是我们关系的误判概率。