布隆过滤器的实现（c++）_c++实现布隆滤波器

作者：从前慢现在也慢 | 2024-06-27 16:58:18

踩

c++实现布隆滤波器

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。（摘自百度百科）

实现：

1.计算需要的哈希函数个数k及需要申请的内存长度m（m是二进制长度，申请时可以申请（（m/32）+1 个int 类型），

2.将文件中的每一个样本经k个哈希函数求得k个哈希值，并对每一个哈希值取模（哈希值%m），并将申请的内存中对应位置1（如果本来是1，则不改变），

3.判断某样本是否存在，只需重复第二步，根据哈希函数计算每一个哈希值，取模并看内存

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】