布隆过滤器

https://www.bilibili.com/video/BV192421T7JV/?spm_id_from=333.337.search-card.all.click&vd_source=0404d052110f319caf00323d54512b50

布隆过滤器一般会用到哈希函数来决定在哪个bit位,解决哈希碰撞的方式一般是多次哈希,得到多个bit位。
多次哈希的值都存在我们认为它存在(但有误判的概率)
但如果有一个哈希的值不存在,那一定不存在。

总结:不存在一定不存在,存在也有小概率不存在。

用处:缓存穿透,nosql的lsm树判断元素是否存在某个level

减少哈希冲突:增加bit位或者增加哈希函数个数。

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部