CodeWalk

海量数据TopK问题：从1TB数据中找出出现频率最高的100个单词

作者：屠龙少年 · 2026-05-30 12:55

给定1TB的文本文件，每行一个单词。单机内存只有8GB，请设计算法找出出现频率最高的100个单词。请解释MapReduce、堆(Heap/HashMap)和Trie树的多种解法，以及如何通过HashMap+小顶堆优化内存占用。

回答

屠龙少年

海量数据TopK经典解法：

解法1：MapReduce分治

  1. 分片：将1TB文件按行Hash分片到100个节点，每片~10GB
  2. 每个节点：统计单词频次→取TopK
  3. 合并：汇总所有节点的TopK，全局排序取Top100

解法2：单机HashMap+小顶堆（8GB内存优化）

import heapq, collections

class TopK:
    def __init__(self, k=100):
        self.k = k
        self.min_heap = []  # 小顶堆
        self.counter = collections.defaultdict(int)
    
    def process_chunk(self, chunk_words):
        # 1. 统计本批次频率
        local_counter = {}
        for w in chunk_words:
            local_counter[w] = local_counter.get(w, 0) + 1
        # 2. 合并到全局counter
        for w, c in local_counter.items():
            self.counter[w] += c
        # 3. 清理低频词释放内存
        if len(self.counter) > 10_000_000:
            self._clean_low_freq()
    
    def _clean_low_freq(self):
        # 保留Top 10M个最高频的词，裁剪低频词
        top_items = heapq.nlargest(10_000_000, 
            self.counter.items(), key=lambda x: x[1])
        self.counter = dict(top_items)

解法3：Trie树统计

  • 用Trie树（前缀树）压缩存储单词
  • 叶子节点记录频次
  • 遍历Trie取TopK
  • 适合单词重复率高的场景

复杂度：

  • 时间复杂度：O(NlogK)（N=总单词数，K=100）
  • 空间复杂度：O(唯一单词数)

关键点：不能一次性将所有单词加载到内存，必须分批处理+裁剪。