布隆过滤器：一种低空间成本的判断元素是否存在的方式_使用布隆过滤器判断元素是否存在

作者：IT小白 | 2024-04-28 19:13:31

踩

使用布隆过滤器判断元素是否存在

简介

布隆过滤器（BloomFilter）是一种用于判断元素是否存在的方式，它的空间成本非常小，速度也很快。

但是由于它是基于概率的，因此它存在一定的误判率，它的Contains()操作如果返回true只是表示元素可能存在集合内，返回false则表示元素一定不存在集合内。因此适合用于能够容忍一定误判元素存在集合内的场景，比如缓存。

它一秒能够进行上百万次操作（主要取决于哈希函数的速度），并且1亿数据在误判率1%的情况下，只需要114MB内存。

布隆过滤器的数据结构是一个位向量，也就是一个由0、1所组成的向量（下面是一个初始向量）：

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

判断元素是否存在也是如上图流程，根据哈希函数映射的位置，判断所有映射位置是否都为1，如果是则元素可能存在，否则元素一定不存在。

由于不同的值通过哈希函数之后可能会映射到相同的位置，因此如果一个不存在的元素对应地位位置都被其他元

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/503833