求大量64位整数向量并集的高效算法需求

针对你提到的「100万个含1万个64位整数的向量分批输入、内存不足、允许10%误报但严禁漏报」的场景，std::unordered_set因需存储完整整数导致内存占用过高，并非最优选择，以下是更适配的方案：

首选方案：布隆过滤器（Bloom Filter） #

这是完全贴合需求的概率型数据结构，核心特性完美匹配约束：

• 严禁漏报：只要布隆过滤器判定某整数不存在，该整数一定是新的（无漏报）；判定存在时可能是重复或误报（符合10%误报允许范围）。
• 极低内存占用：无需存储完整整数，仅用位图标记哈希映射位置，内存消耗比std::unordered_set低1-2个数量级。
• 支持分批增量处理：每批向量可直接增量插入过滤器，无需加载全量数据。

关键参数计算（控制误报率在10%） #

根据布隆过滤器公式，已知允许误报率p=0.1，预估去重后总整数数量n（比如按总数据量的20%估算，即100万×1万×0.2=2e8）：

• 位图总位数m = -n × ln(p) / (ln2)²，代入数值后约为6.64e8位≈83MB，内存占用极低。
• 哈希函数数量k = ln2 × (m/n)，计算后约为3个，平衡误报率和性能。

C++实现示例 #

#include <vector>
#include <cstdint>
#include <cmath>

// 高效非加密哈希：MurmurHash3 64位实现
uint64_t murmurhash3_64(const uint64_t* key, uint64_t seed) {
    uint64_t h = seed;
    uint64_t k = *key;
    k *= 0xc6a4a7935bd1e995;
    k ^= k >> 47;
    k *= 0xc6a4a7935bd1e995;
    h ^= k;
    h *= 0xc6a4a7935bd1e995;
    h ^= h >> 47;
    h *= 0xc6a4a7935bd1e995;
    h ^= h >> 47;
    return h;
}

class BloomFilter {
private:
    std::vector<uint64_t> bitmap;
    size_t total_bits;
    size_t hash_count;

    size_t get_bit_position(uint64_t hash) const {
        return hash % total_bits;
    }

public:
    // 构造函数：n=预估去重后整数数量，p=允许误报率
    BloomFilter(size_t n, double p) {
        const double ln2 = 0.6931;
        total_bits = static_cast<size_t>(-n * log(p) / (ln2 * ln2));
        // 对齐到64位，优化位图存储效率
        total_bits = ((total_bits + 63) / 64) * 64;
        hash_count = static_cast<size_t>(ln2 * (total_bits / n));
        bitmap.resize(total_bits / 64, 0);
    }

    // 插入整数到过滤器
    void insert(uint64_t num) {
        for (size_t i = 0; i < hash_count; ++i) {
            uint64_t hash = murmurhash3_64(&num, i);
            size_t pos = get_bit_position(hash);
            bitmap[pos / 64] |= 1ULL << (pos % 64);
        }
    }

    // 判断整数是否可能存在（false=肯定不存在，true=可能存在/误报）
    bool might_exist(uint64_t num) const {
        for (size_t i = 0; i < hash_count; ++i) {
            uint64_t hash = murmurhash3_64(&num, i);
            size_t pos = get_bit_position(hash);
            if (!(bitmap[pos / 64] & (1ULL << (pos % 64)))) {
                return false;
            }
        }
        return true;
    }
};

// 分批处理逻辑
void process_batch(const std::vector<std::vector<uint64_t>>& batch, BloomFilter& filter, std::vector<uint64_t>& unique_nums) {
    for (const auto& vec : batch) {
        for (uint64_t num : vec) {
            if (!filter.might_exist(num)) {
                filter.insert(num);
                unique_nums.push_back(num);
            }
            // 若filter返回true，直接跳过（可能是重复或误报，符合误报允许规则）
        }
    }
}

方案优势对比std::unordered_set #

• 内存：处理2e8个去重整数，布隆过滤器仅需约83MB，而std::unordered_set需约1.6GB（2e8×8字节），内存占用降低95%以上。
• 性能：插入/查询时间复杂度为O(k)（k=3），接近std::unordered_set的平均O(1)，但内存优势完全抵消微小的性能差异。
• 扩展性：支持跨批次持久化（将bitmap序列化到磁盘），适合长期分批处理场景。

注意事项 #

1. 预估数量准确性：尽量准确估算去重后的整数总量，若预估偏小会导致误报率升高；可适当高估（比如按总数据量的30%估算）。
2. 哈希函数选择：务必使用质量稳定的非加密哈希（如MurmurHash3、CityHash），避免std::hash<uint64_t>可能的哈希碰撞集中问题。
3. 误报率调整：若实际误报率超过10%，可增大位图大小或增加哈希函数数量（最多不超过5个，避免性能下降）。

内容的提问来源于stack exchange，提问作者user416983