在10 亿个字符串中如何找到重复次数最多的前 100 个？

上面无邪的回答**简单的归并 100 个小文件的 Top 100 并直接用大顶堆选 100 个，会导致准确性问题**。如果某个小文件的字符串分布较特殊（比如某个字符串频次特别高），直接选取各小文件的 Top 100 可能会漏掉某些在全局范围内更常见的字符串。 ### **改进方案：多轮归并，确保准确性** 为了保证 **最终的 Top 100 是全局准确的**，我们需要 **两步归并**： 1. **第一步：分块统计 & 局部 Top K** - 每次读取 **1000 万个字符串**，用 **HashMap 统计频次**。 - 排序后 **保留所有字符串的完整计数**（而不是仅存 Top 100）。 - **写入磁盘**（如 `"chunk_1.txt"`），存储格式为： ``` 字符串1 频次1 字符串2 频次2 ... ``` - 这样，我们会得到 **100 个小文件**，每个小文件中存储该块中的所有字符串及其频次。 2. **第二步：全局归并 & 计算全局 Top 100** - 使用 **归并排序（Merge Sort）** 合并 100 个小文件，合并时保持 **字符串频次累加**。 - 维护 **全局哈希表（或堆）**，累加相同字符串的频次，最终得到全局最热的 Top 100。 ## **改进后的完整代码** ```java import java.io.*; import java.util.*; public class Top100FrequentStrings { private static final int CHUNK_SIZE = 10_000_000; // 每块1000万 private static final int TOP_K = 100; public static void main(String[] args) throws IOException { String inputFile = "bigdata.txt"; // 假设10亿字符串存储在这个文件 List<String> chunkFiles = splitIntoChunks(inputFile); // 归并所有小文件，得到全局Top 100 List<Map.Entry<String, Integer>> result = mergeChunks(chunkFiles); // 输出最终结果 System.out.println("Top 100 frequent strings:"); for (Map.Entry<String, Integer> entry : result) { System.out.println(entry.getKey() + " -> " + entry.getValue()); } } // **第一步：分块读取 & 统计频次** private static List<String> splitIntoChunks(String inputFile) throws IOException { BufferedReader reader = new BufferedReader(new FileReader(inputFile)); List<String> chunkFiles = new ArrayList<>(); Map<String, Integer> freqMap = new HashMap<>(); int count = 0, chunkIndex = 0; String line; while ((line = reader.readLine()) != null) { freqMap.put(line, freqMap.getOrDefault(line, 0) + 1); count++; if (count >= CHUNK_SIZE) { // 写入小文件，包含所有字符串的频次，而不仅仅是Top 100 String chunkFile = "chunk_" + chunkIndex++ + ".txt"; writeChunk(chunkFile, freqMap); chunkFiles.add(chunkFile); freqMap.clear(); count = 0; } } reader.close(); return chunkFiles; } // **写入小块的频次数据** private static void writeChunk(String chunkFile, Map<String, Integer> freqMap) throws IOException { BufferedWriter writer = new BufferedWriter(new FileWriter(chunkFile)); for (Map.Entry<String, Integer> entry : freqMap.entrySet()) { writer.write(entry.getKey() + " " + entry.getValue()); writer.newLine(); } writer.close(); } // **第二步：归并所有小文件，求全局Top 100** private static List<Map.Entry<String, Integer>> mergeChunks(List<String> chunkFiles) throws IOException { Map<String, Integer> globalFreqMap = new HashMap<>(); for (String chunkFile : chunkFiles) { BufferedReader reader = new BufferedReader(new FileReader(chunkFile)); String line; while ((line = reader.readLine()) != null) { String[] parts = line.split(" "); String key = parts[0]; int count = Integer.parseInt(parts[1]); globalFreqMap.put(key, globalFreqMap.getOrDefault(key, 0) + count); } reader.close(); } // 使用小顶堆维护全局Top 100 PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>( TOP_K, Map.Entry.comparingByValue()); for (Map.Entry<String, Integer> entry : globalFreqMap.entrySet()) { if (minHeap.size() < TOP_K) { minHeap.offer(entry); } else if (entry.getValue() > minHeap.peek().getValue()) { minHeap.poll(); minHeap.offer(entry); } } // 转换为列表并按降序排序 List<Map.Entry<String, Integer>> result = new ArrayList<>(minHeap); result.sort((a, b) -> b.getValue() - a.getValue()); return result; } } ``` ## **改进点** ### **✅ 为什么这样可以保证正确性？** 1. **分块存储完整计数信息**： - 之前的方法只存储 **每个块的 Top 100**，可能导致某些字符串频次低时被截断。 - 现在的改进是：**每个小文件都存储该块内的所有字符串及其频次**，确保所有字符串都能参与全局排名。 2. **全局归并频次累加**： - 读取所有小文件，并 **合并相同字符串的频次**，得到全局正确的频次数据。 3. **最终使用小顶堆筛选前 100**： - **避免哈希表占用过多内存**，仍然能保证只存储 Top 100。 ## **时间复杂度分析** | 步骤 | 计算量 | 复杂度 | |------|--------|----------| | **分块统计** | 读取 + HashMap 计数 | **O(N)** | | **写入小文件** | 按字符串写磁盘 | **O(N)** | | **归并所有数据** | 100 个文件 **全局归并** | **O(N)** | | **堆筛选 Top 100** | 维护 `O(100)` 规模的小顶堆 | **O(N log 100)** | - **总复杂度 ≈ `O(N) + O(N log 100) ≈ O(N)`** - 由于 `log 100 ≈ 7`，这个复杂度 **几乎等于 O(N)**，非常高效。 ## **总结** | 方法 | 适用场景 | 可能的问题 | 改进 | |------|---------|----------|----------| | **直接归并 Top 100** | **简单易实现** | **容易漏掉全局高频字符串** | ❌ | | **分块存完整计数 + 全局归并** | **保证正确性** | 需要归并大文件 | ✅ | ### **推荐方案** - **如果数据小于内存**（如几千万条）：用 **HashMap + 小顶堆**。 - **如果数据远超内存**（10 亿级）：**必须使用分块存储完整计数 + 全局归并**。 这样能 **保证前 100 结果的准确性**，同时 **不会因数据规模过大导致内存溢出**。

在 **10 亿个字符串** 中找到 **重复次数最多的前 100 个**，需要高效的处理方式。由于数据量巨大，可能无法全部放入内存，因此可以采用 **哈希计数 + 小顶堆** 或 **外部排序 + 归并** 来解决。 ## **方法 1：哈希表 + 小顶堆（适用于内存足够的情况）** ### **思路** 1. **使用 HashMap 统计每个字符串的出现次数**（`O(N)`）。 2. **使用小顶堆（Min Heap，size 100）维护前 100 个最高频字符串**（`O(N log 100)`）。 ### **时间复杂度** - **哈希计数**：`O(N)` - **堆操作（插入、删除）**：`O(log 100) ≈ O(7)`，总共 `O(N log 100)` - **最终排序**：`O(100 log 100)` 最终复杂度约为 `O(N log 100) ≈ O(N)` ### **代码** ```java import java.util.*; public class Top100FrequentStrings { public static void main(String[] args) { // 假设数据来源于一个超大文件或数据库 List<String> data = Arrays.asList("apple", "banana", "apple", "orange", "banana", "banana", "apple", "cherry"); // 1. 使用 HashMap 统计字符串频次 Map<String, Integer> freqMap = new HashMap<>(); for (String str : data) { freqMap.put(str, freqMap.getOrDefault(str, 0) + 1); } // 2. 用小顶堆维护前 100 个最大频次 PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(100, Map.Entry.comparingByValue()); for (Map.Entry<String, Integer> entry : freqMap.entrySet()) { if (minHeap.size() < 100) { minHeap.offer(entry); } else if (entry.getValue() > minHeap.peek().getValue()) { minHeap.poll(); minHeap.offer(entry); } } // 3. 取出 Top 100 List<Map.Entry<String, Integer>> result = new ArrayList<>(minHeap); result.sort((a, b) -> b.getValue() - a.getValue()); // 按频次降序排列 // 4. 输出结果 for (Map.Entry<String, Integer> entry : result) { System.out.println(entry.getKey() + " -> " + entry.getValue()); } } } ``` ## **方法 2：外部排序 + 归并（适用于超大数据集）** 如果 **10 亿个字符串** 超过 **内存限制**，则采用 **外部排序** 方法。 ### **思路** 1. **分块处理**： - 每次读取 **1000 万个字符串** 进入 **内存（HashMap 计数）**。 - 统计 **局部 Top 100** 并写入磁盘 **（排序存储）**。 - **共生成 100 个小文件，每个文件包含前 100 个热门字符串**。 2. **归并 Top 100**： - 归并 100 个小文件，使用 **大顶堆（最大堆）** 选出全局前 100。 ### **时间复杂度** - 读取并分块计数：`O(N)` - 归并 100 个小文件：`O(100 log 100)` - **总复杂度 ≈ `O(N) + O(100 log 100)` ≈ `O(N)`** ### **代码** ```java import java.io.*; import java.util.*; public class ExternalSortTop100 { private static final int CHUNK_SIZE = 10_000_000; // 每块1000万 private static final int TOP_K = 100; public static void main(String[] args) throws IOException { String inputFile = "bigdata.txt"; // 假设10亿字符串存储在这个文件 List<String> chunkFiles = splitIntoChunks(inputFile); // 归并小文件，得到全局前100 List<Map.Entry<String, Integer>> result = mergeChunks(chunkFiles); // 输出结果 System.out.println("Top 100 frequent strings:"); for (Map.Entry<String, Integer> entry : result) { System.out.println(entry.getKey() + " -> " + entry.getValue()); } } // 1. 读取文件并分块处理 private static List<String> splitIntoChunks(String inputFile) throws IOException { BufferedReader reader = new BufferedReader(new FileReader(inputFile)); List<String> chunkFiles = new ArrayList<>(); Map<String, Integer> freqMap = new HashMap<>(); int count = 0, chunkIndex = 0; String line; while ((line = reader.readLine()) != null) { freqMap.put(line, freqMap.getOrDefault(line, 0) + 1); count++; if (count >= CHUNK_SIZE) { // 写入小文件 String chunkFile = "chunk_" + chunkIndex++ + ".txt"; writeChunk(chunkFile, freqMap); chunkFiles.add(chunkFile); freqMap.clear(); count = 0; } } reader.close(); return chunkFiles; } // 2. 将小块的频次数据写入文件 private static void writeChunk(String chunkFile, Map<String, Integer> freqMap) throws IOException { List<Map.Entry<String, Integer>> sortedList = new ArrayList<>(freqMap.entrySet()); sortedList.sort((a, b) -> b.getValue() - a.getValue()); // 按频次降序排序 BufferedWriter writer = new BufferedWriter(new FileWriter(chunkFile)); for (int i = 0; i < Math.min(TOP_K, sortedList.size()); i++) { writer.write(sortedList.get(i).getKey() + " " + sortedList.get(i).getValue()); writer.newLine(); } writer.close(); } // 3. 归并小文件，得到最终 Top 100 private static List<Map.Entry<String, Integer>> mergeChunks(List<String> chunkFiles) throws IOException { PriorityQueue<Map.Entry<String, Integer>> maxHeap = new PriorityQueue<>( TOP_K, (a, b) -> b.getValue() - a.getValue()); for (String chunkFile : chunkFiles) { BufferedReader reader = new BufferedReader(new FileReader(chunkFile)); String line; while ((line = reader.readLine()) != null) { String[] parts = line.split(" "); String key = parts[0]; int count = Integer.parseInt(parts[1]); maxHeap.offer(new AbstractMap.SimpleEntry<>(key, count)); if (maxHeap.size() > TOP_K) { maxHeap.poll(); } } reader.close(); } // 转换为列表并按降序排序 List<Map.Entry<String, Integer>> result = new ArrayList<>(maxHeap); result.sort((a, b) -> b.getValue() - a.getValue()); return result; } } ``` ## **方法对比** | 方法 | 适用场景 | 时间复杂度 | 适用数据规模 | |------|---------|---------|-------------| | **哈希表 + 小顶堆** | **内存足够** | **O(N log 100)** | **10 亿以内** | | **外部排序 + 归并** | **数据太大（超内存）** | **O(N) + O(100 log 100)** | **10 亿以上** | ### **推荐方案** - **如果内存足够**（如 10GB RAM 可存储 1~2 亿条字符串）：用 **HashMap + 小顶堆**。 - **如果数据超大**（如 10 亿级别，超过内存）：用 **外部排序 + 归并**。 对于 **10 亿个字符串**，**推荐使用 "外部排序 + 归并" 方法**，可以高效处理超大数据集，并保证内存不会溢出。