使用C++高效移除文本文件重复行的最优内存方案

核心思路：用哈希摘要替代完整行存储 #

直接存储整行字符串内存开销大的核心原因是std::string的容量冗余、内存对齐开销，加上std::unordered_set的桶结构额外消耗，导致内存占用是原文件的5-10倍。换成固定长度的哈希摘要（比如64位、128位或160位哈希值），能把单条记录的内存占用从几十/几百字节压缩到8-20字节，内存占用直接降到原方案的1/10甚至更低，完全能在20GB内存限制下处理10GB文件。

具体实现步骤 #

1. 选择低碰撞率的哈希函数 #

• 追求速度优先：选非加密哈希如MurmurHash3、CityHash，速度比加密哈希快数倍，碰撞概率极低，满足绝大多数场景需求。
• 追求绝对无碰撞风险：选加密级哈希如SHA-1（160位）、SHA-256（256位），或同时存储两个不同哈希的组合（比如64位MurmurHash3 + 64位CityHash），进一步降低碰撞概率。

2. 用高效哈希集合替代标准库实现 #

std::unordered_set的桶结构内存利用率低，建议替换为：

• 第三方高效集合：如Abseil的absl::flat_hash_set或folly的folly::F14ValueSet，这类实现的内存利用率比标准库高30%-50%，同时保持O(1)的查找/插入性能。
• 自定义哈希表：如果不想引入依赖，可基于动态数组实现开放寻址法的哈希表，减少桶结构的额外开销。

3. 逐行处理流程（保证O(n)速度） #

• 大缓冲区IO：设置1MB以上的读写缓冲区，或用内存映射（mmap）读取文件，避免频繁小IO操作拖慢速度。
• 哈希计算与去重：逐行读取后计算哈希摘要，若哈希值未在集合中，则写入输出文件并将哈希值加入集合；若已存在则跳过。
• 碰撞处理：若需绝对避免误删，当检测到哈希重复时，需读取原行（或原行在输入文件的偏移量）与当前行对比，确认是否真的重复。可通过存储行偏移量替代完整行，进一步节省内存。

4. 极端场景：分块处理 #

如果10GB文件的哈希集合仍接近内存上限，可采用分块哈希+磁盘暂存：

• 用哈希函数将每行映射到N个临时文件（比如N=10），相同内容的行必然进入同一个临时文件。
• 对每个临时文件单独用上述哈希摘要方式去重，最后合并所有临时文件的结果。
• 该方式可将内存占用降到原方案的1/N，同时保持整体O(n)的时间复杂度。

C++代码示例 #

#include <fstream>
#include <string>
#include <absl/container/flat_hash_set.h>
#include <murmurhash3.h> // 引入MurmurHash3

// 计算字符串的64位MurmurHash3值
uint64_t compute_murmurhash(const std::string& str) {
    uint64_t hash[2];
    MurmurHash3_x64_128(str.c_str(), str.size(), 0x12345678, hash);
    return hash[0];
}

int main() {
    std::ifstream infile("input.txt", std::ios::binary);
    std::ofstream outfile("output.txt", std::ios::binary);
    std::string line;

    // 用flat_hash_set存储哈希值，内存效率更高
    absl::flat_hash_set<uint64_t> seen_hashes;

    // 设置1MB读写缓冲区，提升IO速度
    char buffer[1024 * 1024];
    infile.rdbuf()->pubsetbuf(buffer, sizeof(buffer));
    outfile.rdbuf()->pubsetbuf(buffer, sizeof(buffer));

    while (std::getline(infile, line)) {
        uint64_t hash = compute_murmurhash(line);
        if (seen_hashes.insert(hash).second) {
            outfile << line << '\n';
        }
        // 若需严格防碰撞，此处需添加原行对比逻辑（需额外存储行偏移）
    }

    return 0;
}

关键注意事项 #

• IO是速度瓶颈：必须用大缓冲区或内存映射，避免频繁的系统IO调用，确保整体处理速度接近磁盘读写极限。
• 哈希函数选择：根据业务场景权衡速度与碰撞风险，非加密哈希足以应对绝大多数普通文本去重需求。
• 内存对齐：自定义哈希集合时注意内存对齐，避免不必要的内存浪费。

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