摘要：选择哈希函数：使用均匀分布的哈希函数（如MD5、SHA-1或自定义哈希），将每条数据映射到固定数量的分片中。分片数计算：假设每条数据平均占10字节，1G内存可存储约1亿条数据（实际需预留哈希表开销）。为确保安全，将数据分到100个文件中，每个文件最多包含100
解决方案：分片哈希去重法
在仅有1G内存的情况下处理10亿条数据的去重问题，可以采用分片哈希法，将大数据集分解为多个小文件处理。具体步骤如下：
1. 哈希分片：将数据分散到多个文件中
选择哈希函数：使用均匀分布的哈希函数（如MD5、SHA-1或自定义哈希），将每条数据映射到固定数量的分片中。分片数计算：假设每条数据平均占10字节，1G内存可存储约1亿条数据（实际需预留哈希表开销）。
为确保安全，将数据分到100个文件中，每个文件最多包含1000万条数据（10亿/100=1000万），即使全无重复也能装入内存。import Hashlibdef hash_shard(data, num_shards=100): # 计算哈希值并取模分片 hash_val = int(hashlib.md5(data).hexdigest, 16) return hash_val % num_shards
2. 分步处理每个文件
逐文件加载：依次读取每个分片文件到内存。内存去重：使用哈希表（如Python的set或字典）快速去重。写入结果：将去重后的数据写入最终输出文件。def process_shard(shard_file, output_file): seen = set with open(shard_file, 'r') as f_in, open(output_file, 'w') as f_out: for line in f_in: if line not in seen: seen.add(line) f_out.write(line)3. 合并所有分片结果
将所有分片的去重结果合并为最终文件，若分片间仍有重复（极小概率），可再次分片或直接合并（因同一数据必在同一分片已去重）。
# 合并所有分片输出cat output_shard_* > final_deduplicated_data.txt关键优化点
动态分片调整：监控分片文件大小，若某分片数据量接近内存极限，可动态增加分片数（如从100调整为200）。
高效哈希函数：
选择低碰撞、高速度的哈希算法（如MurmurHash），减少分片不均匀风险。
并行处理：
在多核环境下，可并行处理多个分片文件，提升整体速度。
复杂度分析
时间：O(N)，需两次全量数据读写（分片+去重）。空间：内存仅需存储单个分片的数据，完美适配1G限制。适用场景
数据分布均匀，哈希函数能有效分散重复项。允许磁盘IO时间换内存空间，适用于离线批处理。方法优点缺点分片哈希法精确去重，内存可控需多次磁盘IO外部排序法无需哈希，天然有序归并复杂度高，速度慢布隆过滤器内存极省，速度快存在误判，不精确通过分片哈希法，可在有限内存下高效完成10亿级数据去重，平衡时间与空间复杂度，是此类问题的经典解法。
来源：柯梧教育
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!
