【C++】BloomFilter——布隆过滤器_c++ 布隆过滤器

作者：菜鸟追梦旅行 | 2024-04-08 03:37:00

踩

c++ 布隆过滤器

文章目录

一、布隆过滤器概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间 .

位图的优点是节省空间，快，缺点是要求范围相对集中，如果范围分散，空间消耗上升，同时只能针对整型，字符串通过哈希转化成整型，再去映射，对于整型没有冲突，因为整型是有限的，映射唯一的位置，但是对于字符串来说，是无限的，会发生冲突，会发生误判：此时的情况的是不在是正确的，在是不正确的，因为可能不来是不在的，但是位置跟别人发生冲突，发生误判

此时布隆过滤器就登场了，可以降低误判率：让一个值映射多个位置，但是并不是消除误判

可能还是会出现误判：

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