得物搜推(偏工程)一面:HashMap 扩容、GC 与千亿行日志算 Top 10
- 轮次
- 一面
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
实习与项目
- 你们这个系统有多少人在用,用户量多大?(借调部门场景)
- 相关的维护工作是你做吗?
- 实习经历你最大的收获是什么?
- 从 0 到 1 接触新领域,你是怎么快速学习入门的?
Java 基础
- Java 里哈希表是怎么实现的?
- HashMap 扩容的时候是怎么扩容的?
- 红黑树是一种什么样的数据结构?
- JVM 的垃圾回收机制大概是什么样的(含内存区域和回收算法)?
并发
- 现在要实现一个线程安全的计数器,你有哪些方案?
- 如果借用外部中间件或开源组件,还有什么方案?
场景题
- 几百 G、几千亿行的搜索日志,怎么统计 Top 10 搜索词?
《参考解析》
HashMap 的实现与扩容。 JDK 8 之前是「数组 + 链表」,JDK 8 起是「数组 + 链表 + 红黑树」。put 时先用 hash(key)(高 16 位异或低 16 位,让高位也参与定位)与 n-1 做与运算得到桶下标;桶为空就放新节点,否则遍历链表/树,key 相同就覆盖,不同就尾插(JDK 8 改为尾插,避免 JDK 7 头插在并发扩容时成环)。当链表长度 ≥8 且数组长度 ≥64 时转红黑树(数组不足 64 时优先扩容),树节点数 ≤6 时退化回链表。扩容(resize)在元素数超过 容量 × 负载因子(默认 0.75)时触发,容量翻倍,元素重新分布:JDK 8 利用「容量是 2 的幂」这一点,只看 hash 在旧容量位上是 0 还是 1,0 留在原位置、1 移到「原位置 + 旧容量」,避免重新计算 hash,也不需要整棵树重建(树会 split 成两棵,必要时退化)。为什么容量必须是 2 的幂:这样 n-1 是低位全 1 的掩码,取模变成按位与,且扩容时分布规则简单。
红黑树。 一种自平衡二叉查找树,五个性质:节点非红即黑、根是黑、叶子(NIL)是黑、红节点的子节点必须是黑、从任一节点到其所有叶子的路径上黑节点数相同。这些约束保证最长路径不超过最短路径的两倍,树高 O(log n)。插入/删除通过变色与旋转(左旋、右旋)恢复平衡,相比 AVL 树旋转次数更少、更适合频繁插入删除的场景。HashMap 用它是因为单个桶里元素多时链表查询 O(n),树化后降到 O(log n),防止哈希碰撞攻击导致性能退化。
JVM 内存区域与 GC。 区域:线程私有的程序计数器、虚拟机栈、本地方法栈;共享的堆与方法区(JDK 8 起为元空间);另有直接内存。堆分新生代(Eden + 两个 Survivor,默认 8:1:1)与老年代。回收算法:标记-清除(产生碎片)、标记-复制(新生代,浪费一半空间但快)、标记-整理(老年代,无碎片但慢)、分代收集。常见收集器:Serial(单线程)、Parallel(吞吐优先)、CMS(并发标记清除,低停顿但有碎片与 Concurrent Mode Failure)、G1(分区 Region、可预测停顿、JDK 9 起默认)、ZGC/Shenandoah(超低停顿,着色指针/读屏障)。对象晋升:在 Survivor 间来回复制、年龄达阈值(默认 15)或大对象直接进老年代、动态年龄判定(同龄对象总和超过 Survivor 一半就提前晋升)。要能说出「什么时候触发 Minor GC / Full GC」以及「Full GC 频繁先查内存泄漏还是参数不合理」。
线程安全计数器的方案。 ① synchronized 或 ReentrantLock 包住 ++——最简单,竞争激烈时性能差;② AtomicInteger/AtomicLong——CAS 无锁,低竞争快,高竞争下自旋重试多;③ LongAdder——分段累加(base + Cell 数组),读时求和,高并发写场景吞吐最好,适合统计类(QPS、计数),不适合要求「读到的就是精确当前值」的场景;④ volatile 不行(++ 不是原子操作);⑤ 线程封闭——每个线程自己累加、最后汇总,本质同 LongAdder。选择依据是「读写比例 + 竞争强度 + 是否要求强一致读」。这题常被用来考察你是否知道 CAS 的 ABA 与伪共享(LongAdder 的 Cell 用 @Contended 填充避免伪共享)。
用外部中间件做计数。 Redis 的 INCR/INCRBY 是单线程原子操作,天然适合分布式计数;要注意的是一致性(主从异步复制下故障切换可能丢计数)、热点 key(单个 key 打满一个分片,要按维度拆 key 再汇总)、以及持久化(RDB 快照间隔内宕机会丢)。也可以按业务分桶(counter:{shard})后由定时任务汇总。数据库方案是 update t set c = c + 1 where id = ? 靠行锁保证原子,配唯一索引做幂等,但扛不住高并发。消息队列方案则是「写事件入队、消费端累加并落库」,用最终一致换吞吐。
几百 G、几千亿行日志算 Top 10。 这题考的是「不能把数据全放进内存」。标准解法是分治 + 小顶堆:① 按 hash(搜索词) % N 把日志流式扫一遍,拆成 N 个小文件(同一搜索词一定落在同一个文件),保证每个小文件能放进内存;② 对每个小文件用哈希表统计词频,再用大小为 10 的小顶堆选出该文件的 Top 10;③ 把 N 个文件的 Top 10 合并(最多 N×10 个候选),再统计一次全局 Top 10。复杂度是 O(总行数 + 候选数·log 10),内存是 O(单词种类数 / N)。工程上的补充:用 MapReduce/Spark 就是同一思路(map 阶段局部 Top K、reduce 阶段合并);如果允许近似,可以用 Count-Min Sketch 或 Space-Saving 算法,内存固定、误差可控;实际还要考虑「搜索词归一化」(大小写、去空格、同义词合并)和「刷量过滤」(同一用户短时间重复搜索只算一次)。回答时把「为什么不能直接排序」「为什么用哈希分桶而不是范围分桶」「小顶堆为什么选 10」讲清楚,基本就满分。