ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、视频、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
下图就是一个经过了`2`次哈希函数得到的布隆过滤器,根据下图我们很容易看到:假如`Redis`根本不存在,但是`Redis`经过`2`次哈希函数之后得到的两个位置已经是`1`了(一个是`wolf`通过`f2`得到,一个是`Nosql`通过`f1`得到,这就是发生了哈希碰撞,也是布隆过滤器可能存在误判的原因)。 ![](https://img.kancloud.cn/91/8d/918d97ceaf4b4734c896b55d26278e29_750x275.png) 所以通过上面的现象,我们从布隆过滤器的角度可以得出布隆过滤器主要有`2`大特点: 1. 如果布隆过滤器判断一个元素存在,那么这个元素**可能存在**。 2. 如果布隆过滤器判断一个元素不存在,那么这个元素**一定不存在**。 而从元素的角度也可以得出`2`大特点: 1. 如果元素实际存在,那么布隆过滤器**一定会判断存在**。 2. 如果元素不存在,那么布隆过滤器**可能会判断存在**。 PS:**需要注意的是,如果经过`N`次哈希函数,则需要得到的`N`个位置都是`1`才能判定存在,只要有一个是`0`,就可以判定为元素不存在布隆过滤器中**。 #### fpp 因为布隆过滤器中总是会存在误判率,所以哈希碰撞是不可能百分百避免的。**布隆过滤器对这种误判率称之为假阳性概率**,即:False Positive Probability,简称为`fpp`。 在实践中使用布隆过滤器时可以自己定义一个`fpp`,然后根据布隆过滤器的理论计算出需要多少个哈希函数和多大的位数组空间。需要注意的是这个`fpp`不能定义为`100%`,因为无法百分保证不发生哈希碰撞。