【Q328】简述 bloomfilter，及它的使用场景是什么

[shfshanyue]

[liazylee]

一个以计算来换取空间的概率算法，分配一个连续的内存 （m 位的位数组），将目标通过k个hash函数，每个hash函数映射到位数组上。查询时通过所有的k个hash函数计算是否为1。只要有一个0 则不存在，全部为1也不是一定存在。所以bloomfilter适合希望减少内存占用，但允许判断存在True出现误判。不允许误差的使用的场景是在缓存或数据库的上层加上bloomfilter，判断是否存在，如果不存在就不去操作缓存或者数据库层。允许误差的情况下使用场景就较多，可以参考redis set的使用场景。