C++中利用磁盘空间高效存储unordered_set值的最优方案？

方案1：分治法（外部排序+归并去重） #

这是处理超大文件去重最成熟的方案，无需依赖特殊磁盘哈希库，核心逻辑是化整为零，先局部去重再全局去重：

• 步骤1：将大文件分割成多个内存可容纳的小文件
• 步骤2：对每个小文件用robin-hood哈希完成内存内去重，再将去重后内容排序
• 步骤3：归并所有排序后的小文件，归并时跳过重复行，输出最终结果

代码示例（C++） #

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <robin_hood.h>
#include <filesystem>

namespace fs = std::filesystem;

// 分割大文件为小文件
size_t split_file(const std::string& input_path, size_t max_chunk_size) {
    std::ifstream in(input_path);
    std::string line;
    size_t chunk_idx = 0;
    size_t current_size = 0;
    std::ofstream out;

    while (std::getline(in, line)) {
        if (current_size == 0 || current_size + line.size() > max_chunk_size) {
            if (out.is_open()) out.close();
            out.open("chunk_" + std::to_string(chunk_idx++) + ".tmp");
            current_size = 0;
        }
        out << line << '\n';
        current_size += line.size() + 1; // 包含换行符长度
    }
    return chunk_idx;
}

// 单个小文件去重并排序
void process_chunk(const std::string& chunk_path) {
    std::ifstream in(chunk_path);
    std::string line;
    robin_hood::unordered_set<std::string> seen;

    while (std::getline(in, line)) {
        seen.insert(line);
    }
    in.close();

    std::vector<std::string> sorted_lines(seen.begin(), seen.end());
    std::sort(sorted_lines.begin(), sorted_lines.end());

    std::ofstream out(chunk_path);
    for (const auto& l : sorted_lines) {
        out << l << '\n';
    }
}

// 归并所有排序后的小文件
void merge_chunks(const std::string& output_path, size_t chunk_count) {
    std::vector<std::ifstream> chunk_streams;
    std::vector<std::string> current_lines;
    std::string prev_line;

    // 初始化所有小文件流
    for (size_t i = 0; i < chunk_count; ++i) {
        chunk_streams.emplace_back("chunk_" + std::to_string(i) + ".tmp");
        std::string line;
        current_lines.push_back(std::getline(chunk_streams.back(), line) ? line : "");
    }

    std::ofstream out(output_path);
    bool has_data = true;

    while (has_data) {
        has_data = false;
        size_t min_idx = -1;
        std::string min_line;

        // 找出当前最小的非空行
        for (size_t i = 0; i < chunk_count; ++i) {
            if (!current_lines[i].empty()) {
                has_data = true;
                if (min_idx == -1 || current_lines[i] < min_line) {
                    min_idx = i;
                    min_line = current_lines[i];
                }
            }
        }

        // 输出非重复行
        if (has_data && min_line != prev_line) {
            out << min_line << '\n';
            prev_line = min_line;
        }

        // 读取对应文件的下一行
        if (min_idx != -1) {
            std::string next_line;
            current_lines[min_idx] = std::getline(chunk_streams[min_idx], next_line) ? next_line : "";
        }
    }

    // 清理临时文件
    for (size_t i = 0; i < chunk_count; ++i) {
        fs::remove("chunk_" + std::to_string(i) + ".tmp");
    }
}

int main() {
    const std::string input_file = "large_input.txt";
    const std::string output_file = "deduplicated_output.txt";
    const size_t max_chunk_size = 1024 * 1024 * 100; // 100MB/块，根据内存调整

    size_t chunk_count = split_file(input_file, max_chunk_size);
    for (size_t i = 0; i < chunk_count; ++i) {
        process_chunk("chunk_" + std::to_string(i) + ".tmp");
    }
    merge_chunks(output_file, chunk_count);

    return 0;
}

方案2：使用嵌入式KV存储（LevelDB/RocksDB） #

如果不想做分治排序，可直接用LevelDB/RocksDB这类磁盘优化的KV存储替代内存哈希。它们基于LSM树实现，读写性能远优于简单磁盘哈希，且支持高效的键存在性查询。

代码示例（LevelDB） #

#include <iostream>
#include <fstream>
#include <string>
#include <leveldb/db.h>
#include <filesystem>

namespace fs = std::filesystem;

int main() {
    leveldb::DB* db;
    leveldb::Options options;
    options.create_if_missing = true;
    leveldb::Status status = leveldb::DB::Open(options, "./deduplicate_temp_db", &db);
    if (!status.ok()) {
        std::cerr << "LevelDB打开失败: " << status.ToString() << std::endl;
        return 1;
    }

    std::ifstream in("large_input.txt");
    std::ofstream out("deduplicated_output.txt");
    std::string line;
    std::string dummy_value;

    while (std::getline(in, line)) {
        leveldb::Status s = db->Get(leveldb::ReadOptions(), line, &dummy_value);
        if (!s.ok()) { // 行不存在则写入DB和输出文件
            db->Put(leveldb::WriteOptions(), line, "");
            out << line << '\n';
        }
    }

    delete db;
    fs::remove_all("./deduplicate_temp_db"); // 清理临时DB文件
    return 0;
}

注：为避免哈希冲突，这里直接存储行内容而非哈希值；若需节省空间，可存储行哈希+行的片段做二次验证，防止碰撞导致误判。

方案3：布隆过滤器预过滤+磁盘存储 #

先用布隆过滤器快速过滤大概率重复的行，仅将疑似唯一的行送入磁盘存储（或内存哈希）做二次验证，能大幅减少磁盘IO次数。但布隆过滤器存在假阳性（可能误判唯一行为重复），必须配合二次验证。

核心流程 #

1. 第一遍扫描文件，将所有行的哈希加入布隆过滤器
2. 第二遍扫描文件，对布隆过滤器标记为“不存在”的行，用磁盘KV或内存哈希做真实存在性检查，输出唯一行

方案对比 #

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