bloom filter 本质就是 hash 算法, 不过处理逻辑与一般的逻辑不太一样, bloom filter 主要用在大数处理上, 一般可能有几千万甚至上亿条数据比较重复的时候, 就体现出 bloom filter 的优势了, 首先 bloom filter 是位数组, 比普通算法节省大量的空间, 而且时间复杂度相比普通算法也强很多
bloom filter 的原理是取一个很长的位数组, 取 n 个 hash, 用每一个 hash 分别对要存入的元素 hash, 这时候 hash 结果落在位数组的哪里, 就将哪里的位 置为一, 这样在比较的时候只需要将需要比较的值进行 hash, 然后看这一位是不是 1, 如果是 1, 那么这个元素就可能有, 注意是可能, 而不是一定, 但是如果这一位不是 1, 那么一定不在
误判是因为多个 hash, 每次 hash 都将某一位置为一, 那么可能会有某个元素刚好被 hash 到了之前被置为 1 的地方
来源: http://www.bubuko.com/infodetail-3207211.html