redis数据结构-布隆过滤器

 布隆过滤器就是一个初始为0的数组+n个hash函数

上图三个hash函数h1,h2,h3,分别算出x1的三个位置,h1(x1),h2(x1),h3(x1),然后把对应位置(数组的1,4,8)置1,同理算出x2的三个位置(数组的4,6,10)置1

判断是否存在则根据三个hash函数算出3个位置,如果都是1则有可能存在,若任意1个位置为0则肯定不存在

判断出不存在一定不存在,判断出存在则有一定几率误判(只是判断3个位置为1,有可能不是同一个值算出来的),因此hash函数个数和数组的长度决定了误判几率

原文地址:https://www.cnblogs.com/liuboyuan/p/14942707.html