面试场景题100GB 日志文件统计接单最多的 Top10 车主这道题在面试里属于海量数据处理分类考的不是写 SQL 或调 API而是你在内存有限的约束下怎么思考问题。核心矛盾就一个100GB 的文件内存可能只有 4~8GB一次性加载不了怎么办先把题目拆清楚原始数据长这样一行一条日志driver_id,order_id,status D10001,OD20001,ACCEPTED D10001,OD20001,ARRIVED ← 同一个车主、同一个订单、不同状态 D10001,OD20001,COMPLETED ← 还是同一单要去重 D10001,OD20002,ACCEPTED ← 同一个车主、不同订单 D10002,OD20003,ACCEPTED ...要做的事去重相同driver_id order_id只算一个订单不管有多少种 status计数统计每个 driver_id 的去重后订单数排序取接单量最多的 Top 10难点在于100GB 文件内存放不下。思路一哈希分治面试首选答案这是最经典的解法也是面试官最想听到的。核心思想大文件放不下那就切成小文件每个小文件能放进内存。第一步哈希分片 —— 把大文件拆成小文件100GB 大文件 ↓ 逐行读取对 driver_id 取哈希 ↓ hash(driver_id) % N → 写入对应的小文件 ↓ file_0 file_1 file_2 ... file_N假设内存 4GB我们可以设 N100平均每个小文件约 1GBHashMap 能放得下。关键点按driver_id取哈希不是随机切分。这样保证了同一个车主的所有记录一定落在同一个小文件里后面每个小文件可以独立完成去重和计数不需要跨文件合并。// 伪代码哈希分片 int N 100; BufferedWriter[] writers new BufferedWriter[N]; // ... 初始化 N 个文件输出流 ​ try (BufferedReader reader new BufferedReader(new FileReader(huge_log.csv))) { String line; while ((line reader.readLine()) ! null) { String driverId line.split(,)[0]; int bucket (driverId.hashCode() 0x7FFFFFFF) % N; writers[bucket].write(line); writers[bucket].newLine(); } }注意 0x7FFFFFFF是为了把 hashCode 的负数变成正数不然取模会得到负的下标第二步逐个小文件处理 —— 去重 计数对每个小文件把它整个加载到内存里处理// 处理一个小文件 // key driver_id, value 该车主的去重订单集合 MapString, SetString driverOrders new HashMap(); ​ try (BufferedReader reader new BufferedReader(new FileReader(file_ i))) { String line; while ((line reader.readLine()) ! null) { String[] parts line.split(,); String driverId parts[0]; String orderId parts[1]; // status 直接忽略不参与去重 driverOrders.computeIfAbsent(driverId, k - new HashSet()) .add(orderId); // HashSet 自动去重 } } ​ // 转成 driver_id → 订单数 MapString, Integer driverCount new HashMap(); for (Map.EntryString, SetString entry : driverOrders.entrySet()) { driverCount.put(entry.getKey(), entry.getValue().size()); }这里用HashSetString存 orderId 来去重。同一个 driver_id order_id 不管出现多少次不同 statusSet 里只会存一份。第三步小顶堆取全局 Top 10每个小文件处理完会得到一批(driver_id, count)键值对。我们维护一个大小为 10 的小顶堆把所有小文件的结果都过一遍// 小顶堆堆顶是最小值 PriorityQueueint[] minHeap new PriorityQueue(10, (a, b) - a[1] - b[1] // 按 count 升序 ); ​ // 遍历每个小文件的 driverCount 结果 for (Map.EntryString, Integer entry : driverCount.entrySet()) { if (minHeap.size() 10) { minHeap.offer(new int[]{entry.getKey(), entry.getValue()}); } else if (entry.getValue() minHeap.peek()[1]) { // 比堆顶大踢掉堆顶放进来 minHeap.poll(); minHeap.offer(new int[]{entry.getKey(), entry.getValue()}); } } // 最终堆里就是全局 Top 10为什么用小顶堆而不是大顶堆因为我们要的是最大的 10 个。小顶堆的堆顶是当前 Top10 里最小的那个新来一个元素只要比堆顶大就有资格进来。堆始终保持大小为 10每次操作 O(log10) ≈ O(1)比全量排序高效得多。完整流程图100GB 原始文件 ↓ ① 逐行读按 driver_id 哈希分成 100 个小文件 ↓ file_0 file_1 file_2 ... file_99 ↓ ② 逐个加载到内存 HashSet 对 (driver_id, order_id) 去重 统计每个 driver_id 的订单数 ↓ D10001→35 D10002→12 D10003→28 ... (每个小文件产出一批 driver→count) ↓ ③ 所有结果过一遍小顶堆大小10 ↓ Top 10 车主按接单数降序复杂度分析阶段时间空间哈希分片O(n) 全量读一遍O(1) 只需要少量缓冲区单文件去重计数O(m) 每个文件内线性扫描O(m) HashMap HashSet小顶堆 Top10O(n log 10) ≈ O(n)O(10)总计O(n)两遍扫描O(100GB / 100) ≈ 1GB思路二两阶段去重优化内存上面思路一有个潜在问题如果某个车主特别活跃他的订单特别多那HashSetString存他所有的 orderId 可能很占内存。优化思路先去重再计数。分成两步走。第一步去重阶段还是哈希分片但这次按driver_id order_id的组合取哈希// 按 driver_id order_id 组合哈希分片 String key driverId _ orderId; int bucket (key.hashCode() 0x7FFFFFFF) % N;每个小文件内部用 HashSet 对driver_id order_id去重去重后写入中间文件每行只保留driver_id去重前file_0: 去重后dedup_0: D10001,OD20001,ACCEPTED D10001 D10001,OD20001,COMPLETED D10001 ← 这条被去掉了重复的 OD20001 D10001,OD20002,ACCEPTED D10001 D10002,OD20003,ACCEPTED D10002等等... 这样写出来的中间文件里同一个 driver_id 会出现多次每个去重后的订单一次后面计数的时候只要数每个 driver_id 出现了几次就行。第二步计数阶段对去重后的中间文件再按driver_id哈希分片一次然后用 HashMapString, Integer 计数。这次不用存 orderId 了HashMap 的 value 就是一个 int内存压力小很多。这个两阶段的方案适合订单量特别大、去重集合放不进内存的极端情况。代价是多了一轮磁盘 IO。思路三外部排序另一个经典思路先排序再计数。第一步外部排序对 100GB 文件按driver_id, order_id做外部排序External Sort把文件切成能装进内存的块比如每块 1GB每块在内存里排序后写回磁盘多路归并 —— 同时打开所有排序好的块文件用最小堆做 K 路归并输出全局有序的文件排序后数据长这样D10001,OD20001,ACCEPTED D10001,OD20001,ARRIVED ← 相邻且相同的 driverorder D10001,OD20001,COMPLETED ← 连续出现 D10001,OD20002,ACCEPTED D10001,OD20002,COMPLETED D10002,OD20003,ACCEPTED D10002,OD20004,ACCEPTED ...第二步顺序扫描 去重计数排好序之后相同 driver_id order_id 的记录一定是连续的直接顺序扫描就能去重 计数不需要 HashMapO(1) 内存就够了String prevDriver null, prevOrder null; int currentCount 0; PriorityQueueMap.EntryString, Integer minHeap ...; ​ while ((line reader.readLine()) ! null) { String[] parts line.split(,); String driverId parts[0], orderId parts[1]; ​ if (driverId.equals(prevDriver)) { // 同一个车主 if (!orderId.equals(prevOrder)) { // 新订单去重只有 orderId 变了才算新的一单 currentCount; prevOrder orderId; } // 否则是同一个订单的不同状态跳过 } else { // 换了一个车主把上一个的结果入堆 if (prevDriver ! null) { updateHeap(minHeap, prevDriver, currentCount); } prevDriver driverId; prevOrder orderId; currentCount 1; } } // 别忘了最后一个车主 updateHeap(minHeap, prevDriver, currentCount);这个方案的好处是计数阶段几乎不占内存只需要存上一行的 driver_id 和 order_id。代价是外部排序本身比较耗时需要多轮磁盘读写。思路四MapReduce分布式方案如果面试官追问如果数据量更大单机处理不了怎么办就聊 MapReduce100GB → Mapper 输入: driver_id,order_id,status 输出: driver_id_order_id, 1 ← key 是组合键自动去重 ↓ Shuffle Sort Reducer 输入: driver_id_order_id, [1,1,1] 去重: 每个 key 只计 1 次 输出: driver_id, 1 ↓ 第二轮 MR Reducer 按 driver_id 聚合求和 每个 Reducer 维护本地 Top10 小顶堆 cleanup() 输出本地 Top10 ↓ 单 Reducer 汇总 全局 Top 10或者更简洁的一轮方案// Mapper: 输出 driverId, orderId map(line) { emit(driverId, orderId); } ​ // Reducer: 收到某个 driverId 的所有 orderId用 Set 去重后计数 reduce(driverId, IteratororderId values) { SetString uniqueOrders new HashSet(); for (orderId : values) { uniqueOrders.add(orderId); } emit(driverId, uniqueOrders.size()); }然后再跑一轮 MR 或者在 Reducer 的cleanup()里用小顶堆取 Top10。思路五Linux 命令行快速验证用面试中提一嘴加分。虽然 100GB 跑起来很慢但逻辑上完全 work# 1. 提取 driver_id 和 order_id去掉 status 列 # 2. 排序 去重同一个 driverorder 只保留一行 # 3. 只保留 driver_id 列 # 4. 统计每个 driver_id 出现次数 # 5. 按次数降序排序 # 6. 取前 10 ​ cut -d, -f1,2 huge_log.csv \ | sort -u \ | cut -d, -f1 \ | sort \ | uniq -c \ | sort -rn \ | head -10一行搞定逻辑面试里能秀一下。但实际 100GB 文件sort命令的外部排序会很慢不过 GNU sort 默认就支持外部排序会自动用临时文件。各方案对比方案时间复杂度内存占用实现复杂度适用场景哈希分治O(n) 两遍扫~1GB中单机、面试首选外部排序O(n log n)O(1) 计数阶段中内存极度受限MapReduceO(n)分布式高数据量更大、有集群命令行O(n log n)系统管理低快速验证面试回答要点如果我是面试者我会这么组织答案100GB 文件放不进内存核心思路是哈希分治。第一步逐行读取文件对 driver_id 做哈希取模分散写入 N 个小文件。这样同一个车主的所有记录一定在同一个文件里。第二步逐个处理小文件。每个文件全部加载到内存用HashMapdriver_id, HashSetorder_id做去重和计数。HashSet 保证相同 driver_id order_id 的不同状态只算一次。第三步维护一个大小为 10 的小顶堆所有小文件的结果都过一遍堆最终堆里就是全局 Top 10。如果某个小文件还是太大放不进内存哈希倾斜可以对这个文件换一个哈希函数再分一次。如果数据量更大、单机处理不了就上 MapReduceMapper 输出driverId, orderIdReducer 里用 HashSet 去重后计数。面试官可能追问的点Q为什么用小顶堆不用大顶堆小顶堆的堆顶是最小的新元素比堆顶大就替换进来保持堆大小始终为 K。最终堆里就是最大的 K 个。如果用大顶堆你得把所有数据都放进去再取 K 个空间不够。Q如果哈希分片后某个文件特别大怎么办说明某些 driver_id 特别集中哈希倾斜对这个大文件换一个哈希函数按driver_id order_id再分一次。或者直接增大分片数 N。QHashSet 存 orderId 太多内存不够呢可以用两阶段方案第一阶段按driver_id order_id组合哈希分片后去重只输出 driver_id第二阶段再按 driver_id 分片计数。或者用布隆过滤器做近似去重有极小误差但省内存。Q能不能用数据库可以。把 100GB 文件用 LOAD DATA 导入 MySQL/ClickHouse然后一条 SQL 搞定SELECT driver_id, COUNT(DISTINCT order_id) AS cnt FROM logs GROUP BY driver_id ORDER BY cnt DESC LIMIT 10。但面试官考的是你对分治和数据结构的理解不是让你用数据库。小结这道题的本质是三个子问题的组合大文件不能一次加载→ 分治、去重→ HashSet / 排序相邻去重、Top K→ 小顶堆。把这三个单独拎出来都不难组合在一起就是一道综合考查基本功的好题。面试时重点讲清楚为什么按 driver_id 哈希分片和为什么用小顶堆就够了。