Redis缓存三大问题解析，看完保你面试能造火箭，工作能拧螺丝。

以上只是画了布隆过滤器的很小很小的一部分，实际布隆过滤器是非常大的数组（这里的大是指它的长度大，并不是指它所占的内存空间大）。

那么一个数据是怎么存进布隆过滤器的呢？

当一个数据进行存入布隆过滤器的时候，会经过如干个哈希函数进行哈希（若是对哈希函数还不懂的请参考这一片[]），得到对应的哈希值作为数组的下标，然后将初始化的位数组对应的下标的值修改为1，结果图如下：

?

?

当再次进行存入第二个值的时候，修改后的结果的原理图如下：

所以每次存入一个数据，就会哈希函数的计算，计算的结果就会作为下标，在布隆过滤器中有多少个哈希函数就会计算出多少个下标，布隆过滤器插入的流程如下：

1. 将要添加的元素给m个哈希函数
2. 得到对应于位数组上的m个位置
3. 将这m个位置设为1

那么为什么会有误判率呢？

假设在我们多次存入值后，在布隆过滤器中存在x、y、z这三个值，布隆过滤器的存储结构图图如下所示：

当我们要查询的时候，比如查询a这个数，实际中a这个数是不存在布隆过滤器中的，经过2哥哈希函数计算后得到a的哈希值分别为2和13，结构原理图如下：

（编辑：PHP编程网 - 湛江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!