17370845950

位图是一种高效数据结构，通过比特数组表示非负整数的存在状态，显著节省内存。例如，表示1千万个整数仅需约1.2MB，远低于传统方法的40MB。文章给出了C++实现，包含设置、清除、查询和翻转操作，利用uint32_t数组按位操作，支持去重、排序和快速查找。应用场景包括活跃用户统计、布隆过滤器及大文件内存映射，还可结合Roaring Bitmap优化。注意事项有：限非负整数、需边界检查、多线程保护和合理预估规模。

处理海量数据时，空间效率是关键。位图（Bitmap）是一种高效的数据结构，特别适用于去重、排序和快速查找等场景。它通过用一个比特位表示一个整数是否存在，将空间占用压缩到极致。

什么是位图

位图本质是一个比特数组，每个比特位代表一个非负整数的状态：0 表示不存在，1 表示存在。例如，要表示数字 5 是否存在，只需将第 5 个比特位置为 1。

相比使用 int 数组或哈希表，位图在存储大量稀疏整数时能节省大量内存。比如表示 1 千万个整数，传统方式可能需要 40MB（每个 int 4 字节），而位图仅需约 1.2MB（10^7 / 8 / 1024 / 1024 ≈ 1.19MB）。

手动实现一个简单的 C++ 位图

下面是一个基础但实用的 Bitmap 类，支持设置、清除、查询和翻转操作：

class Bitmap {
private:
    std::vector bits;
    size_t size;

public:
    explicit Bitmap(size_t n) : size(n) {
        bits.resize((n + 31) / 32, 0);
    }

    void set(size_t i) {
        if (i >= size) return;
        bits[i / 32] |= (1U << (i % 32));
    }

    void clear(size_t i) {
        if (i >= size) return;
        bits[i / 32] &= ~(1U << (i % 32));
    }

    bool get(size_t i) const {
        if (i >= size) return false;
        return (bits[i / 32] & (1U << (i % 32))) != 0;
    }

    void flip(size_t i) {
        if (i >= size) return;
        bits[i / 32] ^= (1U << (i % 32));
    }
};

说明：

• 使用 std::vector 存储比特位，每项管理 32 位。
• 通过 i / 32 定位到对应的整数单元，i % 32 确定具体比特位。
• 位运算 |= 设置位，&= ~() 清除位，^= 翻转位。
• 构造函数中 (n + 31) / 32 是向上取整，确保覆盖所有位。

位图的应用场景与优化技巧

位图在实际中有多种用途，尤其适合以下情况：

• 去重统计：如统计某日活跃用户 ID（假设 ID 范围 0~10^7），只需一个 1.2MB 的位图即可完成。
• 排序输出：遍历位图，遇到为 1 的位就输出对应索引，自然有序且无重复。
• 布隆过滤器底层：结合多个哈希函数，位图可作为概率性判断元素是否存在的基础结构。
• 内存映射文件配合大位图：若数据范围极大（如 0~2^32），可用 mmap 映射文件，避免一次性加载进内存。

对于超大数据集，还可考虑分段位图或压缩位图（如 Roaring Bitmap），进一步提升性能与空间利用率。

注意事项

• 位图只适合非负整数。若原始数据是字符串或负数，需先做映射转换。
• 注意边界检查，防止数组越界。
• 多线程环境下需加锁或使用原子操作保护共享位图。
• 合理预估最大值，避免分配过多内存。

基本上就这些。位图看似简单，但在海量数据处理中威力巨大。掌握它，能让程序在时间和空间上都更高效。