布嵘过滤器为一种空间效率很高的随机数据结构, 它的实现方法主要包括一个位数组, 可用c++中的bitset来实现和k个哈希函数. 算法原理为: 当向某一个集合中添加一个元素的时候, 该元素会分别作为K个哈希函数的输入, 将该元素映射到位数组的k个点, 将这些点置为1. 当要查找某个元素是否在该集合中时, 只要将该元素作为k个哈希函数的输入, 然后看映射到的k个点是否为1, 如果全为1, 则该元素(可能)在该集合中, 如果出现了一个为0, 则说明该元素不在该集合中. 这就是该算法的基本思想.
集合s = {x1, x2, x3,...xn}在添加元素时, 设置位数组的过程:
说全为1, 该元素可能存在是因为该算法是存在一个错误率的, 即可能将一个不存在的元素判断为存在这个集合中.为了使错误率最低, 需要知道如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
即: 位数组大小 m >= nlg(1/E)*lge (E为错误率) = nlg(1/E)1.44倍(lg表示以2为底的对数)
哈希函数的个数 k = (ln2)*(m/n)
所以bloom filter比较适合可以容忍错误的应用.它通过低的错误率来节省大量的存储空间.
使用范围: 拼音错误检测和数据库系统; 可以用来实现数据字典, 数据判重或者求集合的交集.
Bloom filter将集合中的元素映射到位数组当中, 用k(k为哈希函数的个数)个映射位是否全1表示元素是否在这个集合中. 它的缺点是, 一个元素添加到集合中之后, 就不能删除了, 否则该元素对应的位会影响其他元素. CBF是一种改进, 它将每个bit改为了一个计数器, 从支持删除操作,即每删除一个关键字, 将对应k个位(计数器)减一. SBF 将计数器与元素出现次数相关联, 将计数器中最小的作为该元素出现的频率.