哈希函数堂兄弟 “布隆过滤器”

2026/9/10 8:31:25 拓冰建站浏览量

本篇文章来描述一下布隆过滤器数据结构

什么是布隆过滤器?

Bloom Filter是一种时空效率都很高的随机数据结构，通过一个位数组和多哈希函数来解决海量数据的判重问题，适用于不严格要求100%正确的场合，也可以用来对数据进行初步过滤。

Bloom Filter的原理与Bitmap十分类似，区别仅在于使用k个而不是单个哈希函数，以降低因哈希碰撞冲突造成的误判。

Bloom Filter一般需要提供两个接口：

将元素加入集合

给定元素，判断集合中是否存在

2.布隆过滤器初始化

初始集合bits[m]是个全为0的位数组。

3.添加元素

在添加元素时，分别计算出k个哈希值hi，并将bits[hi]置成1。

4.判断存在性

给定元素，分别计算出k个哈希值hi，只要有一个bits[hi]是0，则该元素一定不在集合中；反之，如果全部bits[hi]都是1，那么该元素有很大概率存在于集合中。

布隆过滤器代码实例:

#include <bitset>  
#include <vector>  
#include <functional>  class BloomFilter {  
private:  size_t capacity_;  size_t hash_num_;  std::vector<std::function<size_t(const std::string&)>> hash_functions_;  std::bitset<8 * 1024 * 1024> bitset_;  // 假设位数组的大小为1MB  public:  BloomFilter(size_t capacity, size_t hash_num)  : capacity_(capacity), hash_num_(hash_num), bitset_(capacity) {  hash_functions_.resize(hash_num);  hash_functions_[0] = std::hash<std::string>{};  if (hash_num > 1) {  auto seed = std::chrono::system_clock::now().time_since_epoch().count();  std::mt19937 gen(seed);  std::uniform_int_distribution<> dis(0, INT_MAX);  for (size_t i = 1; i < hash_num; ++i) {  hash_functions_[i] = [&gen, &dis](const std::string& s) {  return dis(gen) ^ std::hash<std::string>{}(s);  };  }  }  }  void add(const std::string& value) {  for (auto& hash : hash_functions_) {  size_t hash_value = hash(value);  bitset_.set(hash_value % capacity_, true);  }  }  bool might_contain(const std::string& value) {  for (auto& hash : hash_functions_) {  size_t hash_value = hash(value);  if (!bitset_.test(hash_value % capacity_)) {  return false;  }  }  return true;  }  
};

这个布隆过滤器类有两个主要的函数：add 和 might_contain。add 函数用于向过滤器中添加一个元素，而 might_contain 函数则用于检查一个元素是否可能在过滤器中。

布隆过滤器有一个重要的特性，那就是它可能会产生误报。也就是说，如果一个元素没有被添加到过滤器中，might_contain 函数仍然可能会返回 true。这是因为在布隆过滤器中，元素是通过多个哈希函数映射到位数组中的，而这些哈希函数可能会产生冲突，导致一些未被添加的元素被错误地标记为已存在。

好了本篇文章就到这里结束了内容有点难大家要反复的理解这篇文章的基础是哈希函数和哈希算法在理解了哈希算法之后再来学习布隆过滤器有助于加深对文章的理解

在这里我给大家推荐一个课程小编也学习过这个课程感觉性价比挺高:

https://xxetb.xetslk.com/s/2PjJ3T

建站实战干货

哈希函数堂兄弟 “布隆过滤器”

3.添加元素

4.判断存在性