C++怎么实现一个布隆过滤器_C++数据结构与布隆过滤器实现-C++-PHP中文网

C++怎么实现一个布隆过滤器_C++数据结构与布隆过滤器实现

裘德小鎮的故事

发布： 2025-11-21 16:35:41

原创

779人浏览过

布隆过滤器通过位数组和多个哈希函数判断元素是否存在，C++中可用vector<bool>和std::hash实现，插入时将哈希位置设为1，查询时若所有位均为1则可能存在，允许误判但不漏判。

c++怎么实现一个布隆过滤器_c++数据结构与布隆过滤器实现

布隆过滤器（Bloom Filter）是一种空间效率高、查询速度快的概率型数据结构，用于判断一个元素是否可能在集合中。它允许一定的误判率（即把不在集合中的元素误判为存在），但不会将存在的元素漏判。C++ 中可以通过位数组和多个哈希函数来实现布隆过滤器。

基本原理与设计思路

布隆过滤器的核心是一个长度为 m 的位数组 bitset，初始时所有位都为 0。同时定义 k 个独立的哈希函数，每个函数可以将输入元素映射到位数组的一个位置。

当插入一个元素时：

用 k 个哈希函数计算出 k 个位置
将位数组中这 k 个位置都设为 1

当查询一个元素是否存在时：

立即学习“C++免费学习笔记（深入）”；

同样计算出 k 个位置
如果这些位置中有任意一位是 0，则该元素一定不存在
如果所有位都是 1，则该元素可能存在（可能是误判）

核心组件实现

在 C++ 中，我们可以使用 std::vector<bool> 或 std::bitset 来表示位数组。考虑到动态大小，vector<bool> 更灵活。

对于哈希函数，可以使用 STL 提供的 std::hash 模板，并通过加盐或扰动方式生成多个不同的哈希值。

GPTKit

一个AI文本生成检测工具

108

查看详情

// 示例：使用 std::hash 和扰动生成多个哈希

size_t hash1 = std::hash<T>{}(value);
size_t hash2 = hash1 * 0x9e3779b9 + 0xabcdef12;
for (int i = 0; i < k; ++i) {
  size_t combined_hash = hash1 + i * hash2;
  size_t index = combined_hash % bitset_size;
  bit_array[index] = true;
}

C++ 实现代码示例

以下是一个通用的布隆过滤器模板类实现：

#include <iostream>
#include <vector>
#include <functional>
#include <cmath>

template <typename T>
class BloomFilter {
private:
  std::vector<bool> bit_array;
  size_t size;
  size_t hash_count;
public:
  explicit BloomFilter(size_t n, double fpp) {
    // n: 预期元素数量，fpp: 可接受误判率
    size = static_cast<size_t>(-n * log(fpp) / (log(2)*log(2)));
    hash_count = static_cast<size_t>(size * log(2) / n);
    bit_array.resize(size, false);
  }
  void insert(const T& value) {
    size_t h1 = std::hash<T>{}(value);
    size_t h2 = h1 * 0x9e3779b9 + 0xabcdef12;
    for (size_t i = 0; i < hash_count; ++i) {
      size_t combined_hash = h1 + i * h2;
      size_t index = combined_hash % size;
      bit_array[index] = true;
    }
  }
  bool mightContain(const T& value) const {
    size_t h1 = std::hash<T>{}(value);
    size_t h2 = h1 * 0x9e3779b9 + 0xabcdef12;
    for (size_t i = 0; i < hash_count; ++i) {
      size_t combined_hash = h1 + i * h2;
      size_t index = combined_hash % size;
      if (!bit_array[index]) {
        return false;
      }
    }
    return true;
  }
};

使用示例与注意事项

下面是一个简单使用示例：

int main() {
  BloomFilter<std::string> bf(1000, 0.01); // 支持1000个元素，误判率1%
  bf.insert("hello");
  bf.insert("world");
  std::cout << std::boolalpha;
  std::cout << bf.mightContain("hello") << "\n"; // true
  std::cout << bf.mightContain("test") << "\n"; // 可能为 false 或 true（误判）
  return 0;
}

注意点：