Bloom Filter 原理与应用
这篇是从老blog里复制出来，用markdown格式更新了下，纯当练手。 介绍 Bloom Filter是一种简单的节省空间的随机化的数据结构，支持用户查询的集合。一般我们使用STL的std::set, stdext::hash_set，std::set是用红黑树实现的，stdext::hash_set是用桶式哈希表。上述两种数据结构，都会需要保存原始数据信息，当数据量较大时，内存就会是个问题。如果应用场景中允许出现一定几率的误判，且不需要逆向遍历集合中的数据时，Bloom Filter是很好的结构。 优点 查询操作十分高效。 节省空间。 易于扩展成并行。 集合计算方便。 代码实现方便。 有误判的概率，即存在False Position。 无法获取集合中的元素数据。 不支持删除操作。 缺点 有误判的概率，即存在False Position。 无法获取集合中的元素数据。 不支持删除操作。 ...