C++怎么实现一个布隆过滤器_C++海量数据去重与概率性数据结构

风明同学_9394

风明同学_9394

2025-11-28

469人浏览

原创

布隆过滤器是一种高效判断元素是否可能存在于集合中的概率性数据结构,由位数组和多个哈希函数构成;插入时将k个哈希位置设为1,查询时若所有位均为1则可能存在,否则一定不存在;C++实现采用vector存储,通过双重哈希生成多值,结合最优m和k参数控制误判率,适用于去重、缓存防穿透等场景,但不支持删除且存在假阳性。

c++怎么实现一个布隆过滤器_c++海量数据去重与概率性数据结构

布隆过滤器(Bloom Filter)是一种用于快速判断某个元素是否可能存在于集合中的概率性数据结构。它特别适合处理海量数据去重场景,比如爬虫URL去重、数据库缓存穿透防护等。虽然它会存在一定的误判率(即“假阳性”),但不会出现“假阴性”,而且空间和时间效率极高。

布隆过滤器的核心原理

布隆过滤器由一个长度为 m 的位数组和 k 个独立的哈希函数组成。每个哈希函数将输入元素映射到位数组的一个位置上。

  • 插入元素:对元素使用 k 个哈希函数得到 k 个位置,将位数组中这些位置全部置为 1。
  • 查询元素:同样计算 k 个位置,如果所有位置都为 1,则认为元素“可能存在”;只要有一个位置为 0,就说明元素“一定不存在”。

由于多个元素可能哈希到位数组的相同位置,所以会出现误判——即某个元素没插入过,但它的 k 个位置都被其他元素设为 1,导致判断为“可能存在”。

C++ 实现布隆过滤器的关键步骤

要实现一个高效的布隆过滤器,需要考虑位数组管理、哈希函数设计以及参数调优。

1. 使用 bitset 或 vector 管理位数组

为了节省内存,应使用位级别存储。C++ 中推荐使用 std::vector,它是特化的模板,按位存储。

std::vector<bool> bits;
size_t size;</bool>

2. 设计多个哈希函数

实际中不需要真正实现 k 个完全独立的哈希函数。可以通过一个通用哈希函数结合种子值生成多个不同结果。

常用技巧是使用 std::hash 并引入扰动:

class BloomFilter {
private:
    std::vector<bool> bits;
    size_t size;
    size_t hashCount;
<pre class="brush:php;toolbar:false;">// 使用双重哈希生成多个哈希值
std::vector<size_t> getHashes(const std::string& key) const {
    std::vector<size_t> hashes;
    std::hash<:string> hasher;
    size_t hash1 = hasher(key);
    size_t hash2 = hash1 >> 1;  // 简单扰动生成第二个基础哈希

    for (size_t i = 0; i <p>};</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill13058" title="Upstream Recon"><img
														src="https://img.php.cn/upload/skill/001/246/273/6adaf20e352aa140.jpg" alt="Upstream Recon" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill13058" title="Upstream Recon" class="overflowclass">Upstream Recon</a>
													<p class="overflowclass">在与开源项目(如提交PR、Issue或评论)互动前,先对其进行调研。适用于:提交Issue、提交PR或发表评论之前。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill13058" title="Upstream Recon" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div></:string></size_t></size_t>

3. 插入与查询操作

插入时将所有哈希位置设为 true;查询时检查是否全为 true。

void insert(const std::string& key) {
    auto hashes = getHashes(key);
    for (size_t pos : hashes) {
        bits[pos] = true;
    }
}
<p>bool mayContain(const std::string& key) const {
auto hashes = getHashes(key);
for (size_t pos : hashes) {
if (!bits[pos]) return false;  // 一定不存在
}
return true;  // 可能存在
}</p>

4. 参数选择:m 和 k 的最优值

给定预期插入元素数量 n 和可接受误判率 p,可以推导出最优参数:

  • 位数组长度:m = -n × ln(p) / (ln(2))²
  • 哈希函数数量:k = ln(2) × m / n ≈ 0.693 × m / n

例如,若 n=1000000,p=0.01(1%误判率),则 m≈9.6MB,k≈7。

完整简化版实现示例

#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <cmath><p>class BloomFilter {
private:
std::vector<bool> bits;
size_t size;
size_t hashCount;</bool></p>
<pre class="brush:php;toolbar:false;">std::vector<size_t> getHashes(const std::string& key) const {
    std::vector<size_t> hashes;
    std::hash<:string> hasher;
    size_t hash1 = hasher(key);
    size_t hash2 = hash1 >> 1;

    for (size_t i = 0; i <p>public:
BloomFilter(size_t expectedCount, double errorRate) {
// 计算最优 m 和 k
double ln2 = std::log(2);
size = static_cast<size_t>(-expectedCount <em> std::log(errorRate) / (ln2 </em> ln2));
hashCount = static_cast<size_t>(ln2 * size / expectedCount);
bits.resize(size, false);
}</size_t></size_t></p>
<pre class="brush:php;toolbar:false;">void insert(const std::string& key) {
    auto hashes = getHashes(key);
    for (size_t pos : hashes) {
        bits[pos] = true;
    }
}

bool mayContain(const std::string& key) const {
    auto hashes = getHashes(key);
    for (size_t pos : hashes) {
        if (!bits[pos]) return false;
    }
    return true;
}

};

// 使用示例 int main() { BloomFilter bf(100000, 0.01); // 支持10万个元素,1%误判率

bf.insert("hello");
bf.insert("world");

std::cout <p>}
</p>
stream>

应用场景与注意事项

布隆过滤器非常适合以下场景:

  • 缓存系统中防止缓存穿透(如 Redis + BloomFilter 拦截无效查询)
  • 网页爬虫中判断 URL 是否已抓取
  • 垃圾邮件过滤(邮箱黑名单)
  • 大数据去重预处理(先过 BloomFilter 快速筛除已存在项)

需要注意的是:

  • 不支持删除操作(除非使用计数型布隆过滤器 Counting Bloom Filter)
  • 存在误判率,关键业务需配合后端精确查询使用
  • 哈希函数质量影响性能,避免冲突过多

基本上就这些。C++ 实现布隆过滤器不复杂,但对内存和速度要求高的场景下非常实用。

C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.02

7639

3

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.08.29

3625

6

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

2025.08.29

4768

10

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

2025.08.29

3185

10

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

2025.08.29

4768

10

C++中int、float和double的区别
C++中int、float和double的区别

本专题整合了c++中int和double的区别,阅读专题下面的文章了解更多详细内容。

2025.10.23

924

4

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2941

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Go-Zero官方文档
Go-Zero官方文档

共0课时 | 0人学习