面灵AI→

拼多多服务端研发一二三面:HashMap、Redis 分布式锁与 JVM GC,手撕 HashMap 和反转链表

轮次
一至三面
时间
2026-11
来源
牛客网

《面试题目》

一面

  1. 了解 Java 中的哪些数据结构?
  2. HashMap 有哪几种实现方式?除了把链表转成红黑树,还能如何提升查询效率?
  3. Redis 分布式锁如何实现?
  4. JVM GC 的原理是什么?如何判断一个对象是否可回收?如何保证 GC Roots 充分且正确?
  5. 手撕:实现 HashMap(忽略转化为红黑树的逻辑);如果 key 为 null 如何处理?
  6. 手撕:反转链表。

二面

  1. 实习经历。
  2. 了解哪些 Redis 数据结构?
  3. 手撕:反转字符串中的单词。

三面

  1. 实习经历深挖。

《参考解析》

HashMap 的几种实现与优化。Java 里常见实现有三类:HashMap(数组 + 链表 + 红黑树)、LinkedHashMap(在 HashMap 基础上加双向链表维护插入或访问顺序)、TreeMap(红黑树,按 key 排序,O(log n))。此外还有 ConcurrentHashMap(分段 / CAS + synchronized 桶头)、IdentityHashMap(引用相等)、WeakHashMap(弱引用 key)。除树化之外的优化路径:扩容时把容量设为 2 的幂并用 (n-1) & hash 代替取模;对 hash 值做扰动(高 16 位异或到低位)降低碰撞;控制负载因子(默认 0.75,内存敏感时调高、查询敏感时调低);预设初始容量避免反复 rehash;自定义 key 用不可变对象并缓存 hash;高并发场景换 ConcurrentHashMap。

Redis 分布式锁。SET key value NX PX ttl 一条命令完成加锁与过期,value 存「客户端唯一标识 + 线程 ID」;解锁必须用 Lua 脚本先比对 value 再删除,避免锁过期后误删别人的锁。业务执行时间不确定时要续期(看门狗),续期同样要比对标识、只给自己续。要注意主从切换丢锁的问题:异步复制下主节点宕机可能丢锁,强一致场景用 RedLock 或带 fencing token 的方案。回答时补一句:锁的粒度与超时时间要按业务定,超时太短会误放行、太长会拖死故障恢复。

GC 与可达性分析。主流 JVM 用可达性分析判断对象存活:从 GC Roots 出发做图遍历,不可达的对象可回收。GC Roots 包括:虚拟机栈(栈帧中的局部变量表)引用的对象、本地方法栈引用的对象、方法区中类静态属性引用的对象、常量引用的对象、同步锁 synchronized 持有的对象、JNI 引用,以及 JVM 内部引用(系统类加载器、基本类型 Class 对象等)。「如何保证充分且正确」是这个问题的难点:充分指所有可能存活对象的入口都要覆盖(漏了会把活对象回收,直接崩溃);正确指不能把死对象当根(会导致内存泄漏)。工程上的保证方式是:由 JVM 规范定义根集合、用 OopMap 记录栈上引用位置、在安全点(safepoint)暂停线程扫描、并在 JIT 优化后维护引用映射;应用侧要做的是避免把长生命周期对象塞进静态集合、避免 ThreadLocal 未清理。

手撕 HashMap 要点。核心是「数组 + 链表 + 扩容」:put 时先算 hash(扰动)、定位桶,桶空就新建节点,非空则遍历比对 key(先比 hash 再 equals),命中就覆盖值,未命中就尾插;size 超过阈值(容量 × 负载因子)时扩容为两倍并 rehash。get 同理遍历。key 为 null 的处理是约定俗成的:单独放在 table[0](或一个专门的 null 桶),因为 null 没有 hashCode,不能走正常 hash 流程;HashMap 里 null key 的 hash 固定为 0。写完主动说清并发下会丢数据(需要 ConcurrentHashMap)以及为什么 JDK 8 之后改成尾插(避免并发扩容成环)。

反转链表。迭代用三指针:prev = null,循环里先保存 cur.next,再 cur.next = prev,最后 prev = cur; cur = next,返回 prev。递归的边界是 head == null || head.next == null,递归到最后一个节点后回溯改指向。复杂度 O(n) / O(1)(迭代)。面试里要能顺手写出并说明「为什么必须先保存 next」。

反转字符串中的单词。两种思路:一是按空格切分、反转数组、再用单个空格拼接(注意合并连续空格与首尾空格);二是原地做法——先整体反转,再逐个单词反转,最后清理多余空格。Java 里 split("\\s+") 加 StringBuilder 最直接,但要说明它额外占 O(n) 空间;原地做法在面试里更能体现对双指针的掌握。手撕题记得处理空串与全空格输入。