这个问题是典型的海量数据处理场景（类似“大数据去重”问题），需要巧妙利用有限内存。下面是详细解决方案和优化策略：
一、问题分析
已知条件：
40亿个QQ号（假设每个QQ号8字节，原始数据约 32GB）
只有1GB内存可用
需要去重，保留唯一QQ号
关键限制：
内存放不下全部数据
硬盘空间足够（可以存储中间文件）
时间效率需要合理
二、解决方案（多层次）
方案1：哈希分片法（最可靠）
# 伪代码描述流程 def deduplicate_huge_data(): # 步骤1：哈希分片到多个小文件 for qq in read_all_qq(): hash_value = hash(qq) % 1024 # 分成1024个文件 write_to_file(f"part_{hash_value}.txt", qq) # 步骤2：逐个文件去重（内存中处理） unique_qq = [] for i in range(1024): qq_list = read_file(f"part_{i}.txt") # 1GB内存可容纳约1.3亿个QQ号（每个8字节） # 每个文件约4000万个QQ号，内存足够 unique_set = set(qq_list) # 去重 write_to_file(f"unique_{i}.txt", unique_set) # 步骤3：合并结果 merge_all_unique_files()分片数量计算：
40亿 ÷ 1.3亿 ≈ 31 但需要预留内存给其他操作，建议分1024个文件： 每个文件约 4000万QQ号，占用内存约320MB方案2：位图法（BitMap）优化版
适用于QQ号范围相对集中的情况：
// 两层位图方案 public class QQDeduplication { // 假设QQ号范围在10亿以内（实际情况QQ号目前最大11位） private static final long MAX_QQ = 10_0000_0000L; // 100亿 public void deduplicate() { // 第一层：布隆过滤器（Bloom Filter）快速过滤 BloomFilter bloomFilter = createBloomFilter(); // 第二层：分段位图 // 将100亿范围分成1000个段，每段1亿 int segmentSize = 100_000_000; // 1亿 int segments = (int)(MAX_QQ / segmentSize) + 1; for (int seg = 0; seg < segments; seg++) { // 当前段的位图：1亿位 ≈ 12.5MB BitSet bitSet = new BitSet(segmentSize); // 扫描原始数据，处理属于当前段的QQ号 for (long qq : readAllQQNumbers()) { if (qq / segmentSize == seg) { long offset = qq % segmentSize; if (!bitSet.get((int)offset)) { bitSet.set((int)offset); writeUniqueQQ(qq); } } } } } }内存计算：
每个段1亿QQ号，位图大小：1亿位 ÷ 8 = 12.5MB
加上程序开销，远小于1GB
方案3：外部排序+去重
# Linux系统命令组合方案 # 步骤1：分割大文件（假设原始文件为qq.txt） split -l 10000000 qq.txt qq_part_ # 步骤2：对每个小文件排序去重 for file in qq_part_*; do sort -u $file > ${file}_sorted done # 步骤3：多路归并去重 sort -m -u qq_part_*_sorted > qq_unique.txtJava实现外部排序：
public class ExternalSortDeduplicate { public void externalSort(String inputFile, String outputFile) throws IOException { int maxLines = 50000000; // 每批处理5000万行 List<String> chunkFiles = new ArrayList<>(); // 1. 分批读取、排序、去重、写入临时文件 try (BufferedReader br = new BufferedReader(new FileReader(inputFile))) { List<Long> buffer = new ArrayList<>(maxLines); String line; int chunkNum = 0; while ((line = br.readLine()) != null) { buffer.add(Long.parseLong(line)); if (buffer.size() >= maxLines) { // 排序去重 Collections.sort(buffer); String chunkFile = writeUniqueChunk(buffer, chunkNum++); chunkFiles.add(chunkFile); buffer.clear(); } } // 处理最后一批 if (!buffer.isEmpty()) { Collections.sort(buffer); String chunkFile = writeUniqueChunk(buffer, chunkNum); chunkFiles.add(chunkFile); } } // 2. 多路归并 mergeSortedChunks(chunkFiles, outputFile); // 3. 清理临时文件 for (String chunkFile : chunkFiles) { new File(chunkFile).delete(); } } // 多路归并实现 private void mergeSortedChunks(List<String> chunkFiles, String output) throws IOException { PriorityQueue<QueueElement> pq = new PriorityQueue<>(); // 打开所有文件，读取第一行 List<BufferedReader> readers = new ArrayList<>(); for (String chunkFile : chunkFiles) { BufferedReader reader = new BufferedReader(new FileReader(chunkFile)); readers.add(reader); String line = reader.readLine(); if (line != null) { pq.offer(new QueueElement(Long.parseLong(line), readers.size() - 1)); } } try (BufferedWriter bw = new BufferedWriter(new FileWriter(output))) { Long lastOutput = null; while (!pq.isEmpty()) { QueueElement current = pq.poll(); // 去重：只输出与前一个不同的数 if (lastOutput == null || !current.value.equals(lastOutput)) { bw.write(current.value.toString()); bw.newLine(); lastOutput = current.value; } // 从同一文件读取下一行 BufferedReader reader = readers.get(current.fileIndex); String line = reader.readLine(); if (line != null) { pq.offer(new QueueElement(Long.parseLong(line), current.fileIndex)); } } } // 关闭所有reader for (BufferedReader reader : readers) { reader.close(); } } }三、实际生产环境中的优化方案
方案4：MapReduce分布式处理（如果允许）
// Hadoop MapReduce示例 public class QQDeduplicationMR { public static class DedupMapper extends Mapper<Object, Text, Text, NullWritable> { private Text qq = new Text(); public void map(Object key, Text value, Context context) throws IOException, InterruptedException { // QQ号作为key，MapReduce会自动去重 qq.set(value.toString().trim()); context.write(qq, NullWritable.get()); } } public static void main(String[] args) throws Exception { Configuration conf = new Configuration(); Job job = Job.getInstance(conf, "QQ Deduplication"); job.setJarByClass(QQDeduplicationMR.class); job.setMapperClass(DedupMapper.class); job.setReducerClass(Reducer.class); // 使用默认Reducer去重 job.setOutputKeyClass(Text.class); job.setOutputValueClass(NullWritable.class); FileInputFormat.addInputPath(job, new Path(args[0])); FileOutputFormat.setOutputPath(job, new Path(args[1])); System.exit(job.waitForCompletion(true) ? 0 : 1); } }方案5：数据库辅助方案
-- 使用数据库临时表（如果有数据库可用） -- 步骤1：创建临时表（带索引） CREATE TABLE temp_qq ( qq_number BIGINT PRIMARY KEY ) ENGINE = MEMORY; -- 使用内存表 -- 步骤2：分批插入（每次插入1000万条） -- 由于主键约束，重复的会被忽略 INSERT IGNORE INTO temp_qq VALUES (...); -- 步骤3：导出唯一结果 SELECT qq_number FROM temp_qq INTO OUTFILE 'unique_qq.txt';方案6：布隆过滤器 + 磁盘存储
// 使用Guava的布隆过滤器 public class BloomFilterSolution { public void deduplicate(String inputFile, String outputFile) throws IOException { // 布隆过滤器参数：预期40亿元素，错误率0.1% BloomFilter<Long> bloomFilter = BloomFilter.create(Funnels.longFunnel(), 4_000_000_000L, 0.001); Set<Long> memoryCache = new HashSet<>(10_000_000); // 内存缓存1千万 try (BufferedReader br = new BufferedReader(new FileReader(inputFile)); BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile))) { String line; while ((line = br.readLine()) != null) { long qq = Long.parseLong(line); if (!bloomFilter.mightContain(qq)) { // 肯定不重复 bloomFilter.put(qq); memoryCache.add(qq); bw.write(line); bw.newLine(); } else if (!memoryCache.contains(qq)) { // 可能重复，需要进一步检查 // 这里可以查询磁盘上的已存在记录 if (!checkInDiskStorage(qq)) { memoryCache.add(qq); bw.write(line); bw.newLine(); } } // 定期清理内存缓存 if (memoryCache.size() > 10_000_000) { memoryCache.clear(); } } } } }四、性能对比与选择建议
| 方案 | 内存占用 | 磁盘IO | 时间复杂度 | 适用场景 |
|---|---|---|---|---|
| 哈希分片 | 低 | 中等 | O(n) | 通用，最稳定 |
| 位图分段 | 低 | 高 | O(n*k) | QQ号范围集中 |
| 外部排序 | 中等 | 高 | O(n log n) | 需要有序输出 |
| MapReduce | 低 | 高 | O(n) | 分布式环境 |
| 数据库 | 高 | 低 | O(n) | 有数据库可用 |
| 布隆过滤器 | 极低 | 低 | O(n) | 允许极小误差 |
五、生产环境最佳实践
推荐方案：哈希分片 + 内存去重
public class ProductionSolution { public static void main(String[] args) throws Exception { // 参数配置 int numShards = 1024; // 分片数 int batchSize = 10_000_000; // 每批处理1000万 // 阶段1：哈希分片 List<File> shardFiles = hashSharding("qq_input.txt", numShards); // 阶段2：并行处理每个分片 ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()); List<Future<File>> futures = new ArrayList<>(); for (File shardFile : shardFiles) { futures.add(executor.submit(() -> processShard(shardFile))); } // 阶段3：合并结果 List<File> resultFiles = new ArrayList<>(); for (Future<File> future : futures) { resultFiles.add(future.get()); } mergeResults(resultFiles, "qq_unique.txt"); executor.shutdown(); } private static File processShard(File shardFile) throws IOException { // 使用HashSet去重（适合分片后数据量） Set<Long> uniqueSet = new HashSet<>(); try (BufferedReader br = new BufferedReader(new FileReader(shardFile))) { String line; while ((line = br.readLine()) != null) { uniqueSet.add(Long.parseLong(line)); } } // 写入临时结果文件 File resultFile = new File(shardFile.getPath() + ".unique"); try (BufferedWriter bw = new BufferedWriter(new FileWriter(resultFile))) { for (Long qq : uniqueSet) { bw.write(qq.toString()); bw.newLine(); } } return resultFile; } }内存优化技巧：
使用基本类型集合：
// 使用Trove库的LongHashSet，比Java HashSet节省内存 import gnu.trove.set.hash.TLongHashSet; TLongHashSet longSet = new TLongHashSet(10_000_000); // 内存占用：约8字节/元素 vs HashSet的~40字节/元素压缩存储：
// 使用变长编码存储QQ号 // 较短的QQ号占用更少字节分批处理：
// 控制每批数据量，防止OOM while (hasMoreData()) { List<Long> batch = readNextBatch(5_000_000); // 每批500万 processBatch(batch); System.gc(); // 显式触发GC }六、扩展思考
如果QQ号长度不一致（4-11位），可以考虑：
分长度处理：相同长度的QQ号一起处理
字典序排序：按字符串排序，然后去重
前缀树：对字符串形式的QQ号构建Trie树去重
对于超大规模数据（万亿级别），需要：
分布式计算（Spark/Flink）
列式存储 + 压缩
使用RoaringBitmap等高级数据结构
这个问题的核心是时间与空间的权衡，在内存限制下，通过分批、分片、外部排序等技术，实现海量数据去重。
