Bloom Filter

Introduction

布隆过滤器是一种空间效率非常高的概率型数据结构，用于判断一个元素是否存在于一个集合中。它允许存在误判（false positives，即它说在可能不在），但不会产生误报（false negatives，即它说不在肯定不在）。

布隆过滤器的工作原理概述如下：

初始化：在开始时，布隆过滤器初始化为一个全0的位数组（bit array）和几个哈希函数（这里涉及2个参数，数组长度m和哈希函数个数k，后文介绍如何选择合适参数）
添加元素：每当添加一个元素到过滤器中时，使用多个哈希函数对元素进行计算，得到数组中的多个位置，并将这些位置的位都设置为1。
元素查找：要判断一个元素是否存在于集合中，同样使用那些哈希函数对该元素进行计算，得到位数组中对应的位置。如果所有这些位置的位都是1，那么认为元素可能存在于集合中（存在假阳性的风险）。如果任何一个位是0，则元素肯定不在集合中。

布隆过滤器的优点是空间效率和查询时间都非常高效，尤其适合于处理大数据集合。缺点则是它不能从集合中删除元素（虽然有变体如计数布隆过滤器允许这样做，或者Cuckoo filter），并且随着元素的增加，假阳性的概率会上升。

选择合适的位数组大小m 和哈希函数数量k 是实现高效Bloom Filter的关键。这些参数直接影响到布隆过滤器的误判率（false positive rate, FPR）。

\[m=-\frac{n\ln p}{(\ln 2)^2}, k = \frac{m \ln 2}{n}\]

其中\(n\)是要添加到布隆过滤器中的元素数量，\(p\) 是期望的误判率。
但是，如果不确定要添加到布隆过滤器中的元素数量怎么办？可以使用可扩展的布隆过滤器（Scalable Bloom Filter）[^sbf]，这种类型的布隆过滤器允许动态调整容量，以保持误判率在一个可接受的阈值之内。

周亚金课题组：浙江大学的计算机本科教育，在课程上存在着两极分化较为严重的情况。一方面，一些专业课程通过课程改革，紧跟技术发展，给同学们提供了更先进的知识；一方面，一些课程的老师照本宣科，实验陈旧，跟不上时代。同时，一些专业课程的改革不在课程内容上下功夫，而是在课程形式上做表面文章。