大数据过滤及判断算法 -- Bitmap / Bloomfilter
这篇讲的是如何用极低的空间成本，高效判断一个元素是否存在于海量数据集合中。作者从一道常见的面试题出发，引出了两个核心数据结构：Bitmap与Bloomfilter。 文章首先剖析了Bitmap，它本质上就是一块连续的内存位图，每个bit（0/1）直接对应一个元素的“无/有”。作者展示了如何通过简单的位运算（`/8`和`%8`）定位到具体的bit位，并给出了一个完整的C++代码示例，用于在一个10万规模的集合中精确查找缺失的数字。Bitmap的优点是100%准确，但缺点是所需内存与元素值的范围直接相关。 接着，文章重点介绍了Bloomfilter。它通过多个哈希函数对同一个值进行多次哈希，将结果映射到不同的bit位上。这种设计能用远小于Bitmap的内存处理更海量的数据，但代价是存在理论上的误判——可能将不在集合的元素误判为“存在”。作者解释了误判率与哈希函数数量、内存大小的关系，并提供了包含三种经典哈希函数（BKDR、FNV、DEK）的实现代码。 文末，作者还留下了一个思考题：对于“从1到100万无序数中找出被随机取走的N个数”这个问题，除了这两种方法，还可以如何利用数学性质（如求和、求积）来间接求解？这展示了不同场景下算法选择的灵活性。