布隆过滤器原理及实现
原创
一句话总结
布隆过滤器的核心能力是：
- 在超大规模的数据集中，仅使用少量内存空间，即可快速判断一个元素是否存在。
- 具备数据隐私性。即，可以在不暴露具体数据的情况下，判断一个元素是否存在。
它的核心原理是，不存储具体数据，而仅仅存储数据指纹（哈希值），通过比对指纹来判断数据是否存在。
典型的超大规模数据场景有：
判断一个 HTTP 请求的 URL 是否在恶意 URL 列表中。这个列表的数量可以达到上亿，我们可以借助布隆过滤器，保证这个查询仅消耗少量的内存和查询时间，否则会影响用户体验。
在大数据存储系统中，海量的数据一般会分散存储在多个不同的文件中。查询一个数据时，需要在磁盘上遍历多个文件才能找到，效率很差。我们可以为每个文件在内存中维护一个布隆过滤器，以便快速判断目标数据是否存在于该文件中，避免无效的磁盘 IO 操作。
说到判断元素是否存在，首先应该想到前文讲的 哈希集合，它可以在 的时间增删元素，可以在 的时间判断一个元素是否存在。
但如果数据规模特别大，那就不行了。
因为哈希集合本质上就是哈希表，而在 哈希表的代码实现 中，我们必须要用一个 KVNode 类把键值数据存储在内存中，以便处理哈希冲突。
所以哈希集合的空间复杂度是 ，随着存储元素的数量增加，占用的内存也会线性增加。在超大数据规模场景下，有限的内存肯定是无法加载所有数据的。
同时，因为哈希集合要存储实际的数据，也就不具备数据隐私性。
那么，布隆过滤器是如何实现的呢？有了布隆过滤器，是否还需要哈希集合呢？