当前位置：首页 > news >正文

C++哈希扩展：位图与布隆过滤器实战

news 2026/4/20 6:11:07

【C++】哈希扩展——位图和布隆过滤器的介绍与实现

位图（Bitmap）和布隆过滤器（Bloom Filter）是两种基于哈希扩展的高效数据结构，常用于处理大规模数据集的存储和查询。位图主要用于表示和操作布尔值集合，而布隆过滤器则是一种概率数据结构，用于快速测试元素是否在集合中（可能产生假阳性但不会假阴性）。下面我将逐步介绍它们的概念、原理、优缺点，并提供C++实现代码。

1. 位图（Bitmap）的介绍

位图是一种紧凑的数据结构，用于存储和操作二进制位（bit）。它通过将每个位映射到一个索引来表示布尔值集合，例如表示一个元素是否存在。位图的优势在于空间效率高（每个元素仅占1位），适合处理大规模稀疏数据。

工作原理：位图使用一个位数组（bit array），每个索引对应一个元素的状态（0表示不存在，1表示存在）。
优点：
- 空间复杂度低：每个元素只占1位。
- 查询和修改速度快：通过位操作（如位掩码）实现$O(1)$时间复杂度的操作。
缺点：
- 只能处理整数索引元素，不适合非整数类型。
- 当元素范围很大时，可能导致空间浪费（例如元素稀疏）。
应用场景：集合去重、内存管理、位图索引等。

在C++中，位图可以用std::bitset实现，或手动使用位操作（如unsigned int数组）。

2. 位图的C++实现

下面是一个手动实现的位图类，支持设置、清除和查询操作。代码使用位操作优化空间和性能。

#include <iostream> #include <vector> class Bitmap { private: std::vector<unsigned int> bits; // 使用unsigned int数组存储位 size_t size; // 位图总位数 public: // 构造函数，初始化位图 Bitmap(size_t num_bits) : size(num_bits) { // 计算需要的unsigned int数量 size_t num_ints = (num_bits + sizeof(unsigned int) * 8 - 1) / (sizeof(unsigned int) * 8); bits.resize(num_ints, 0); } // 设置位（设为1） void set(size_t index) { if (index >= size) throw std::out_of_range("Index out of range"); size_t int_index = index / (sizeof(unsigned int) * 8); size_t bit_index = index % (sizeof(unsigned int) * 8); bits[int_index] |= (1U << bit_index); } // 清除位（设为0） void clear(size_t index) { if (index >= size) throw std::out_of_range("Index out of range"); size_t int_index = index / (sizeof(unsigned int) * 8); size_t bit_index = index % (sizeof(unsigned int) * 8); bits[int_index] &= ~(1U << bit_index); } // 查询位（返回bool） bool test(size_t index) const { if (index >= size) throw std::out_of_range("Index out of range"); size_t int_index = index / (sizeof(unsigned int) * 8); size_t bit_index = index % (sizeof(unsigned int) * 8); return (bits[int_index] & (1U << bit_index)) != 0; } // 获取位图大小 size_t get_size() const { return size; } }; // 示例使用 int main() { Bitmap bm(100); // 创建100位的位图 bm.set(10); // 设置第10位为1 bm.set(50); std::cout << "Bit 10: " << bm.test(10) << std::endl; // 输出1 (true) std::cout << "Bit 20: " << bm.test(20) << std::endl; // 输出0 (false) bm.clear(10); std::cout << "Bit 10 after clear: " << bm.test(10) << std::endl; // 输出0 return 0; }

代码解释：

使用std::vector<unsigned int>存储位，每个unsigned int通常为32位（取决于系统）。
set()、clear()和test()方法通过位操作实现高效访问。
时间复杂度：所有操作均为$O(1)$。
空间复杂度：约$\frac{n}{32}$个unsigned int（n为总位数）。

3. 布隆过滤器（Bloom Filter）的介绍

布隆过滤器是一种概率数据结构，用于高效测试元素是否在集合中。它使用多个哈希函数和一个位数组，插入元素时设置多个位，查询时检查这些位是否全为1。布隆过滤器不会产生假阴性（即如果查询为false，元素一定不在集合中），但可能产生假阳性（即查询为true时，元素可能不在集合中）。

工作原理：
- 初始化一个大小为$m$的位数组（初始全0）。
- 使用$k$个独立的哈希函数，每个函数将元素映射到位数组的一个位置。
- 插入元素：计算$k$个哈希值，将对应位设为1。
- 查询元素：计算$k$个哈希值，如果所有位均为1，则元素可能在集合中（否则一定不在）。
优点：
- 空间效率高：远低于哈希表。
- 查询速度快：$O(k)$时间复杂度（k为哈希函数数）。
缺点：
- 有假阳性概率：无法保证100%准确。
- 不能删除元素：因为多个元素可能共享位。
假阳性概率：布隆过滤器的假阳性概率$P$取决于位数组大小$m$、元素数量$n$和哈希函数数$k$，公式为：

$$ P \approx \left(1 - e^{-\frac{k \cdot n}{m}}\right)^k $$

应用场景：网络缓存、数据库查询优化、垃圾邮件过滤等。

4. 布隆过滤器的C++实现

下面是一个简单的布隆过滤器实现，使用标准库哈希函数和位图作为底层存储。

#include <iostream> #include <vector> #include <functional> #include <cmath> #include <string> class BloomFilter { private: Bitmap bits; // 使用位图存储 size_t size; // 位数组大小 int num_hashes; // 哈希函数数量 std::vector<std::function<size_t(const std::string&)>> hash_functions; // 哈希函数列表 public: // 构造函数，初始化布隆过滤器 BloomFilter(size_t m, int k) : bits(m), size(m), num_hashes(k) { // 初始化k个哈希函数（模拟多个独立哈希） for (int i = 0; i < k; ++i) { hash_functions.push_back([i, m](const std::string& key) { std::hash<std::string> hash_fn; return (hash_fn(key) + i) % m; // 使用std::hash并添加偏移 }); } } // 插入元素 void insert(const std::string& key) { for (auto& hash_fn : hash_functions) { size_t index = hash_fn(key); bits.set(index); } } // 查询元素（可能假阳性） bool contains(const std::string& key) const { for (auto& hash_fn : hash_functions) { size_t index = hash_fn(key); if (!bits.test(index)) { return false; // 如果任一位置为0，元素一定不在 } } return true; // 所有位置为1，元素可能在 } // 估算假阳性概率（理论值） double false_positive_rate(size_t n) const { return std::pow(1 - std::exp(-static_cast<double>(num_hashes) * n / size), num_hashes); } }; // 示例使用 int main() { BloomFilter bf(1000, 3); // 位数组大小1000，3个哈希函数 bf.insert("apple"); bf.insert("banana"); std::cout << "Contains 'apple': " << bf.contains("apple") << std::endl; // 输出1 (true) std::cout << "Contains 'orange': " << bf.contains("orange") << std::endl; // 可能输出1 (假阳性) // 估算假阳性概率（假设已插入2个元素） std::cout << "False positive rate: " << bf.false_positive_rate(2) << std::endl; return 0; }

代码解释：

使用Bitmap类作为底层存储。
哈希函数使用std::hash并添加偏移来模拟多个独立哈希（实际应用中可能需要更复杂的哈希函数）。
insert()和contains()方法时间复杂度为$O(k)$。
false_positive_rate()方法估算理论假阳性概率，基于公式$P \approx \left(1 - e^{-\frac{k \cdot n}{m}}\right)^k$。
注意：布隆过滤器不支持删除操作。