这个大名早有耳闻,但一直没有仔细研究过,现在通过学习“系统设计”仔细研究了这个数据结构。
其实原理非常简单,就是变种的hash用来检查元素是否存在。 单纯的hash在数据量极大的时候会有很多瓶颈,空间利用率问题还有冲突概率问题。 而Bloom Filter使用多个hash函数同时映射,在判断是否存在的时候也同时检查多个hash值,当任何hash值不为true的时候,可以肯定 该元素不存在,当所有hash都为true是,只能确定可能存在。 所以这里面有一定的概率,具体取决于一些参数的设定。
这个思想很巧妙,也算是一种时间空间的trade-off
与普通的bloom filter每个hash值只存储0或1不同,count-bloom-filter每次映射的数组值都会加一,这样就会有一个count上限, 对一个hash进行检查的时候,可以把对应的所有hash值进行比较,其最小值代表了该元素的count上限。