本篇文章来描述一下布隆过滤器数据结构
什么是布隆过滤器?
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。这是因为在布隆过滤器中，元素是通过多个哈希函数映射到位数组中的，而这些哈希函数可能会产生冲突，导致一些未被添加的元素被错误地标记为已存在。好了 本篇文章就到这里结束了 内容有点难 大家要反复的理解 这篇文章的基础是哈希函数和哈希算法 在理解了哈希算法之后 再来学习布隆过滤器 有助于加深对文章的理解
在这里我给大家推荐一个课程 小编也学习过这个课程 感觉性价比挺高:
