前几天有准备面试的朋友来问我内存有限的情况下怎么对4亿个英语短语去重这道题在网上流传很广我也在面试中面试过、也被面试官问过。第一次听到“4亿”这个量级很多人第一反应是“丢进 Set 里不就行了”但现实是你连数据本身的体积可能都还没估算清楚。这道题的价值不在于背一个标准答案而在于它同时考察了几件重要的事你有没有数据规模意识会不会在大数据量面前先算一笔账你知不知道内存资源和磁盘 IO 之间的取舍你能不能把一个看似庞大的问题拆成可以逐个吃掉的小问题。今天我直接用工程视角把这道题拆开从估算数据体积到几种核心方案再到面试时怎么组织语言一次讲透。1. 先算账4亿个英语短语到底有多占内存1.1 从“裸数据体积”开始估算很多人一上来就聊算法我反倒建议先算算数据量级。这个习惯无论是面试还是实际做系统都能帮你避免很多低级失误。假设每个英语短语平均 30 个字节左右。这个数字怎么来的常见短短语像cat、dog不到 10 字节长一点的如machine learning algorithm到 40 字节取个平均值 30 已经比较保守。那么4亿 × 30 字节 120亿字节 约 12 GB如果平均是 50 字节那就是 20 GB这还只是“原文本身”的体积。也就是说哪怕你有一台 16 GB 内存的机器光把所有短语读进内存就已经很紧张了更别提去重时还要维护额外的数据结构。而题目限定了“内存有限”那这个场景基本默认内存是在几个 GB 量级甚至可能只有 1-2 GB。所以第一步结论很明确内存里直接全量放 Set 这个思路从一开始就不成立。1.2 语言运行时带来的“隐藏开销”更大你以为 12 GB 是全部不是。真正用语言自带的哈希表去存开销要大得多。我分别按 Java 和 C 给你估一下Java 里一个 String 本身有对象头内部还有一个 char[] 数组这两个对象都有头部信息char 数组在 UTF-16 编码下每个字符占 2 字节。再加上 HashSet 底层 HashMap 的桶数组、节点对象、链表指针一个 30 字符的短语在 Set 里实际占的内存通常是 100-200 字节。按 150 字节算4亿 × 150 字节 ≈ 60 GBC 情况好一些。std::string 在小字符串优化SSO机制下短字符串直接存在对象内部但 unordered_set 的节点还要存哈希值、指针、键对象。总体算下来每个条目大约 40-90 字节。按 80 字节估算4亿 × 80 字节 ≈ 32 GB这就是为什么有经验的工程师从来不会在“几十 GB 级数据”前直接 new 一个 HashSet。不是不会写代码而是心里要先有一张“成本和容量表”。1.3 真正动手前先把三个假设问清楚面试场景题往往故意把条件说得模糊这时候先提问比先答题重要得多。我通常会确认三件事“去重”的定义是什么短语完全一致才算重复吗大小写是否敏感空格和标点要不要统一如果允许把 “Hello World” 和 “hello world” 视为重复那方案完全不一样。“内存有限”到底是多少512 MB、1 GB、还是 4 GB不同量级能容纳的桶内数据规模不同方案参数也要跟着变。输入输出的形式是什么输入是文件里一行一个短语吗输出只需要一个去重后的结果文件还是需要保留原始顺序问清楚这三件事本身就是回答的一部分。面试官想看到的往往不是你直接背方案而是你有没有“先界定问题边界”的意识。2. 哈希分片面试里最值得优先讲的方案2.1 为什么哈希分片能“一招破局”哈希分片的核心逻辑特别简单对每个短语计算哈希值然后取模分到 K 个桶里。相同短语的哈希值一定相同所以它们必然进同一个桶。于是“全局去重”就变成了“每个桶内部去重”每个桶的数据量大约是总量的 1/K内存压力瞬间降下来。这个思路的本质是用一次全量的磁盘读写换取“内存只装得下一个小分片”的可行性。工程上这叫分而治之思维上叫“把一个不可能在内存里完成的问题拆成多个能在内存里完成的小问题”。这也是为什么我推荐在面试中优先讲这个方案它思路清晰、实现简单、可扩展性强而且直接命中“内存受限”这个核心约束。对比外部排序它的复杂度还更低。2.2 实现步骤可以用 Python 伪代码快速演示如果让你用代码表达我会写一套和下面结构类似的版本import hashlib K 64 # 分片数后面会讲怎么定 # 第一遍按哈希把短语分发到 K 个桶文件 with open(input.txt, r, encodingutf-8) as fin: bucket_fds [open(fbucket_{i}.txt, w, encodingutf-8) for i in range(K)] for line in fin: phrase line.strip() h int(hashlib.md5(phrase.encode(utf-8)).hexdigest(), 16) bucket h % K bucket_fds[bucket].write(phrase \n) for fd in bucket_fds: fd.close() # 第二遍逐个桶读入内存去重 with open(deduped.txt, w, encodingutf-8) as fout: for i in range(K): seen set() with open(fbucket_{i}.txt, r, encodingutf-8) as fin: for line in fin: phrase line.strip() if phrase not in seen: seen.add(phrase) fout.write(phrase \n) # 这个桶处理完就释放内存继续下一个这里有几个工程细节值得单独说不要一次把整个输入文件读入内存。用流式读取一次处理一行否则你第一遍分桶就把内存吃满了方案直接失败。写桶时用缓冲写入。Python 里可以用io.BufferedWriter或者干脆在写文件的循环里攒一批再 flush减少小文件频繁写盘的系统开销。第二遍逐个桶处理保证峰值内存只和一个桶的大小相关。这是整个方案的精髓。2.3 分片数 K 怎么定K 的选择直接决定内存峰值。原则很简单单个桶的数据量必须能稳稳塞进内存预算。假设单条短语在 Set 里的开销是 80 字节内存预算只有 1 GB那一个桶最多大约放1 GB / 80 字节 ≈ 1250 万条总量 4亿想要单桶不超过 1250 万条K 至少要4亿 / 1250万 ≈ 32考虑到哈希分布不可能绝对均匀最好留出 2-3 倍余量所以我一般会定 K 64 甚至 K 128。K 越大每个桶越小内存越安全但临时文件和后续 IO 也会增多这是一个典型的“空间换 IO”权衡。还有一个细节取模的 K 尽量不要用 2 的幂次。某些哈希函数低比特位分布并不均匀如果 K 是 2 的幂等于只用了哈希值的低几位容易扎堆。用质数或者接近质数的 K会稳很多。2.4 处理“热桶”如果某个桶还是太大怎么办理论归理论现实里可能会碰到极端情况某个桶的短语格外多或者某个桶里的短语特别长导致它超出了内存预算。这时候有两个处理方向二级哈希分片。对超出阈值的大桶换个哈希函数再分一次子桶把子桶控制到可接受大小每个子桶内部去重。逻辑和第一级完全一样相当于递归调用。桶内外部排序。如果不想再维护一批文件也可以直接在单桶内走“分块排序 归并”的思路用磁盘换内存。我实际见过的情况是只要第一轮哈希函数选得好、K 留了余量绝大多数桶都不会太大。但面试时你能主动说出“热桶怎么办”会显得你见过真实数据里的倾斜问题这比只会背方案的人高出一个段位。2.5 时间复杂度和 IO 成本整个流程是读一遍全量输入写 K 个桶再读 K 个桶逐个去重后写结果。总共大约两遍读、两遍写时间接近 O(N)空间是 O(N/K)。如果按 4亿条、每条约 30 字节来算单机一次全量读写的 IO 总量大约是十几个 GB 乘以两遍SSD 上只要十几分钟到半小时就能跑完。这个成本在大数据场景下完全可以接受。3. 外部排序把去重变成“有序序列上的相邻比较”3.1 为什么“有序”之后去重就变得很简单如果你手里是一个已经全局有序的短语序列去重就变成了一次线性扫描每读到一个新短语只要和上一个对比相同就跳过不同就保留。重复项在排序后一定相邻所以不需要任何额外的哈希表内存里只要存一个“上一个短语”就够。这就是外部排序思路的核心逻辑我不去维护一个“记录所有出现过的元素”的结构而是通过排序让重复项物理上靠到一起。3.2 外部排序的标准三步分块、排序、归并外部排序的思路是先用内存能容纳的块大小把大文件切碎把每个碎片分别排好序再通过多路归并拼成一个全局有序的序列。第一步分块。比如设定一个块大小是 256 MB每次读入 256 MB 的短语在内存里排序后写成一个临时文件run_0.txt、run_1.txt……原始数据是 12 GB那大约会生成 48 个临时文件。第二步多路归并。同时打开所有这些临时文件每个文件维护一个读指针用最小堆选出当前最小的一条输出然后继续读对应文件的下一条恢复到堆里。这样一路输出得到的就是全局有序的完整序列。import heapq def k_way_merge(runs, fout): heap [] for run_id, run in enumerate(runs): phrase next(run, None) if phrase is not None: heapq.heappush(heap, (phrase, run_id)) last None while heap: phrase, run_id heapq.heappop(heap) if phrase ! last: # 去重逻辑 fout.write(phrase \n) last phrase nxt next(runs[run_id], None) if nxt is not None: heapq.heappush(heap, (nxt, run_id))第三步在归并输出时顺便去重。因为全局有序重复项必然连续出现只需要记住上一次输出的是什么碰到相同的就直接跳过。这一行代码在场外处理里极其关键。3.3 内存和磁盘 IO 成本算一算外部排序的内存占用和分块大小直接相关。每个临时文件只需要一个读缓冲区堆里最多同时存在“路数”个元素。假设 48 路归并堆里几百条短语内存开销可以控制在 MB 级比哈希分片还要省。但 IO 就没那么便宜了。每一轮分块排序要写一遍临时文件归并要读一遍临时文件最后写结果。如果临时文件数量超过系统文件描述符上限或者单轮归并结果太大你还要做多轮归并每多一轮就多一轮全量的读写。按 12 GB 原始数据算第一轮写约 12 GB 临时文件归并读 12 GB写结果约几个 GB总 IO 量大概 30-40 GB。这还是一次归并能完成的情况。所以外部排序的优势是内存极小、输出天然有序代价是时间比哈希分片慢IO 也更多。3.4 和哈希分片怎么选取决于要不要“有序输出”我在面试和实际项目里的判断标准很简单如果只需要“去重后的结果”不关心顺序——首选哈希分片它更快、实现更直观。如果下游还想做“排序输出”“范围查询”“TopK”或者内存紧张到只有几百 MB——外部排序更合适因为排序结果可以一次产出多个用途。如果两者都想要也可以先哈希分片每个桶内排序后再按桶号归并输出。不过这是叠加方案复杂度上去了一般不推荐在面试里主动展开除非面试官追问。面试时你能把“何时选哪个”说清楚比单纯写代码更体现工程判断力。4. 布隆过滤器它不能单独完成但能让方案更经济4.1 布隆过滤器的原理和关键特性布隆过滤器是个很常见的概率性数据结构一个 m 位的位数组搭配 k 个哈希函数。插入一个元素时把 k 个哈希位置分别置为 1查询一个元素时检查这 k 个位置是否全为 1只要有一个是 0就说明这个元素一定没出现过。这个结构有两个让人又爱又恨的特点没有漏判false negative。布隆说“没见过”那一定没见过。有误报false positive。布隆说“见过”可能只是其他元素把那些位也置成了 1。用大白话说它像是一个“只记印象不记细节”的保安你说一个名字他说好像见过可能是真见过可能是记串了但他说肯定没见过那就是真没见过。4.2 算一笔账4亿规模的布隆过滤器要多少内存布隆过滤器的内存和误报率强相关。用经典的公式m - (n × ln p) / (ln 2)^2k (m / n) × ln 2其中 n 是元素数量p 是期望误报率m 是需要的位数。代入 n 4亿p 1%m ≈ 3.84 × 10^9 bit ≈ 480 MBk ≈ 7也就是说一个误报率 1%、能容纳 4亿短语的布隆过滤器只需要大约 480 MB 内存。如果放宽到 0.1% 误报率也只需要大约 720 MB。这个内存占用在“有限内存”条件下完全可行而且每查一个短语只需要算 7 次哈希速度极快。这个数字很惊艳所以我见过不少候选人会直接提出“用布隆过滤器去重”。但这里有个概念陷阱。4.3 为什么不能用布隆过滤器直接做去重去重这个动作的定义是最终输出的集合里每个短语只出现一次并且不能漏掉任何一个真实存在的短语。布隆过滤器的问题在于误报。如果一个从未出现过的短语因为哈希位置冲突被误判为“已存在”你在去重逻辑里就会直接跳过它结果就是把这个短语整个漏掉了。对某些场景这可能无所谓比如爬虫遇到少量 URL 重复无伤大雅但对“精确去重”的要求来说这是不可接受的错误。所以面试时如果题目没有明确说“允许误报”你不能把布隆过滤器当作最终去重结构。你可以在回答里主动点出这一点顺便展示你理解了概率型结构的能力边界。4.4 正确的组合姿势布隆过滤器当“预检”磁盘当“精查”布隆过滤器虽然不能单干但它能在精确方案里当加速器。经典的组合思路是内存里维护一个布隆过滤器外部存储维护一个精确的已见集合比如哈希分片后的桶文件。来一个短语先查布隆过滤器。如果布隆说“肯定没见过”直接写入结果同时更新布隆过滤器不需要去磁盘翻文件。如果布隆说“可能见过”再去外部存储里精确查找确认确认存在就丢弃确认不存在就写入并更新布隆。因为大多数重复短语会被布隆过滤器直接拦住真正需要走磁盘确认的只是一小部分整体 IO 大幅下降。这个模式的本质是“用内存换磁盘随机访问次数”。我在做爬虫 URL 去重时就经常这么干内存里放一个几百 MB 的布隆过滤器外面配一层 KV 存储做精确确认效果比单纯用哈希表快很多。面试时你能把它作为“进一步优化”提出来会是一个很自然的加分项。5. 数据本身的可压缩性几个“加分项”技巧5.1 排序后做前缀压缩英语短语不是随机字节序列它天然有大量的公共前缀。比如the quick brown fox、the quick blue dog这种结构排序之后相邻的两条短语可能共享很长一段前缀。利用这一点存储时可以只记录“与上一条共享的前缀长度 差异后缀”。比如上一条是the quick brown fox下一条是the quick blue dog那就只需要存共享前缀11字节 blue dog。这种方法在自然语言数据上通常能省 30%-70% 的空间。注意前缀压缩主要优化的是“驻留内存/磁盘文件”的体积不会改变你选用的去重算法但在内存极紧的场景里它能让你把 K 值放大、单桶装更多数据实际效果很可观。5.2 词表编码把短语拆成词 ID另一个思路是拆词。4亿个短语听起来巨大但构成它们的英语单词数量其实有限可能就几十万到几百万的规模。那我可以建一个全局词典把每个单词映射成一个短整数 ID短语就从“一串字符”变成“一串 ID”。比如the cat→[17, 42]the dog→[17, 98]这样两个短语可能只需要 2 个 int也就是 8 字节远小于原来的 10-15 字节字符存储。如果短语有固定长度限制甚至可以连长度都不用存进一步压缩。但这个方案有个前提你要能可靠地分词而且处理的是规范的英语短语不能是一堆没有空格、没有规律的字符串。面试中提到“如果短语结构规整可以用词表编码进一步压内存”足以说明你对数据特征有敏感性。5.3 极低内存下的数据库和分布式扩展如果内存真的低到连一个分桶都装不下比如只有 64 MB那可以退一步用数据库方案把短语作为主键写入 SQLite 或类 LevelDB 的嵌入式存储靠数据库的 B 树索引去重。原理上仍然是“用磁盘索引换内存”只是把分桶逻辑外包给了成熟的存储引擎。如果允许多台机器那思路就更灵活了。最简单的方式就是把哈希分片的桶分发到不同机器上每台机器只负责自己的几个桶。本质上还是同一个分治思想只是把“内存”的范围从单机扩大到了集群。分布式只是把同一个方案放大而不是引入新概念这一点你要能在面试里表达清楚。6. 面试怎么答10分钟组织一个完整回答6.1 我的答题节奏约束先行方案殿后回答这类题最忌讳不问条件就猛讲。我会把时间这样分配前 1-2 分钟确认“去重标准”“内存上限”“输入输出格式”三个前提。接下来 3-5 分钟主推哈希分片方案讲清楚原理、K 怎么定、时间复杂度、内存怎么控制。再用 1-2 分钟补充一句如果需要全局有序可以改成外部排序如果允许一点误差可以用布隆过滤器做预过滤。最后留一点时间说工程细节比如热桶怎么处理、IO 量级估算。这套节奏的优点是既有方案又有取舍还能体现你考虑过真实实现里的坑。6.2 高频追问和参考答案我在模拟面试时经常会追问下面几个问题你可以提前准备追问一你会把 K 定为多少直接按公式来K ≈ 总数据量 × 单条内存开销 / 内存预算再留出至少一倍余量。比如总数据 4亿条、单条 80 字节、预算 1 GB算出来最小 K 是 32实际我会选 64 或 128。追问二如果某个桶还是太大怎么办两个方向一是对那个桶做一个二级哈希二次分片递归处理二是桶内改用外部排序。本质上都是继续“分割到能装进内存为止”。追问三要是允许少量误判呢那就直接用布隆过滤器当作近似去重结构按误报率 1% 来算4亿条大约需要 480 MB 内存配 7 个哈希函数。然后强调一句布隆过滤器只能误报不能漏报所以它适合“宁可多留少量重复也不能漏数据”的场景。追问四如果换到多台机器方案怎么改把哈希分片的桶分发到各机器每台只处理自己负责的桶集合。分桶逻辑完全复用只是从“单机多个文件”变成“集群多个节点”。6.3 最后分享一点我的实际体会这类题看似是“面试场景题”其实就是海量数据处理里最常见的一类问题。我自己做爬虫 URL 去重的时候用的就是 64 个文件分桶然后把每个桶按顺序读进内存做精确去重整套流程跑下来处理上亿条数据只需要一台普通服务器加一块 SSD。这道题给我的最大启发不是哪个数据结构更高级而是先算账再分治最后再谈优化。你先对数据规模心里有数再思考怎么把问题切成内存能承受的小块布隆过滤器、前缀压缩这些技巧都是建立在这两步之上的锦上添花。能把这条思路讲出来比背十个方案都管用。