我面过不少候选人这道题出现频率极高几乎可以排进我题库里的前三。一上来就背“用布隆过滤器”的很多但能当场把内存算明白、把约束问清楚、把方案权衡讲透的人很少。这题表面是“去重”实际考的是三件事你能不能做量级估算能不能在约束下做技术选型能不能把你的选择用工程语言讲清楚。今天我把整个思考链路完整拆开从算账开始到布隆过滤器、Trie、外部排序和哈希分片最后给一套能直接拿去面试用的答题框架。1. 先算账4亿条短语到底能把内存吃成什么样1.1 能先做一次“口头估算”的候选人我就知道稳了很多候选人拿到这题第一反应是“用 HashSet 呗”。这句话本身没错但它回避了最关键的问题内存够吗面试官说“内存有限”到底是怎么个有限法8GB 的 JVM 堆和 512MB 的容器是两种完全不同的约束。先做量级估算。4 亿条英语短语平均一条有多长一个英语短语通常由 2 到 6 个单词组成算上空格和标点平均按 20 到 30 个字符估比较合理。按最保守的 20 字节算原始数据就是 4 亿 × 20 字节 80 亿字节约 8GB。这意味着即使什么额外结构都不建光把原始字符串放进内存就已经超过了绝大多数单机可用的堆内存。如果按 30 字节估那就是 12GB。所以第一句话就应该告诉面试官题目里的“内存有限”是一个比想象中更苛刻的约束原始数据本身就已经很重了。候选人在这一阶段展现出的“估算感”往往比答案本身更重要。因为真实业务里没人会给你精确到字节的数据量你必须有根据数量级判断可行性的直觉。能主动把估算过程说出来说明你处理过真实的数据问题。1.2 为什么 HashSet 看着简单实际一跑就挂既然原始数据就要 8GB 以上那 HashSet 的开销就更夸张了。很多人只算字符串本身的长度忽略了 JVM 对象模型里的“隐藏成本”。以 Java 为例一条 20 字符的 String 对象它的内存构成大致如下对象头 12 字节开启指针压缩后HotSpot 默认 -XX:UseCompressedOops实例数据里有一个 byte[] 引用4 字节、一个 hash 字段4 字节、一个 coder 字段1 字节、再加上对齐填充String 对象本身大约 24 字节。底层的 byte[] 数组还要再占 16 字节数组头 20 字节数据 对齐约 40 字节。光一条字符串就是 60 字节以上。放进 HashMap 还要包一层 NodeNode 里有 hash、key、next 等字段至少 32 字节。哈希桶数组本身也有开销。把这些全部加起来一条短语在 HashSet 里的占用轻松超过 100 字节4 亿条就是 40GB 以上这还没算扩容时临时多出来的内存。这个计算过程本身就有价值。面试的时候你可以现场算给面试官看字符串内容 20 字节但对象模型把它放大了 5 倍。这也是为什么任何“直接用内存集合硬扛”的思路在大规模数据面前都会立刻失效。1.3 “内存有限”是个弹性约束先跟面试官对齐面试官说“内存有限”到底是多少这里我强烈建议你主动追问因为它直接决定方案走向。如果可用内存是 8GB 甚至更大配合布隆过滤器或分片方案空间完全不同。如果只有 1GB那连原始数据都放不下必须走磁盘或分布式。这个追问不是示弱而是专业表现。真实工程里需求方说的“数据量不大”和“内存够用”往往跟实际差着好几个数量级。你首先要澄清的是几个核心约束第一可用的内存上限大概是多少第二这个去重必须精确还是可以容忍一个很小的误判率第三最后需要输出的是“哪些是重复的”还是只要一个“去重后的集合”或者甚至只要求“剩余多少条”第四允许使用磁盘和分布式吗。这四个问题问完面试气氛基本就控制在你手里了因为你在主导需求分析而不是被动答题。2. 别急着写代码先把需求问清楚2.1 三个关键问题精度、输出、资源去重方案里最容易被忽略的是“精度要求”。如果业务上允许极小概率的误判比如一个短语本来不重复但被判断为重复那就可以用布隆过滤器这类概率型结构省下一个数量级的内存。如果要求绝对精确那就只能走 Trie、外部排序、哈希分片这类确定性方案。输出也很关键。是要得到“每个重复短语出现了几次”还是“把所有重复项删掉保留唯一列表”还是“只告诉我剩下的数量”不同输出对应的方案差异巨大。想要计数可以用 HyperLogLog 做近似基数统计每个 key 只花 12KB 左右但想知道具体哪些短语重复就完全做不到。如果只是去重保留集合布隆过滤器也不行因为它只能告诉你“可能存在”不能把集合元素取出来。资源边界同样要确认给一台机器还是多台机器允许多少磁盘空间这几个问题直接决定你是往“内存压缩”方向想还是往“分治 磁盘”方向想。2.2 一张图看懂技术选型把候选方案摆出来你就能看到它们各自适用的约束条件方案精确度内存量级能否输出集合适用场景HashSet精确每条 100B 以上4 亿条 40GB能数据量小内存充裕布隆过滤器有误判每条约 1 到 2 字节按误判率不能只需判断“是否存在”Trie / 双数组 Trie精确取决于前缀共享度能前缀共享高如 URL、域名、词根外部排序精确内存只占排序缓冲能单机 磁盘数据海量哈希分片精确分片后每片很小能单机多进程或分布式数据库 DISTINCT精确交给引擎能有现成数据库数据已入库面试时把这张表在脑子里过一遍然后根据刚问到的约束挑一个主线方案再准备一个备选方案就能让面试官觉得你思路完整而不是只会背某一个结构。2.3 面试官出这题其实在考什么出这道题的面试官通常不是真想让你把布隆过滤器的论文细节默写出来。他更想看到的是面对一个“数据规模超过直觉”的问题你能不能冷静地先做需求拆解和量级估算再在多个方案里做合理的工程取舍。这种能力在真实系统中非常关键因为数据量永远不会停在面试题的数字上线上流量翻几倍是常有的事。你今天设计的方案能不能在数据翻倍后还扛得住才是面试官真正关心的。换句话说这道题的隐藏考点是“决策能力”。你不需要给出一个唯一正确答案但你需要展示我理解约束我量化过代价我知道每个方案的边界我能为我的选择给出理由。3. 方案一布隆过滤器用低于 10% 的误判率换掉 95% 的内存3.1 原理其实一句话位数组 多个哈希函数布隆过滤器理解起来很直观。你准备一个长度为 m 的位数组初始全是 0。插入一个短语时用 k 个相互独立的哈希函数算出 k 个位置把这 k 个位置全部置 1。查询一个短语时同样算出 k 个位置只要发现任何一个位置是 0就说明这个短语绝对没有被插入过如果 k 个位置全是 1那只能说“它大概率被插入过”。这里的“大概率”就是误判的来源。因为随着插入的元素越来越多位数组里的 1 越来越多不同元素把同一个位置置 1 的概率也随之增加。到后期一个新元素的所有哈希位置可能都已经被别的元素占用了于是它就被误判成“已存在”。布隆过滤器最大的优点是它完全不保存数据本身只保存“指纹”。一个字符串不管是 10 字节还是 100 字节进来以后都只占几个 bit 的位置。这正是它在海量数据场景下省内存的根源。3.2 关键参数m、k、p 怎么定来动手算一遍这里的三个参数是位数组长度 m、哈希函数个数 k、期望误判率 p。第一个核心公式是 m - (n × ln p) / (ln 2)^2其中 n 是预期插入的元素数量。第二个公式是 k (m / n) × ln 2取整数。我们来算真实数据。n 4 亿如果期望误判率 p 1%ln(0.01) ≈ -4.605(ln 2)^2 ≈ 0.4805代入公式 m ≈ (4 亿 × 4.605) / 0.4805 ≈ 38.34 亿 bit换算成字节约 4.8 亿字节也就是 480MB。k (38.34 亿 / 4 亿) × 0.693 ≈ 6.64取整数 7也就是需要 7 个独立的哈希函数。如果把期望误判率降到 0.1%代入算出来 m ≈ 57.5 亿 bit约 720MBk 约等于 10。很多人会随手记下“布隆过滤器占用小”这句话但你要在面试里能算出具体数字4 亿条数据1% 误判率下大约 480MB0.1% 误判率下大约 720MB。对比 HashSet 动辄 40GB 的占用这是个数量级的下降但也没小到可以无视的地步。如果面试官把内存约束卡到 256MB那布隆过滤器单机也扛不住必须配合分片或外部存储。3.3 工程实现与注意点实现布隆过滤器时有几个细节容易踩坑。第一哈希函数要尽量独立。实际里不需要真的找 7 个不同的算法可以用一个 64 位哈希比如 MurmurHash3再通过不同的种子派生多个哈希值工程上效果就足够了。第二位数组最好用 byte[] 或 long[]配合位运算操作。Java 里 BitSet 也能用但性能敏感的场景下自己控数组更灵活。第三插入和查询之前必须对短语做归一化处理去掉首尾空格、统一大小写、把连续空白符压缩成一个空格。不然同一个短语会因为大小写不同被当成两条数据去重效果直接打折。还有一点必须警惕布隆过滤器无法删除元素。如果你在去重过程中发现“误判”的短语之后想从集合里移除做不到。解决办法是用计数布隆过滤器Counting Bloom Filter每个计数器占用 4 bit 左右内存会明显上浮但支持删除。实际业务里如果主要场景是判存在而不需要删除那普通布隆过滤器就够用了。3.4 局限性它给你的不是“集合”布隆过滤器最大的问题是它不能把去重后的短语集合原样输出。你只能判断某个短语之前有没有见过但没办法遍历所有“已经存在”的短语。所以如果需求是“我需要一个去重后的列表要存文件或者做后续处理”布隆过滤器只适合作为前置过滤最后还得回到其他数据结构上。它更典型的应用场景是判断一个从外部来的短语是否已经在库里出现过比如爬虫抓取时去重 URL、缓存系统判 key 是否存在、垃圾邮件过滤。这些场景只需要回答“是否见过”不需要把元素捞出来。把布隆过滤器的局限讲清楚面试官反而会更认可你的理解深度因为你主动说了它能做什么、不能做什么。4. 方案二Trie 前缀树与它的省内存变体4.1 Trie 去重的天然优势Trie前缀树/字典树是很多人容易忽略的答案但它其实很契合“英语短语”这个题目。它的核心思想是把每个短语拆成字符序列按字符逐层建立树结构公共前缀只保存一份。举个例子“apple pie”和“apple juice”这两个短语共享前缀 “apple ”如果用 Trie 存储这段前缀只需要一条路径而不是在两个 String 对象里各存一遍。在处理 URL、域名、化学式、英语单词这类前缀共享度高的数据时Trie 的省内存效果很明显。而在“英语短语”这个场景下单词的复用率天然就高很多短语都以 “the”、“of”、“in”、“a” 这类高频词开头。Trie 的另一个优势是完全精确不存在误判并且天然支持前缀查询。比如你想统计所有以 “apple” 开头的短语Trie 会非常高效因为它只需要沿着一条路径走到底。4.2 节点开销是最大陷阱但是如果直接实现一个字符级 Trie问题也很大——每个节点在 Java 或 Go 里都是一个对象对象头加字段引用往往要占 32 字节以上再加上子节点数组或 Map 的开销一个节点可能吃掉 40 到 50 字节。我们估算一下节点数量。4 亿条短语平均 20 字符总字符数高达 80 亿。即便有一定前缀共享节点数也可能达到总字符数的很大比例因为不同的单词组合会导致深层分支非常多。如果每个节点 40 字节总内存就是几千亿字节直接比 HashSet 还离谱。所以我在面试现场经常能看到两种极端一种是想都不想直接说 Trie 省内存另一种是想都不想直接否定 Trie。两种都不可取关键是看前缀共享度并且要提出压缩变体。4.3 双数组 Trie 与 Radix Tree 的“瘦身”思路真正工程里采用的往往不是朴素的节点对象实现而是压缩结构。最经典的是双数组 TrieDouble-Array Trie它用两个 base[] 和 check[] 整型数组来存储整棵树的状态转移关系节点本身不再有对象头没有指针只有紧凑的数组下标对应关系。日语分词器、汉字拼音转换、词典匹配里大量使用这种结构的工业实现。双数组 Trie 的内存占用比对象式 Trie 小一个数量级但构建过程比较复杂扩展性也不如普通 Trie。还有一个更常见的选择是 Radix Tree也叫压缩 Trie。它把只有一个子节点的连续链合并成一个节点比如某个分支下只有 “apple” 这一条路那就不需要为 “a”“p”“p”“l”“e” 各建一个节点而是直接存压缩后的片段。从“内存有限 英语短语”的角度看按单词切分建 Trie 也是一种有效的瘦身方式先按空格把短语拆成单词序列Trie 的节点就变成单词而不是字母节点数会大幅下降前缀共享也更明显。4.4 什么时候该选 Trie如果面试官追加“这些短语以 URL 形式出现”或者“我需要支持前缀匹配”那 Trie 的优先级会显著上升。如果数据是随机字符串前缀共享非常低Trie 确实不合适这时候布隆过滤器或分片更靠谱。能讲清楚这个边界说明你不是背了一个树结构就套上去而是真的按数据特征做的选型。另外Trie 还有一个额外的好处它可以边插入边判断是否重复不需要二次扫描。插入过程中如果发现某个短语的最后一个字符对应的节点已经存在那就是重复。这意味着去重的时间复杂度是 O(总字符数)不需要排序不需要哈希碰撞对 CPU 也非常友好。5. 方案三内存不够就让数据流动起来5.1 外部排序把内存问题变成磁盘 IO 问题当内存小到连分片都用不了或者你需要绝对精确的结果外部排序是一个可靠思路。做法是把 4 亿条短语分批读入内存每批比如 100 万条在内存里排序写成一个有序的临时文件。全部处理完之后生成若干个小有序文件再做多路归并。归并过程中相邻的相同记录直接跳过最后剩下的就是去重后的集合。代价也很明确写临时文件会带来大量磁盘 IO。4 亿条记录每条按 30 字节算就是 12GB 数据即使按 10 倍 IO 放大估算也是 120GB 量级的读写。这在 SSD 上还能接受但速度肯定比不上内存方案。外部排序最大的优势是不依赖内存大小只要能跑得动 JVM 或进程给多少内存都能处理无非是批次数变多IO 次数变多。5.2 哈希分片最通用的“降维打击”哈希分片才是大厂面试里最想听到的通用思路之一。核心逻辑很简单对每条短语计算一个哈希值比如用 murmur3然后对某个分片数 N 取模把结果相同的短语归到同一个分片文件。这样一个 4 亿条的大问题就被拆成了 N 个小问题每个小问题里的数据量是原来的 1/N内存压力跟着变成 1/N。这个思路在单机和分布式里都能用。单机版可以做成多进程并行每个进程处理一个分片各自维护一个 HashSet然后取并集。分布式版就是 MapReduce 里的经典流程Map 阶段计算 hash 并分桶Shuffle 阶段把相同桶的数据送到同一个 reduceReduce 阶段在内存里做去重。这也是 Spark 里distinct()操作的底层逻辑跑在 HDFS 或对象存储上对单机内存的压力几乎为零。5.3 单机版分片实操与参数选择分片数选多少取决于可用内存。假设可用内存是 1GB每条短语在 HashSet 里按 100B 算那一个分片里最多放 1000 万条但最好留出余量按 500 万条一个分片算4 亿条需要 80 个分片。如果内存只有 512MB那就把分片数提高到 160 个以上。这一步可以用公式估算分片数 ≥ 总数据量 × 单条内存开销 / 可用内存 × 安全系数。安全系数建议取 2 到 3因为内存里不只有 HashSet还有缓冲区、临时对象、GC 开销。分片处理后还需要注意负载均衡。如果数据分布不均匀比如某些短语被哈希到同一个分片而另一些分片几乎是空的那内存开销依然会围到少数几个分片上。不过哈希函数选得好比如 murmur3分布基本均匀。真遇到数据倾斜可以再加一层“二级分片”把过大的分片继续按另一个哈希值拆细。5.4 顺手提一嘴的 SQL 和分布式方案在面试收尾阶段可以提一句如果数据已经入库一条SELECT DISTINCT phrase FROM table或GROUP BY phrase就够了底层引擎会自己决定走哈希还是排序。用 Spark、Flink、Hive 这类引擎处理大规模去重时也只需要调用框架自带的 distinct 算子不需要自己从零写分片逻辑。这并不意味着上面的手工方案没用而是说明在真实工程里我们优先复用成熟组件手工方案的价值在于让你在框架失效或需要调优时知道底层的分片和排序是怎么运作的。能把这句话讲出来面试官会觉得你既有底层思维又有工程视野。6. 面试现场一个能直接套用的回答框架6.1 五步回答法这种场景题最怕的就是面试官话音刚落你就张口答“用布隆”。我建议你用下面这个五步结构每次面试前在心里过一遍。第一步先复述问题并澄清约束。可以说“我确认一下4 亿条英语短语需要完全精确去重还是可以容忍一个很小的误判可用内存大概多少需要输出去重后的集合本身还是只需要判断重复与否”这一步会让你立刻和其他直接做题的候选人在观感上拉开差距。第二步给量级估算。主动算出原始数据大约 8 到 12GBHashSet 方案大约需要 40GB 以上所以直接装进单机内存不现实。这一步是让面试官知道你对数据规模敏感。第三步给出主线方案。比如“如果可用内存在 512MB 左右我倾向于把数据哈希分片成 160 个左右的桶每个桶在单进程里用 HashSet 精确去重最后合并结果。这个方案精确、可控、单机就能做。如果内存更紧把分片数加大就行。”第四步补充备选。可以说“如果业务上只需要判断某个短语是否出现过允许很小的误判率比如 1%那我用布隆过滤器大概 480MB能覆盖 4 亿条比哈希分片更快但不能输出完整集合也无法删除元素。”第五步说实现重点。比如分片的取模逻辑、临时文件的处理、大小写归一化、哈希函数选型、负载均衡检查。这步是为了证明你不光会画方案还知道落地时容易出问题的地方在哪。6.2 高频追问与应对面试官后续的追问通常集中在几个方向上。问“如果重复率很高怎么办”先答可以先做一次采样估算重复率。如果重复率超过 50%可以先做一轮近似去重比如用布隆过滤器或抽样统计把明显重复的数据过滤掉然后再对瘦身后的集合做精确处理。数据量会在第一轮就大幅下降。问“如果短语长度特别长怎么办”长短语会推高原始数据量和字符串对象开销Trie 和哈希分片的收益反而更明显。另外可以考虑先对短语计算 64 位或 128 位哈希只对哈希值集合做去重代价是会产生碰撞需要评估碰撞概率是否可以接受。问“如何保证分片均匀”说明选择 murmur3 这类分布性好的哈希函数并且可以在分片前做一次抽样验证统计各分片的记录数方差如果发现某个桶过大再对这个桶做二次分片。问“如果必须精确而且内存又很小怎么办”直接落到外部排序。把数据分批排序后多路归并归并时去重内存稳定可控。这些问题没有标准答案但都有共同点你需要回到“约束、代价、权衡”三个词上把每种方案的边界说清楚。6.3 面试官视角的评分点我站在面试官的角度会从四个维度给这类题打分第一是否主动澄清需求而不是埋头就答第二是否能量化内存和时间而不是只给定性的“快”、“省”第三是否能比较多个方案的优缺点而不是只会一个第四是否了解工程落地的坑而不是讲完原理就完了。前两点能拉开大部分差距第三点决定你是共识还是亮点第四点是区分“背过题”和“真做过”的分水岭。7. 我在海量数据去重上踩过的坑7.1 线上布隆过滤器翻车记录前几年我在一个爬虫系统里用布隆过滤器做 URL 去重预估 5000 万条 URL特意把误判率压到 0.01%想着肯定够稳。结果上线一周后发现去重率异常偏高很多新 URL 直接被判定成重复。排查之后发现两个问题一是 URL 里有大小写和尾部斜杠的差异我忘了做归一化导致同一条 URL 被多种变形各插入了一次占用了大量位二是当时选了一个质量不高的字符串哈希分布严重不均匀一些位段被反复置 1而另一些几乎没被动过直接用掉了预期之外的容量。从那以后我的习惯就变成布隆过滤器上线前先取 10 万条真实数据做一次模拟统计实际误判率是否跟理论值接近。同时对比特位图的密度分布如果发现某些区域明显偏热就换哈希函数或者直接上 murmur3 配合不同种子。这些验证只需要跑几分钟但能省掉上线后好几天排查的功夫。7.2 去重之前的清洗往往比去重本身更重要去重踩的第二个坑来自数据清洗。所谓“4 亿英语短语”真实数据里几乎一定有大小写不统一、前后有空格、中间有多个连续空格、带了奇怪的制表符甚至换行符的情况。如果不去清洗直接做哈希或插入集合同一句话 “Hello World” 和 “hello world” 会被当成两条不同数据去重后的数量看起来正常但业务方拿到的结果就是不对的。所以我在方案里永远会把“归一化”放在第一步统一转小写、trim 首尾空白、把连续空白符压成一个空格、按需求决定是否去掉标点。这个步骤不花哨但对最终结果的准确性影响极大。面试时主动提一句“我会先做归一化”能瞬间看出你有真实数据经验因为只有被脏数据毒打过的人才会对这一步有执念。7.3 给准备面试的人几条实在建议把经典框架背熟只是基础真正有效的是把这三件事练成本能第一任何数据规模问题先动手估算一分钟内给出数量级第二任何方案都要说“在什么条件下成立在什么条件下失效”没有银弹第三准备一两个自己真正做过的去重案例不管是日志清洗、用户 ID 去重还是数据库抽数真实细节永远比虚拟案例有说服力。我个人面了这么多人最后能给的高分理由几乎都不是“方案多炫”而是“这个人把账算得很清楚”。算不清账方案再好也是空中楼阁。把这篇文章里的计算过程自己动手推一遍再找一个数据集亲手做一次分片或布隆实验你下一次遇到这道题就不会是背答案而是真正在解决问题。