稻田代码

布隆过滤器

作用:
高效的判断一个元素是否在一个集合中。
优点:高效的判断一个元素不在一个很大的数组中
缺点: 不可以判断一个元素一定在一个数组中

原理:
如果想判断一个元素v是否在一个数组arr中,需要定义一个足够大的数组bit_arr并把每个元素的值初始化为0,预先把arr数组中的每一个元素都用n个hash函数生成n个数字,把位数组bit_arr中对应的n个数字位置的元素改成1。

把v用同样的n个hash生成n个数字,如果这几个数字在位数组bit_arr中对应的位置有一个元素值不是1则v一定不在数组arr中,如果对应的元素都是1,说明v可能在数组arr中(不一定在的原因:虽然v生成的几个位置的值都是1,但可能其中的某个1是arr中其他数字生成的)。

注:
利用了数组读取每个元素的时间复杂度都为O(1)的优点

bit_arr中的元素是预先就用arr生成进去的而不是临时生成的





本原创文章未经允许不得转载 | 当前页面:稻田代码 » 布隆过滤器