c++ 位图和布隆过滤器

位图（bitmap）

定义

位图是一种使用位数组存储数据的结构。每一位表示一个状态，通常用于快速判断某个值是否存在，或者用来表示布尔类型的集合。

特点

• 节省空间：一个字节可以表示8个状态。
• 高效操作：位操作（如按位与、或、非）速度极快。
• 不支持重复元素：每个值只能映射到唯一的位。

应用

集合操作

• 判断某个用户 ID 是否存在。

• 插入一个用户 ID。

• 删除一个用户 ID。

• 计算两个用户 ID 集合的交集、并集和差集。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Bitmap {
private:vector<unsigned char> bitmap; // 位图存储size_t size;                  // 位图大小（支持的最大值）public:// 构造函数Bitmap(size_t size) : size(size) {bitmap.resize((size + 7) / 8, 0); // 每8个数占1字节}// 设置某个位为1（插入操作）void set(int num) {if (num >= size) return; // 越界检查bitmap[num / 8] |= (1 << (num % 8));}// 重置某个位为0（删除操作）void reset(int num) {if (num >= size) return; // 越界检查bitmap[num / 8] &= ~(1 << (num % 8));}// 检查某个位是否为1（查询操作）bool get(int num) const {if (num >= size) return false; // 越界检查return bitmap[num / 8] & (1 << (num % 8));}// 求交集Bitmap intersection(const Bitmap& other) const {Bitmap result(size);for (size_t i = 0; i < bitmap.size(); ++i) {result.bitmap[i] = bitmap[i] & other.bitmap[i];}return result;}// 求并集Bitmap unionSet(const Bitmap& other) const {Bitmap result(size);for (size_t i = 0; i < bitmap.size(); ++i) {result.bitmap[i] = bitmap[i] | other.bitmap[i];}return result;}// 求差集Bitmap difference(const Bitmap& other) const {Bitmap result(size);for (size_t i = 0; i < bitmap.size(); ++i) {result.bitmap[i] = bitmap[i] & ~other.bitmap[i];}return result;}// 打印位图内容void print() const {for (size_t i = 0; i < size; ++i) {if (get(i)) cout << i << " ";}cout << endl;}
};// 测试用例
int main() {Bitmap bm1(100); // 位图1，范围为0到99Bitmap bm2(100); // 位图2，范围为0到99// 插入一些IDbm1.set(10);bm1.set(20);bm1.set(30);bm2.set(20);bm2.set(30);bm2.set(40);cout << "Bitmap 1: ";bm1.print(); // 输出：10 20 30cout << "Bitmap 2: ";bm2.print(); // 输出：20 30 40// 求交集cout << "Intersection: ";Bitmap intersect = bm1.intersection(bm2);intersect.print(); // 输出：20 30// 求并集cout << "Union: ";Bitmap unionResult = bm1.unionSet(bm2);unionResult.print(); // 输出：10 20 30 40// 求差集cout << "Difference (bm1 - bm2): ";Bitmap difference = bm1.difference(bm2);difference.print(); // 输出：10return 0;
}

代码说明

1. 位图核心操作：
   • set(num)：将数字 num 对应的位置为1。
   • reset(num)：将数字 num 对应的位置清零。
   • get(num)：查询数字 num 是否存在。
2. 集合运算：
   • 交集：result.bitmap[i] = bitmap[i] & other.bitmap[i];
   • 并集：result.bitmap[i] = bitmap[i] | other.bitmap[i];
   • 差集：result.bitmap[i] = bitmap[i] & ~other.bitmap[i];
3. 空间效率：
   • 位图将整数范围映射到位数组，节省了大量存储空间。比如范围为 0 到 1,000,000 的位图只需约 125 KB 内存。
4. 时间效率：
   • 插入、删除、查询的时间复杂度为 O(1)。
   • 集合运算的时间复杂度为 O(n)，其中 n是位数组的大小。

数据去重

#include <iostream>
#include <vector>
using namespace std;class Bitmap {
private:vector<unsigned char> bitmap; // 位图存储size_t size;                 // 位图支持的最大值public:Bitmap(size_t size) : size(size) {bitmap.resize((size + 7) / 8, 0); // 每8个数占1字节}// 设置某个位为1void set(int num) {if (num >= size) return; // 超出范围检查bitmap[num / 8] |= (1 << (num % 8));}// 检查某个位是否为1bool get(int num) const {if (num >= size) return false; // 超出范围检查return bitmap[num / 8] & (1 << (num % 8));}
};// 使用位图实现数据去重
void removeDuplicates(const vector<int>& input) {const int MAX_VALUE = 1000000; // 数据范围：0到999999Bitmap bitmap(MAX_VALUE);vector<int> uniqueNumbers;for (int num : input) {if (!bitmap.get(num)) { // 如果位未被设置，说明是新数据uniqueNumbers.push_back(num);bitmap.set(num); // 标记该数据已存在}}// 输出去重后的数据cout << "Unique numbers: ";for (int num : uniqueNumbers) {cout << num << " ";}cout << endl;
}int main() {// 测试数据vector<int> input = {10, 20, 30, 10, 20, 40, 50, 40, 30};removeDuplicates(input); // 输出：10 20 30 40 50return 0;
}

代码说明

1. Bitmap类：
   • set(int num)：将数字 num 对应的位设置为1，表示该数字已存在。
   • get(int num)：检查数字 num 是否已经存在。
2. removeDuplicates函数：
   • 输入一个整数数组 input。
   • 使用位图记录已出现的数字，跳过重复数字，将未重复数字加入结果集。
3. 空间效率：
   • 如果数据范围为0到999999，则需要约125 KB内存（1000000/8字节）。
4. 时间效率：
   • 遍历输入数组的时间复杂度为 O(n)，其中 n是数组的大小。
   • 设置和查询位图的复杂度为 O(1)。

布尔状态管理

#include <iostream>
#include <vector>
using namespace std;class Bitmap {
private:vector<unsigned char> bitmap; // 位图存储size_t size;                 // 位图支持的最大位数public:Bitmap(size_t size) : size(size) {bitmap.resize((size + 7) / 8, 0); // 每8个布尔状态占用1字节}// 设置某个位为1（开）void setOn(int num) {if (num >= size) return; // 越界检查bitmap[num / 8] |= (1 << (num % 8));}// 设置某个位为0（关）void setOff(int num) {if (num >= size) return; // 越界检查bitmap[num / 8] &= ~(1 << (num % 8));}// 查询某个位的状态bool isOn(int num) const {if (num >= size) return false; // 越界检查return bitmap[num / 8] & (1 << (num % 8));}// 打印所有状态void printStatus() const {for (size_t i = 0; i < size; ++i) {cout << "Device " << i << ": " << (isOn(i) ? "ON" : "OFF") << endl;}}
};int main() {const int NUM_DEVICES = 10000; // 管理10000个设备Bitmap devices(NUM_DEVICES);// 设置一些设备为开devices.setOn(1);devices.setOn(100);devices.setOn(9999);// 查询设备状态cout << "Device 1: " << (devices.isOn(1) ? "ON" : "OFF") << endl;   // 输出：ONcout << "Device 2: " << (devices.isOn(2) ? "ON" : "OFF") << endl;   // 输出：OFF// 设置设备100为关devices.setOff(100);// 查询状态cout << "Device 100: " << (devices.isOn(100) ? "ON" : "OFF") << endl; // 输出：OFF// 打印前10个设备状态for (int i = 0; i < 10; ++i) {cout << "Device " << i << ": " << (devices.isOn(i) ? "ON" : "OFF") << endl;}return 0;
}

代码说明

1. 位图操作：
   • setOn(int num)：将设备编号对应的位设置为1（设备开）。
   • setOff(int num)：将设备编号对应的位清零（设备关）。
   • isOn(int num)：检查设备编号对应的位是否为1。
2. 存储空间效率：
   • 如果管理10,000个设备，每个设备1位，需要10,000/8=1250字节（约1.25 KB）。
   • 相比直接用布尔数组（10,000字节），空间节省了约8倍。
3. 时间效率：
   • 查询、设置的时间复杂度为 O(1)。

布隆过滤器

定义

布隆过滤器是一种基于位图的概率性数据结构，用于判断某个元素是否在集合中。它可能存在假阳性（误判元素存在），但不会有假阴性（漏判元素不存在）。

特点

• 高效存储：用较小的空间表示大数据集。
• 高效查询：查询时间复杂度 O(k)，k为哈希函数的数量。
• 不可删除元素：经典布隆过滤器不支持删除。

应用

1. 初始化一个大小为 m 的位数组，将所有位初始化为0。
2. 对于一个元素 x，通过 k 个哈希函数计算其哈希值，并将对应位置的位设为1。
3. 查询时，用同样的 k 个哈希函数检查这些位是否都为1，若全为1，则判断元素可能存在，否则不存在。

#include <iostream>
#include <vector>
#include <functional>
using namespace std;class BloomFilter {
private:vector<bool> bitArray; // 位数组vector<hash<int>> hashFuncs; // 哈希函数集合size_t size;public:BloomFilter(size_t size, int numHashFuncs) : size(size), bitArray(size, false) {for (int i = 0; i < numHashFuncs; ++i) {hashFuncs.push_back(hash<int>()); // 简单使用std::hash}}void insert(int key) {for (auto& hashFunc : hashFuncs) {size_t index = hashFunc(key) % size;bitArray[index] = true;}}bool contains(int key) {for (auto& hashFunc : hashFuncs) {size_t index = hashFunc(key) % size;if (!bitArray[index]) return false;}return true;}
};int main() {BloomFilter bf(100, 3); // 位数组大小为100，使用3个哈希函数bf.insert(10);bf.insert(20);cout << bf.contains(10) << endl; // 输出1cout << bf.contains(30) << endl; // 输出0（一定不存在）cout << bf.contains(20) << endl; // 输出1（可能存在）return 0;
}

位图和布隆过滤器对比

特性	位图	布隆过滤器
存储效率	高	更高
查询效率	快速	快速
误判率	无误判	存在假阳性
数据删除	支持	不支持（需要Counting Bloom）
典型应用	离散集合、计数	大规模数据集查询过滤

应用场景

• 位图：数据去重、位标记、快速布尔状态存储。
• 布隆过滤器：URL去重、缓存预加载、推荐系统中的快速判别过滤。

源码解读（redis中的bitmap）

存储结构

Redis 使用字符串类型存储 Bitmap。

• 每个字符串可以存储多个字节（最多 512MB），而位操作直接基于字符串的二进制位进行。
• 因为 Bitmap 是字符串的扩展功能，其底层存储依赖 sds（Simple Dynamic String）。

sds 源码文件：

• sds.h
• sds.c

Bitmap 数据存储： Bitmap 数据实际上以字符串形式存储在 robj 结构体中，定义在 object.c：

struct redisObject {unsigned type : 4;      /* 数据类型（如 String、Hash） */unsigned encoding : 4;  /* 编码方式（如 RAW、INT 等） */void *ptr;              /* 实际数据的指针 */
};

对于 Bitmap，type 是字符串类型 (REDIS_STRING)，而 encoding 通常为 RAW 或 EMBSTR，表示底层是动态字符串。

核心命令实现

（1）SETBIT key offset value

设置指定位的值。

• 命令格式： SETBIT key offset value
  • key 是存储 Bitmap 的 Redis 键。
  • offset 是位的偏移量。
  • value 是要设置的值（0 或 1）。
• 实现逻辑：
  1. 计算 offset 所属的字节位置：byte = offset / 8。
  2. 计算在字节中的位偏移量：bit = offset % 8。
  3. 如果 key 的值不足以存储该位，Redis 会自动扩展字符串长度。
  4. 使用位运算修改指定位。
• 源码位置： t_string.c

void setbitCommand(client *c) {long long offset, byte, bit;robj *o;size_t bitoffset;int byteval;/* 获取 offset 参数并校验范围 */if (getLongLongFromObjectOrReply(c, c->argv[2], &offset, NULL) != C_OK)return;if (offset < 0 || ((unsigned long long)offset >> 3) >= 512*1024*1024) {addReplyError(c, "bit offset is not an integer or out of range");return;}/* 获取 value 参数并校验 */if (strcmp(c->argv[3]->ptr, "0") && strcmp(c->argv[3]->ptr, "1")) {addReplyError(c, "bit value is not 0 or 1");return;}/* 获取或创建字符串对象 */o = lookupKeyWrite(c->db, c->argv[1]);if (o == NULL) {if (strcmp(c->argv[3]->ptr, "0") == 0) {addReply(c, shared.czero);return; /* 位是0，无需修改 */}o = createObject(OBJ_STRING, sdsnewlen(NULL, byte + 1));dbAdd(c->db, c->argv[1], o);}/* 修改指定位 */byte = offset / 8;bit = 7 - (offset % 8);byteval = ((unsigned char *)o->ptr)[byte];byteval &= ~(1 << bit); /* 清零 */byteval |= (bitval << bit); /* 置位 */((unsigned char *)o->ptr)[byte] = byteval;addReply(c, shared.cone);
}

（2）GETBIT key offset

获取指定位的值。

• 命令格式： GETBIT key offset
• 实现逻辑：
  1. 计算 offset 对应的字节和位位置。
  2. 如果 offset 超出字符串的长度，返回 0。
  3. 读取目标字节并通过位运算提取目标位。
• 源码实现：

void getbitCommand(client *c) {robj *o;long long offset;unsigned char *bitmap;size_t byte, bit;int bitval = 0;/* 获取 offset 参数 */if (getLongLongFromObjectOrReply(c, c->argv[2], &offset, NULL) != C_OK)return;/* 计算字节和位位置 */byte = offset / 8;bit = 7 - (offset % 8);/* 获取字符串对象 */o = lookupKeyRead(c->db, c->argv[1]);if (o != NULL && o->type == OBJ_STRING) {bitmap = o->ptr;if (byte < sdslen(bitmap)) {bitval = bitmap[byte] & (1 << bit);}}addReplyLongLong(c, bitval ? 1 : 0);
}

（3）BITCOUNT key [start end]

统计 Bitmap 中设置为 1 的位数。

• 命令格式： BITCOUNT key [start end]
• 实现逻辑：
  1. 读取字符串中每个字节，逐字节统计 1 的数量。
  2. 如果指定了范围 [start, end]，只计算范围内的位。
• 源码实现：

void bitcountCommand(client *c) {robj *o;long start, end;size_t bitcount = 0;/* 获取并校验范围 */if (getRangeFromObjectOrReply(c, c->argv[2], c->argv[3], &start, &end) != C_OK)return;/* 获取字符串对象 */o = lookupKeyRead(c->db, c->argv[1]);if (o && o->type == OBJ_STRING) {unsigned char *bitmap = o->ptr;size_t len = sdslen(bitmap);/* 遍历字节统计 1 的数量 */for (size_t i = start; i <= end && i < len; i++) {bitcount += __builtin_popcount(bitmap[i]);}}addReplyLongLong(c, bitcount);
}

Redis Bitmap 的常见优化

1. 延迟创建字符串： 如果设置的位是 0，Redis 不会立即分配内存存储字符串。
2. 按需扩展： 设置位时，如果超过当前字符串长度，Redis 会自动扩展存储。
3. 低层优化： Redis 利用 CPU 指令，如 __builtin_popcount 快速统计 1 的数量。

应用场景

1. 用户签到：记录每天用户是否签到。
2. 状态管理：如设备是否可用。
3. 去重与快速过滤：记录某项操作是否完成。