无题

布隆过滤器

布隆过滤球实质上是一个超长的字节数组，经过布隆过滤器的判断，如果判断key存在于系统中，则在系统中可能不存在；如果判断不存在于系统中，则必定不存在

初始时的布隆过滤器：

假设存在

y1 = f(x) = length(str)

y2 = f(x) = length(str) * 2 - 1

y3 = f(x) = length(str) * 3 - 2

这三个函数

现在需要将[“a”, “ab”, “abc”]三个字符串存入布隆过滤器，操作如下

最后一步存入abc后，布隆过滤器变成了如图所示的状态

当查询字符串 ab 时，把字符串 ab 做上面的函数映射，根据三个函数可以得到 111 的组合，都为1，说明系统可能存在字符串ab

当查询字符串 ac 时， 把字符串 ac 做上面的函数映射，根据三个函数可以得到 111 的组合，都为1，说明系统可能存在字符串ac，其实并不存在，这就取决于我们设计的hash函数是否足够分散

当查询字符串 abcdefg 时，把字符串 abcdefg 做上面的函数映射，根据三个函数可以得到 100 的组合，存在0，则说明系统中不存在字符串 abcdefg

当然，布隆过滤器也存在局限，在删除数据时，布隆过滤器无法删除。