位图 (Bitmap)

位图是一种基于哈希映射思想的高效数据结构。由于计算机中最小的存储单位是比特（bit），且一个比特位可以表示 0 或 1 两种状态，我们可以利用这一特性来标记某个数据是否存在。在处理海量整数时，位图能极大地节省内存空间。

#include <iostream>
#include <vector>
#include <cstdint>

/**
 * N 为数据范围（最大整数值）
 */
template<std::size_t N>
class FastBitmap {
public:
    FastBitmap() {
        // 使用 uint64_t 减少位运算频率，提高效率
        storage_.resize((N >> 6) + 1, 0);
    }

    // 将对应数值的位置标记为 1
    void Mark(std::size_t val) {
        std::size_t block_idx = val >> 6;      // 相当于 val / 64
        std::size_t bit_offset = val & 0x3F;  // 相当于 val % 64
        storage_[block_idx] |= (1ULL << bit_offset);
    }

    // 将对应数值的位置重置为 0
    void Erase(std::size_t val) {
        std::size_t block_idx = val >> 6;
        std::size_t bit_offset = val & 0x3F;
        storage_[block_idx] &= ~(1ULL << bit_offset);
    }

    // 检测数值是否存在
    bool Exists(std::size_t val) const {
        std::size_t block_idx = val >> 6;
        std::size_t bit_offset = val & 0x3F;
        return storage_[block_idx] & (1ULL << bit_offset);
    }

private:
    std::vector<std::uint64_t> storage_;
};

海量数据场景应用

• 检测整数是否存在： 给定 100 亿个整数（假设范围在 42 亿以内，即 unsigned int），只需约 512MB 内存构建位图。遍历数据并将对应位置设为 1，查询 X 时直接通过位图索引即可。
• 查找只出现一次的整数： 一个比特位只能表示 0/1，无法区分"出现 1 次"与"出现多次"。可以使用 2 个比特位表示一个数据的状态：00（未出现）、01（出现 1 次）、10（出现 2 次及以上）。通过两个位图对象协同操作，或者建立一个 2-bit 位图即可解决。
• 求两个海量整数文件的交集： 内存限制 1G 时，分别为两个文件的数据建立位图。对两个位图进行按位与（AND）操作，结果中为 1 的位即为交集元素。
• 查找出现次数不超过 2 次的整数： 同样利用 2 个比特位，定义四种状态：00（0次）、01（1次）、10（2次）、11（3次及以上）。遍历结束后，状态为 01 或 10 的即为目标数据。

布隆过滤器 (Bloom Filter)

布隆过滤器是哈希冲突的一种巧妙应用。在位图中，一个位置只能对应一个数据，当处理字符串等非数值类型时，哈希冲突会导致严重的误判。布隆过滤器通过引入多个哈希函数，将一个数据映射到多个比特位上，从而降低误判率。

布隆过滤器的核心结论：

• 如果查询结果显示数据不存在，那么该数据一定不存在（可靠）。
• 如果查询结果显示数据存在，那么该数据可能存在，也可能是因为哈希冲突产生的误判（不可靠）。

#include <string>
#include <bitset>
#include <vector>

struct BKDRHasher {
    std::size_t operator()(const std::string& s) {
        std::size_t hash = 0;
        for (char c : s) hash = hash * 131 + c;
        return hash;
    }
};

struct APHasher {
    std::size_t operator()(const std::string& s) {
        std::size_t hash = 0;
        for (std::size_t i = 0; i < s.size(); i++) {
            if ((i & 1) == 0) hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
            else hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
        }
        return hash;
    }
};

struct DJBHasher {
    std::size_t operator()(const std::string& s) {
        std::size_t hash = 5381;
        for (char c : s) hash += (hash << 5) + c;
        return hash;
    }
};

/**
 * N: 预计插入的数据量
 * Scale: 空间放大因子，越大误判率越低
 */
template<std::size_t N, 
         std::size_t Scale = 5, 
         class K = std::string, 
         class F1 = BKDRHasher, 
         class F2 = APHasher, 
         class F3 = DJBHasher>
class BloomFilter {
public:
    void Add(const K& key) {
        std::size_t m = N * Scale;
        bits_.set(F1()(key) % m);
        bits_.set(F2()(key) % m);
        bits_.set(F3()(key) % m);
    }

    bool Contains(const K& key) {
        std::size_t m = N * Scale;
        // 只要有一个映射位为 0，说明数据一定不存在
        if (!bits_.test(F1()(key) % m)) return false;
        if (!bits_.test(F2()(key) % m)) return false;
        if (!bits_.test(F3()(key) % m)) return false;
        return true; // 此时可能存在误判
    }

private:
    std::bitset<N * Scale> bits_;
};

布隆过滤器常作为"过滤层"放置在昂贵的查询操作（如数据库磁盘查找）之前。如果布隆过滤器判断数据不存在，则无需访问数据库；只有当它判断存在时，才进行深度查找，从而极大减轻了底层系统的负载。