原理

数据结构

布隆过滤器的数据结构是一个位向量,也就是一个由01所组成的向量(下面是一个初始向量):
notion image

添加

每个元素添加进布隆过滤器前,都会经过多个不同的哈希函数,计算出不同的哈希值,然后映射到位向量上,也就是对应的位上面置1:
notion image

判断存在

判断元素是否存在也是如上图流程,根据哈希函数映射的位置,判断所有映射位置是否都为1,如果是则元素可能存在,否则元素一定不存在。
由于不同的值通过哈希函数之后可能会映射到相同的位置,因此如果一个不存在的元素对应的位位置都被其他元素所设置位1,则查询时就会误判:
notion image
假设上图元素3334并没有加入集合,但是由于它映射的位置已经被其他元素所映射,则查询时会误判。
Loading...
目录
文章列表
王小扬博客
产品
Think
Git
软件开发
计算机网络
CI
DB
设计
缓存
Docker
Node
操作系统
Java
大前端
Nestjs
其他
PHP