01

60 秒回答模板

精确方案是流式读取 10G 文件，按 `hash(ip) % N` 写入多个桶文件，保证相同 IP 必须落到同一桶，并让最大桶能在 1G 内存内处理。然后逐桶加载，用 HashMap 统计该桶内每个 IP 的全局频次，再把每个计数结果送入大小为 10 的小根堆；堆顶是当前第 10 大，只有更高频的 IP 才替换。最后堆中就是全局 Top10。若单桶仍过大，增加桶数或二次分片；允许误差时才考虑 Count-Min Sketch。

考点 核心机制与工程取舍
难度 中高频面试题
回答目标 按定义、机制、场景讲清楚
02

深入解析

01

先明确精确性和内存口径

1G 内存不是只能看文件大小，还要估算唯一 IP 数、字符串或整数表示、HashMap entry 开销和堆对象开销。通常要把 IP 转成 32 位整数并预留安全系数。

02

哈希分片保证正确性

对每个 IP 使用同一个 hash 规则落桶，相同 IP 必须进入同一个桶。这样某个 IP 的所有出现次数都能在一个桶里被完整统计，不会被拆散到多个局部计数里。

03

桶内统计控制峰值内存

每次只加载一个桶文件，使用 HashMap 统计 `ip -> count`。处理完一个桶就把计数结果合并到全局小根堆并释放内存，峰值由最大桶决定。

04

小根堆合并全局 TopK

堆大小固定为 10。遍历所有桶内计数项时，堆未满就入堆；堆满后只有频次大于堆顶才替换。这样不用保存所有候选，也不会漏掉高频 IP。

05

倾斜和近似方案要分开讲

如果某个桶异常大，可以加大 N 或对该桶二次分片。Count-Min Sketch、Space-Saving 等近似算法省内存但有误差，只有题目允许近似时才能替代精确方案。

03

易错点

  • 没有保证相同 IP 落到同一个桶，导致频次被拆散。
  • 只说分治，不估算桶数、最大桶和 HashMap 内存上界。
  • 把每桶结果简单拼接，不用全局小根堆或排序合并。
  • 把近似算法当精确答案，却不说明误差和适用条件。
04

面试官追问

为什么不能直接全量 HashMap？

10G 文件里的唯一 IP 数和对象开销可能远超 1G，尤其用字符串和普通对象时内存放大会很明显。

某个桶仍然超过内存怎么办？

增加桶数、二次分片，或先把 IP 转整数减少内存。如果数据极端倾斜，单个超高频 IP 本身不占太多唯一键，但桶里其他唯一键仍要继续拆。

每个桶只取 Top10 再合并为什么要小心？

如果每个 IP 的完整频次已经在桶内算准，取每桶 Top10 再全局合并是可行的；但必须说明相同 IP 不跨桶，否则局部 TopK 会漏全局候选。

IP 频次相同怎么处理？

题目没要求时可任意；生产里要定义 tie-break，例如按 IP 数值、首次出现时间或字典序，保证结果可重复。