布隆过滤器可以快速判断数据是否存在,避免从数据库中查询数据是否存在,减轻数据库的压力
布隆过滤器是由一个初值为0的bit数组和N个哈希函数,可以用来快速的判断某个数据是否存在
当我们想要标记某个数据是否存在时,布隆过滤器会通过三个操作完成标记:
- 首先,使用N个哈希函数,分别计算这个数据的哈希值,得到N个哈希值
- 然后,我们把这N个哈希值对bit数组的长度取模,得到每个哈希值在数组中的对应位置
- 最后,我们把对应位置的Bit位设置为1,这就完成了在布隆过滤器中标记数据库的操作
如果数据不存在,我们也就没有使用过布隆过滤器标记过数据,那么,bit数组对应的bit位的值仍然为0
当需要查询某个数据时,我们就执行刚刚说的计算过程,先得到这个数据在bit数组中对应的N个位置。紧接着,我们查看bit数组中这N个位置上的bit值。只要这个N个bit值不为1,这就说明布隆过滤器没有对该数据做过标记,所以,查询的数据一定没有在数据库中保存。