Bloom Filter可以用于检测一个元素是否已经存在于集合中,它以允许一定的误判为代价,节省了大量的存储空间。
本文描述内容,是以Redis作为底层支撑,实现一个Bloom Filter。
需要提醒的是,Redis Stack当前已支持一些概率容器,包括Bloom Filter,Cuckoo Filter,参见:Redis Stack。但是,Redis Stack并未包含在社区版的Redis中,本文的目的是使用基础的Bitmap结构,来实现一个简单的Bloom Filter。
因为使用Bitmap,所以本文描述的Bloom Filter受到Bitmap本身限制,最大容量为512M,即能存储2^32比特。
另外,本文描述的Bloom Filter暂不支持动态扩容。
本文使用了两个hash算法,分别是FNV1a和Murmur3。
Hash函数个数的计算以及支撑bit数组长度的计算,参见:维基百科
本文默认使用go-redis作为golang的redis驱动。