海量数据Top K：哈希分治+小顶堆，拆解百度面试附加题

2015年春季那一场实习生招聘我印象挺深的。百度这套题里有一道附加题不算难但特别考察基本功尤其是对海量数据处理的敏感度。当年不少人挂在上面不是不会写代码而是思路不够“工程化”。今天把这道题完整拆一遍从题目原貌到解题推演再到面试现场怎么答才能拿高分一次说清楚。1. 题目原貌与出题意图拆解先还原一下题目的大致形态。附加题本身不复杂典型表述是这样的给定一个包含约100亿个查询词Query的日志文件每个查询词平均长度约20字节需要统计出现次数最多的前100个查询词。内存限制为1GB请设计一个可行的方案。如果是第一次见这类题第一反应多半是“用哈希表统计每个词频次再排序取前100”。这个思路方向没错但完全落地不了。100亿个查询词每个按20字节算光原始数据就接近200GB1GB内存连零头都塞不下。更何况哈希表本身还有桶数组、链表节点、字符串存储的开销膨胀系数通常在3到5倍甚至更高。这题出在附加题的位置本身就说明了一些事情它不需要你背任何冷门算法考察的是基础数据结构和算法功底它不追求奇技淫巧而是看你有没有处理真实规模数据的经验它隐含考察你的工程判断力——知道在什么场景下选择什么策略而不是一味追求理论最优。当时不少候选人第一反应是“用Trie树”还有人直接说“用数据库group by”。Trie树确实可以压缩公共前缀但100亿个Query的规模下Trie节点数量依然可能过亿每个节点如果存26个指针内存根本扛不住。而数据库方案则完全没有领会面试官的意图——这种题目本质上是让你在不依赖外部存储的前提下用纯内存算法解决超大规模问题。按我当时跟面试官聊下来的理解这道题的核心考点其实有三个层次第一层能不能意识到暴力哈希不可行快速定位到“分治”这个核心思路。第二层分治之后每个分片内的数据量是否估算清楚内存是否够用。第三层最终取Top 100时是用全排序还是堆排序时间复杂度分别是多少为什么选堆。这三点能答清楚面试官基本就点头了。要是能再补充一嘴“如果数据量再大一两个数量级可以怎么扩展”那就是妥妥的加分项。2. 从暴力解法到可行性推演的完整过程很多人在面试时一上来就写代码这是大忌。正确做法是先做资源估算把问题边界摸清楚。先看“哈希表统计全量词频”为什么不行。100亿个Query假设去重后有10亿个不同的词条这个比例在实际日志中相当常见头部高频词和长尾词并存。一个Java的HashMap存储10亿个条目每个Entry包含Key引用、Value、哈希值、next指针64位JVM下开启压缩指针也要约40到50字节。仅Entry对象本身就40到50GB远超1GB限制。就算换成C的unordered_map内存开销虽然低一些但同等规模下依然需要20GB以上。再看Trie树方案。如果Query由英文小写字母组成Trie树每个节点存储26个孩子指针一个指针8字节就是208字节。哪怕通过数组压缩、子节点稀疏存储等手段优化为了维护几亿甚至几十亿的节点内存依然是以GB甚至10GB为单位计算的。内存不够的时候一切花哨优化都是空中楼阁。所以这个规模下唯一合理的路线就是“哈希分治 堆排序”。分治的核心思想很简单用一个哈希函数把海量Query映射到多个小文件里同一个Query必然落在同一个分片内这样每个分片的规模降下来后再单独统计词频就不会撑爆内存。这里有一个关键细节哈希函数一定要选得足够均匀。我当时用的是经典的BKDR哈希变体或者直接取hash(Query) % NN是分片数。如果哈希函数分布不均匀某些分片会特别大导致内存溢出整个任务就挂了。实际工程中分片数N的选择也有讲究——既要保证单分片能装入内存又不能过多导致文件句柄耗尽。具体计算过程是这样的假设去重后总词条数约10亿哈希分片后希望每个分片内的词条数控制在1000万以内。10亿除以1000万等于100所以至少分成100个分片。为了留足冗余这里有几个变量要小心不同Query的哈希值虽然分布均匀但词频分布并不会均摊到每个分片上——也就是说分片内词条数能控制住不代表分片内所有词的频次统计开销也能控制住。所以稳妥一点直接分200到300个分片这样每个分片数据量更小统计更从容。内存估算上1000万词条用哈希表统计约占用300到500MB控制在1GB限制内是安全的。流程走完后每个分片内统计出词频然后从每个分片取Top 100最后再做一次多路归并得到全局Top 100。这就是标准的大数据Top K解题套路。3. 核心方案哈希分治配合小顶堆的完整实现这一节是整道题的核心当年面试中能够清晰把方案讲明白的人大概只占三成。给你一份可以直接落地的完整方案。整体分为三步哈希分片、分片内Top K、全局归并。第一步是哈希分片。遍历日志文件对每条Query计算哈希值按分片数N取模写入对应的分片文件。这样相同Query必定进入同一个分片不会出现同一个词条被拆到两个分片从而无法合并统计的情况。哈希函数的选择不用太纠结看你的数据形态。如果Query以中英文混合居多可以用BKDR哈希或者MurmurHash效果都很稳定。我当时的做法是在面试现场手写一个简单可靠的哈希函数优先保证哈希值分布均匀。第二步是分片内统计。对每个分片文件建立一个哈希表Key是Query字符串Value是出现次数。遍历该分片的所有Query不断累加词频。遍历结束后就得到了该分片的完整词频表。然后从这个哈希表中找出频次最高的100个词。这里用小顶堆来实现堆的大小固定为100每次插入新元素时与堆顶比较如果比堆顶大就弹出堆顶、插入新元素否则跳过。最终堆里留下的就是该分片的Top 100。第三步是全局归并。将所有分片的Top 100汇总起来最多300个分片乘以100等于3万个候选词条这个规模完全可以在内存中处理。对这3万个词条再统一做一次频次排序取出前100就是全局Top 100。如果分片数更多也可以维护一个大小为100的大顶堆依次吞入所有分片结果逻辑一样。下面给一份可运行的C伪代码完整呈现这个流程#include bits/stdc.h using namespace std; // 分片数按数据量动态调整 const int SHARD_NUM 256; // 需要统计的Top K const int TOP_K 100; // 简单但分布不错的哈希函数BKDR变体 size_t str_hash(const string s) { size_t h 0; const size_t seed 131; for (char c : s) { h h * seed (unsigned char)c; } return h; } // 分片文件写入 void shard_file(const string input_file) { ifstream fin(input_file); vectorofstream fouts(SHARD_NUM); for (int i 0; i SHARD_NUM; i) { fouts[i].open(shard_ to_string(i) .txt); } string query; while (fin query) { size_t idx str_hash(query) % SHARD_NUM; fouts[idx] query \n; } } // 单分片内统计并返回Top K vectorpairint, string top_k_in_shard(int shard_id) { ifstream fin(shard_ to_string(shard_id) .txt); unordered_mapstring, int freq; string query; while (fin query) { freq[query]; } // 小顶堆按频次升序排列 priority_queuepairint, string, vectorpairint, string, greaterpairint, string min_heap; for (auto kv : freq) { min_heap.push({kv.second, kv.first}); if ((int)min_heap.size() TOP_K) { min_heap.pop(); } } vectorpairint, string res; while (!min_heap.empty()) { res.push_back(min_heap.top()); min_heap.pop(); } return res; } // 全局归并 vectorstring merge_all() { // 候选池所有分片的Top K汇总 vectorpairint, string candidates; for (int i 0; i SHARD_NUM; i) { auto part top_k_in_shard(i); for (auto kv : part) { candidates.push_back(kv); } } // 全局小顶堆求全局Top K priority_queuepairint, string, vectorpairint, string, greaterpairint, string min_heap; for (auto kv : candidates) { min_heap.push(kv); if ((int)min_heap.size() TOP_K) { min_heap.pop(); } } vectorstring ans; while (!min_heap.empty()) { ans.push_back(min_heap.top().second); min_heap.pop(); } reverse(ans.begin(), ans.end()); return ans; }有几个实现细节值得单独说明一下。第一哈希分片文件中临时文件的读写是最大的性能瓶颈。如果用C的ofstream逐条写入256个文件100亿条数据会花很长时间主要耗在磁盘IO上。更好的做法是在每个分片文件上挂一个缓冲输出流比如每次攒够4KB到8KB再落盘或者直接用fwrite配合自定义缓冲区。面试中能主动提到这个优化会显得你有真实处理海量数据的经验。第二小顶堆的实现换成手写会更稳。生产级代码里直接调库没问题但面试时手写一个容量为100的简单数组堆会更有说服力。而且手写堆能让你说清楚时间复杂度单次插入是O(log K)K100时基本是常数时间整体复杂度就是O(N log K)。第三如果分片后某个分片的词条数依然很多可以对这个分片做二次分片使用不同的哈希种子再拆一轮。这就是为什么哈希函数必须支持换种子——一旦某个分片溢出了换一个种子重新分片是最快的解决方案。4. 细节与变体面试加分的关键点在哪基础方案答完之后面试官基本会顺着往下问一层“如果数据量再扩大十倍、百倍呢”或者“如果要求实时统计呢”这些追问才是真正决定你评级的关键。先说数据量再扩大的场景。100亿条Query还能靠单机多轮分片硬扛1000亿条甚至更多时单机磁盘和CPU都会成为瓶颈。这个时候标准解法是引入分布式计算框架把分片逻辑并行化。思路依然是哈希分治只是把“分片文件”分散到多台机器上。每台机器处理一部分数据本地统计出Top 100最后汇聚到一台机器上做全局归并。这个方案对应到MapReduce模型就是Map阶段按Query哈希分发到Reduce节点Reduce阶段统计词频并按频次输出Top K最后再有一个全局归并步骤。要注意MapReduce框架中Shuffle和Sort阶段本身就会占用大量磁盘和网络IO很多团队在实际落地时其实更倾向于用Spark的repartition算子实现哈希分区或者用Flink的keyBy操作直接做有状态统计。这些工程框架的选型逻辑本质上和哈希分治如出一辙。再说流式场景。如果数据不是静态文件而是持续不断产生的实时日志那就不能“先落盘再统计”了。好在这类Top K统计问题有很多现成方案最常用的是Count-Min Sketch配合小顶堆。Count-Min Sketch是一种概率型数据结构用多个哈希函数和一个二维计数数组来近似统计词频误差可控、内存占用极小。它的核心思想是每个元素来的时候更新所有哈希函数对应位置上的计数器查询时取所有位置计数器中最小值作为该元素频次的近似估计。把Count-Min Sketch和小顶堆结合起来就能在内存占用极低的条件下实现近似实时Top K统计。不过这个方案是近似的如果面试官要求精确结果还需要在窗口结束时全量重算或者用Flink的TopN算子配合状态后端来实现。这些变体不一定要实现代码但能清晰地讲出“用什么框架、为什么、有什么取舍”就是明显的加分项。我见过不少候选人卡在这一层能答出分治和堆但一问到分布式就只说“用MapReduce”再一问MapReduce里的数据倾斜怎么解决就答不上来了。数据倾斜是分布式Top K最常见的问题——某个高频Query会聚集到同一个分片导致单点计算压力过大。解决办法有三个方向给Key加随机前缀打散到多个子分片再二次聚合或者对高频Key单独处理做两层汇总再或者使用一致性哈希加虚拟节点让负载更均衡。5. 高频踩坑点与面试表达技巧这道题看起来简单真正动手实现或者面试现场回答时还是有不少坑。列几个最常见的提醒大家注意。第一分片数选择不当。分片数太小单分片内存超限分片数太大文件句柄数不够或者产生海量小文件读写效率反而下降。一般情况下单分片去重后词条数控制在100万到1000万之间比较合适。以总共10亿去重词条为例分片数取100到300是合理区间。另外用哈希函数对分片数取模时一定要保证分片数是质数这样哈希冲突会更均匀尤其当数据本身有规律性的时候。分片数选2的幂虽然位运算高效但遇到哈希值低位相同的数据时分布会极不均匀。第二小顶堆还是大顶堆分不清。求Top K最大的元素用大小为K的小顶堆堆顶是当前最小的候选者求Top K最小的元素才用大顶堆。面试时经常有候选人把方向搞反代码写出来后自己都发现不了。一个辅助记忆方式你要的是“最大的前100个”所以堆里保留的是“当前发现的最大的100个”而堆顶是这100个里最小的那个新元素比它大才有资格进堆。第三忘了考虑字符串比较的开销。哈希分片后每个分片内依然有大量字符串比较unordered_map在遇到哈希冲突时会逐字符比较字符串。如果Query字符串较长且数量巨大这一块的时间开销不容忽视。一个优化思路是用哈希值先做快速比较把64位的哈希值直接作为Key的初始排序依据哈希相同再做完整字符串比较能明显降低比较成本。第四归并阶段的时间复杂度估算出错。如果不用堆而是把3万个候选词条统一排序排序复杂度是O(M log M)M是候选总数也就是3万几乎可以忽略。但如果分片数很多比如1000个分片理论上可以直接用多路归并维护一个大小为1000的有序队列持续取最大元素复杂度和堆方案等价。不过在数据量K100的场景下直接全排序反而更简单清晰没必要为了微小的时间优势让代码复杂度上升。面试表达上有一个重要技巧先讲思路和复杂度再写代码写代码时边写边说出每一步在做什么。不要闷头写字也不要在面试官还没理解你方案时就冲上去写。我当时习惯先画一张草图把“分片文件→分片内统计→堆取Top K→全局归并”的流程讲清楚再动手敲代码。面试官看的不只是你最终写对没有更是你在过程中体现的思维方式和工程素养。追问环节也值得提前演练。比如“如果这台机器只有512MB内存怎么办”答案不是重新发明算法而是调大分片数并且把分片内的统计结构从哈希表换成更节省内存的Trie或紧凑哈希甚至在磁盘上维护一个小型索引。又比如“如果不需要精确Top 100允许一定误差呢”答案是用Count-Min Sketch加小顶堆几MB内存就能搞定。提前把这些变体的思路理清楚面试时就能做到兵来将挡。6. 一套完整的思路模板可直接用在同类题目上这类“海量数据Top K”题目在各大厂面试中反复出现比如“10亿个整数取前100大”“搜索日志中找出最热门的100个词”“100亿个URL中找出访问量最高的100个”等。它们的解题模板高度统一可以总结成一个五步思考框架。第一步算清楚数据量级。原始数据多大、去重后大约多大、内存限制多少。这个估算决定了后续所有方案的选择算错了方向就错了。比如10亿个整数每个4字节总数据就是4GB单机装不下但哈希分片后每个分片装几千万个就完全没问题。而如果只是1000万个整数总共40MB直接内存排序都行根本不需要分布式方案。第二步根据内存限制确定分片策略。分片数至少是“去重后数据量”除以“单分片可承载量”的向上取整再乘上1.5到2的冗余系数。分片的过程就是一次全量扫描时间复杂度是O(N)。第三步在每个分片内用哈希表统计词频。这一步的时间复杂度也是O(N)整体分摊到每个分片上就是线性的。这里可以提一句哈希表的扩容机制——如果预估分片内词条数超过当前桶数组容量最好在初始化时一次性reserve足够容量避免频繁rehash带来的性能抖动。第四步用大小为K的堆取出每个分片的局部Top K。这步单独看是O(N log K)但因为K通常远小于Nlog K接近常数所以实际是近似O(N)。第五步汇总所有局部Top K再用堆或全排序求全局Top K。候选总数是分片数乘以K规模很小复杂度基本忽略。这个模板几乎能套用所有同类型问题。不同变体的差异主要在于数据是否可以去重、Key是什么类型、是否需要保序、是精确统计还是近似统计。把模板吃透再针对变体灵活调整细节这类题目就能成为面试中的送分题。另外补充一个很多人不知道的技巧。如果分片前的原始数据本身带有时间戳或者类别信息可以在分片时直接按时间或类别作为分区键后续还能顺便做维度分析。比如按小时分片统计完Top 100之后还能看出高频Query在一天内的分布变化。这种“顺手多答一句”的细节往往比把算法本身讲得更出彩因为它展示了你的业务敏感度而不只是技术执行能力。