“常见面试题精讲”这个系列写到第四期我换了一套打法。前几期我把注意力放在纯算法题上这次我特意挑了几道看起来基础、但非常考验深度的题手写 LRU 缓存、TCP 三次握手、HashMap 的哈希冲突、数据库的 B 树索引。它们分别来自数据结构、网络协议、语言底层、数据库存储这四个领域正好是技术面试里出现频率最高、又最容易“背答案翻车”的地方。我当面试官这几年见过太多“答案背得滚瓜烂熟追问一根针就扎破”的候选人。比如问到“为什么 HashMap 用红黑树”张口就是“链表超过 8 转红黑树”但你再问一句“为什么是 8不是 16”很多人就开始沉默了。所以这一期我不想只给标准答案而是把每个问题的推导过程掰开告诉你面试官问这道题到底想听到什么。文章会偏长建议拿纸笔跟着推一遍效果比单纯收藏好得多。1. 这一期的选题逻辑为什么挑这 4 道题1.1 四道题背后的共同考点先换个角度从面试官选材的角度看。面试官出一道题很多时候不是为了让你“做出来”而是观察你的思维链路。手写 LRU 缓存表面上是在考数据结构设计实际上是在看你怎么从“O(1) 读写”这个硬约束反推方案。TCP 三次握手看起来是网络八股实际是在考“通信双方如何在一个不可靠环境里对齐初始状态”。HashMap 哈希冲突表面是背源码实际是考“工程里如何做量化取舍而不是堆特效”。数据库索引结构表面是理论题实际是考“磁盘 IO 和内存 IO 的本质差异”这才是设计存储引擎的底层逻辑。这四个主题凑在一起覆盖的面试方向也比较全面试题核心考察常见落败点LRU 缓存数据结构设计、复杂度分析直接背 LinkedHashMap不讲原理TCP 三次握手状态机、可靠传输只会背“SYN、SYN ACK、ACK”HashMap 冲突哈希、负载因子、扩容只会说“数组加链表”后面接不上B 树索引磁盘 IO、树高、范围查询只背“叶子链表”不知为什么需要如果你正在准备 3-5 年经验的后端、客户端或者数据岗位这四类题几乎绕不开。就算不面试把这几块吃透对排查线上问题也有实际帮助。1.2 这套题在面试里的辐射范围这组题还有一个特点都可以从“一句话答案”一直追问到“系统设计级别”。以 LRU 为例你可以只回答“HashMap 加双向链表”也能继续牵扯出缓存淘汰策略、Redis 的近似 LRU、数据库 buffer pool 的管理。面试官可以根据候选人的回答深度快速判断他的经验层级。所以这一期真正要练的不是你记住了多少而是你能不能在不同深度之间自由切换。2. 题目一手写 LRU 缓存别只会背 LinkedHashMap2.1 先想清楚 LRU 到底解决什么问题LRU全称 Least Recently Used最近最少使用。它是一个缓存淘汰策略。真实场景里后台服务不可能每次都去查数据库需要把一部分热数据放在内存里。但内存有限缓存不能无限增长总得把某些数据踢出去。踢谁最简单的原则就是过去一段时间没被访问的未来大概率也不会被访问先把它们淘汰掉。题目通常是这样实现一个LRUCacheget(key)返回 key 对应的 value如果不存在返回 -1put(key, value)写入或更新 key 对应的 value要求 get 和 put 的平均时间复杂度都是 O(1)当缓存容量达到上限时删除最久未被访问的数据。注意最后一个要求它意味着每访问一次数据这条数据的“新鲜度”就要刷新。这不仅是缓存题也是一种非常常见的生产环境需求。2.2 从复杂度要求反推数据结构很多人的第一反应是“用一个数组每次访问把元素移到末尾满了就把头元素丢掉”。这个思路能实现 LRU 语义但不可行因为数组中间移动元素是 O(n)查找元素也是 O(n)。要满足 O(1) 读写必须把两个数据结构组合起来哈希表负责 O(1) 的 key 查找双向链表负责维护访问顺序头部是最近访问的尾部是最久未访问的。为什么线性表不行因为每次命中后要把节点移到头部链表可以把“摘除节点再插入头部”这两步都控制在 O(1)。这里的关键是双向链表不是单向链表。单向链表的问题在于如果要淘汰尾部节点你需要把尾部节点的前一个节点也找出来否则没法把链表的“尾部指针”更新到前一位。而单链表找前驱只能从头遍历时间复杂度退化成 O(n)。双向链表每个节点都有prev指针摘除任意节点都是常数时间。哈希表里的 value 不存普通数据而是存“双向链表的节点引用”或者节点本身。这样当我们通过 key 找到节点后可以立刻拿到它的前驱和后继完成顺序调整。一个小陷阱链表节点里必须存 key不能只存 value。因为当缓存满了要从链表尾部淘汰一个节点时你不仅要从链表里摘除它还要从哈希表里把对应的 key 删掉。如果节点只存 value没有 key你无法在哈希表里定位到要删除的那一项。2.3 可以直接抄的参考实现下面这份 Java 实现是我自己在面试里写出来过也拿去面试过别人的版本。没有用任何第三方依赖看完可以直接抄。import java.util.HashMap; import java.util.Map; public class LRUCache { private final int capacity; private final MapInteger, Node map new HashMap(); // 虚拟头尾节点避免边界判断 private final Node head new Node(0, 0); private final Node tail new Node(0, 0); private static class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key key; this.value value; } } public LRUCache(int capacity) { this.capacity capacity; head.next tail; tail.prev head; } public int get(int key) { Node node map.get(key); if (node null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { Node node map.get(key); if (node null) { Node newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); // 超出容量删除尾部节点 if (map.size() capacity) { Node last tail.prev; removeNode(last); map.remove(last.key); } } else { node.value value; moveToHead(node); } } private void addToHead(Node node) { node.next head.next; node.prev head; head.next.prev node; head.next node; } private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(Node node) { removeNode(node); addToHead(node); } }写这份代码时有几个细节必须处理好大多数情况你不需要判断head.next是否为空因为有了虚拟头尾节点链表永远不会空put里如果 key 已经存在除了更新 value必须moveToHead否则这个节点的“新鲜度”没有刷新删除尾部节点时一定要同时从map删掉对应 key否则 map 里会残留数据后续 get 会拿到过期引用。2.4 面试官常追着问的 5 个点别再停留在“我能写出来”这个层面下面这些问题才是拉分项。追问 1为什么用双向链表不用单向链表刚才说了单链表删除尾部节点时找不到前驱。即使你额外加一个“尾节点前驱”的指针也只能解决尾部删除的问题无法解决任意节点被命中后“摘除再移到头部”的操作。真正命中的节点可能在链表中间单链表要从头遍历过去才能摘除它。追问 2用 LinkedHashMap 不就行了吗Java 的LinkedHashMap(initialCapacity, loadFactor, accessOrdertrue)确实能实现 LRU 语义底层其实就是哈希表加双向链表和手写思路一致。但面试官让你手写是想确认你理解原理而不是会用工具。如果你先答“可以用 LinkedHashMap”最好立刻补一句“它的内部实现就是哈希表加双向链表重写 removeEldestEntry 就可以控制淘汰策略”。追问 3如果把 get 设计成“不调整访问顺序”会有什么后果那 LRU 就退化成了 FIFO。一个在极短时间内被访问一万次的数据和一条一分钟前访问过一次的数据在“不调整顺序”的策略下地位相同。真实缓存里这种热点数据很容易被下一次写入挤出去命中率会明显下降。追问 4线程安全怎么处理直接说“这题默认单线程环境”是一种说法但更专业的回答是如果需要并发安全可以在 get/put 外面加锁或者用ConcurrentHashMap配合分段锁思路但依赖场景。面试官问这个主要想看你是不是知道原生 HashMap 不是线程安全的以及你能否分清“读多写少”和“写多读少”的不同优化方向。追问 5容量为 0 时代码会不会挂这是一个很有杀伤力的边界测试。在容量为 0 的情况下执行put代码会插入新节点然后判断map.size() capacity也就是 1 0成立于是删除尾部节点也就是刚插入的那个节点。整个过程自洽不会出现空指针。这个边界如果你没想过面试时很可能被这个追问问懵。3. 题目二TCP 三次握手为什么是三次不能是两次吗3.1 为什么一道网络题让很多人翻车很多人觉得 TCP 三次握手是送分题因为标准答案早背熟了客户端发 SYN服务端回 SYN ACK客户端再回 ACK。但面试官只要多问一句“为什么不是两次”就倒下一大片。这道题考的不是流程而是状态机思维。TCP 是一个面向连接的可靠传输协议连接的本质是什么是通信双方为了后续传输数据在内存里建立一套状态记录包括双方的初始序号、窗口大小、拥塞控制参数等等。三次握手的核心目标是让双方把“我要发送数据的起始序号”和“对端要发送数据的起始序号”对齐。3.2 用状态机看三次握手不要只记报文名字要记状态迁移。假设客户端是主动方服务端是被动方初始状态客户端 CLOSED服务端 LISTEN客户端发送SYN, seqx进入 SYN_SENT服务端收到回复SYN, seqy, ACK, ackx1进入 SYN_RCVD客户端收到确认服务端的序号回复ACK, acky1进入 ESTABLISHED服务端收到这个 ACK也进入 ESTABLISHED。关键就在第 2 步和第 3 步。第二次握手服务端不但回复了 ACK还携带了自己的 SYN。这意味着“确认你的 SYN 有效”和“我的 SYN 也要你确认”这两个动作被合并到了一起。3.3 为什么两次不够四次又多余先看两次握手的问题。假设只有两次客户端发 SYN服务端回 SYN ACK然后服务端就认为连接建立完成开始分配资源。问题是如果这个 SYN 是网络里滞留很久的旧连接请求客户端早就放弃了现在重新发出来服务端不知道就会为一个无效连接创建资源。另一个更本质的问题两次握手只能保证客户端确认了服务端的接收能力不能保证客户端确认了服务端的发送能力。第二次握手里服务端不但要发 ACK还要发自己的 SYN这需要客户端再回一个 ACK才算闭环。那为什么不干脆做成四次完全可以但没必要。因为第二次握手完全可以把“对客户端 SYN 的确认”和“自己的 SYN”放在同一个报文里同时发出去省掉一次往返。所以三的根本原因是需要两次信息交换来同步序号但其中第二次和第三次可以合并一次收发。它的本质是让双方都知道“我能发你能收你能发我能收”同时完成序号对齐。3.4 容易被继续追问的四次挥手和 TIME_WAIT面试官问完三次握手大概率会顺势问四次挥手。四次挥手比三次握手简单同样要用状态机理解。连接建立后双方都需要关闭。TCP 是全双工每一方的发送通道都要独立关闭主动方发送 FIN进入 FIN_WAIT_1被动方收到 FIN回复 ACK进入 CLOSE_WAIT此时主动方的发方向关闭但被动方还可以继续发数据被动方数据发送完毕发送 FIN进入 LAST_ACK主动方收到 FIN回复 ACK进入 TIME_WAIT等待 2MSL 后彻底关闭。为什么主动方要等 2MSL两个原因一是确保最后的 ACK 能到达被动方如果 ACK 丢了被动方会重发 FIN二是为了让旧的报文在网络中消失避免影响后续新连接。3.5 回答这道题的加分结构我建议用“三次握手在解决什么问题 → 为什么两次不行 → 为什么三次刚好 → 状态如何迁移”这个顺序回答。这样既讲了流程又讲了原理面试官可以从你的回答里看到你理解“可靠传输”的本质。4. 题目三HashMap 哈希冲突后的数据结构面试官到底想听什么4.1 冲突不是 bug是哈希表的宿命哈希表的本质是把大范围 key 映射到小范围数组下标映射函数就是哈希函数。既然是“大映射到小”冲突就是不可避免的。面试从“冲突”切入实际上是在看你对哈希表这个数据结构的基本认知是否扎实。常见的冲突解决策略有两种开放寻址法和链地址法。Java 的 HashMap 用的是链地址法也叫拉链法。做法是数组每个位置挂一个链表所有哈希到同一个下标的元素都放进这个链表。理解链表只是在“冲突发生”时的兜底方案这一点很重要。它并不意味着“桶里有链表就是性能差”。在负载因子合理、哈希函数均匀的前提下每个桶的平均节点数很小链表的查找代价接近常数级。4.2 链地址法和开放寻址法的实际选型开放寻址法的思路是如果当前位置被占了就按某种规则找下一个空位。它所有数据都存放在数组里不需要额外链表节点缓存局部性更好但删除操作很麻烦负载因子也不能太高否则探测次数会暴涨。链地址法则相反它允许负载因子超过 1删除简单但每个节点多存了指针缓存局部性略差。维度链地址法开放寻址法存储方式数组 链表纯数组删除实现直接从链表摘除需要标记删除逻辑更繁琐负载因子可以超过 1通常小于 0.8缓存局部性较差较好典型应用Java HashMapPython dict 的一部分、ThreadLocalMap如果你能说出这个对比面试官会知道你不仅会用 HashMap还理解不同哈希策略在不同语言和场景里的差异。4.3 Java 8 的链表和红黑树是优化不是标配在 Java 8 之前HashMap 的桶里面只有链表。如果哈希函数设计得不好或者恶意构造 key让大量数据落到同一个桶里get 的复杂度会直接退化成 O(n)。Java 8 的优化是当某个桶的节点数超过TREEIFY_THRESHOLD 8并且数组容量超过 64这个桶里的链表会转成红黑树把最坏复杂度从 O(n) 降到 O(log n)。判断链表是否转树的代码通常长这样if (binCount TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); }treeifyBin内部还会先判断数组容量if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) { resize(); }这意味着如果数组容量不到 64即使某个桶里已经有 8 个节点HashMap 也不会立刻树化而是先扩容。扩容后哈希重分布桶里的节点数会减少冲突自然缓解。这个设计非常有意思先用扩容解决问题实在解决不了再上重型数据结构。那为什么阈值选 8网上流传很广的说法是泊松分布。假设负载因子 0.75哈希函数足够均匀一个桶里出现 k 个节点的概率大约等于P(k) (e^(-λ) * λ^k) / k!其中 λ 约为 0.5代入 k8 算出来大概是 6e-8。这个概率已经非常低了。所以“8”不是一个硬性性能指标而是一个安全阈值正常情况下永远到不了 8一旦到了说明出现了极端哈希冲突这时候上红黑树可以兜底。4.4 扩容、hash 函数和高低位异或HashMap 的容量始终是 2 的整数次幂这背后有一个工程便利取模运算hash % capacity可以写成hash (capacity - 1)按位与比取模快得多。但这也带来一个隐患如果hashCode的低位分布不均匀直接拿低位做数组下标会导致大量元素挤在少数几个桶里。Java 8 的答案是在哈希完再做一次扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把高 16 位和低 16 位做异或让高位也能参与到低位的计算里。这个操作不改变哈希值的高位但对数组容量比较小的情况能显著改善低位分布的随机性。扩容方面在 Java 8 里也有优化。每次容量翻倍后旧元素迁移不需要重新计算全部哈希只需要看hash oldCap的结果。如果结果是 0元素留在原位置否则元素下标要加上 oldCap。这个设计用位运算替代了全量重哈希效率高很多。4.5 常见翻车点面试里最常见的翻车回答是HashMap 的 get 是 O(1)。如果你不加限定词面试官立刻会用“最坏情况退化到 O(n)”来反击。更严谨的说法是平均 O(1)最坏 O(n)引入红黑树后最坏 O(log n)。另一个翻车点是完全不提hash()扰动、负载因子、扩容条件。这三者才是面试官判断你是不是真正读过源码的分水岭。你不需要背全源码但至少得说出“负载因子 0.75 是时间空间权衡的结果扩容会触发重哈希哈希函数要考虑高位参与运算”这三个关键点。5. 题目四数据库索引为什么是 B 树不是红黑树也不是哈希索引5.1 一切从磁盘 IO 的代价开始要回答这道题必须先建立“磁盘比内存慢几个数量级”这个前提。数据库的数据量太大不可能全部常驻内存索引文件落在磁盘上。内存随机访问是纳秒级别磁盘随机访问是毫秒级别差了百万倍级别。所以数据库索引设计的第一目标不是“代码效率高”而是“尽量减少磁盘 IO 次数”。一个简单模型是每次访问一个节点如果这个节点不在内存里就要产生一次磁盘 IO。控制树高就是控制查询要访问的层数。5.2 为什么红黑树不适合做数据库索引红黑树是平衡二叉搜索树它保持树高约为 log2(n)。看起来不错但有两个问题。第一树高太高。一亿条数据红黑树高度大约 27 层意味着一次查询在最坏情况下要访问 27 个节点。如果这些节点都不在内存那就要做 27 次磁盘 IO。而 B 树的扇出通常有几百甚至上千树高只有 3 层同样一次查询只要 2 到 3 次 IO。第二红黑树每个节点的空间占用很“小气”。
面试必问：LRU缓存、TCP三次握手、HashMap冲突、B+树索引深度解析
“常见面试题精讲”这个系列写到第四期我换了一套打法。前几期我把注意力放在纯算法题上这次我特意挑了几道看起来基础、但非常考验深度的题手写 LRU 缓存、TCP 三次握手、HashMap 的哈希冲突、数据库的 B 树索引。它们分别来自数据结构、网络协议、语言底层、数据库存储这四个领域正好是技术面试里出现频率最高、又最容易“背答案翻车”的地方。我当面试官这几年见过太多“答案背得滚瓜烂熟追问一根针就扎破”的候选人。比如问到“为什么 HashMap 用红黑树”张口就是“链表超过 8 转红黑树”但你再问一句“为什么是 8不是 16”很多人就开始沉默了。所以这一期我不想只给标准答案而是把每个问题的推导过程掰开告诉你面试官问这道题到底想听到什么。文章会偏长建议拿纸笔跟着推一遍效果比单纯收藏好得多。1. 这一期的选题逻辑为什么挑这 4 道题1.1 四道题背后的共同考点先换个角度从面试官选材的角度看。面试官出一道题很多时候不是为了让你“做出来”而是观察你的思维链路。手写 LRU 缓存表面上是在考数据结构设计实际上是在看你怎么从“O(1) 读写”这个硬约束反推方案。TCP 三次握手看起来是网络八股实际是在考“通信双方如何在一个不可靠环境里对齐初始状态”。HashMap 哈希冲突表面是背源码实际是考“工程里如何做量化取舍而不是堆特效”。数据库索引结构表面是理论题实际是考“磁盘 IO 和内存 IO 的本质差异”这才是设计存储引擎的底层逻辑。这四个主题凑在一起覆盖的面试方向也比较全面试题核心考察常见落败点LRU 缓存数据结构设计、复杂度分析直接背 LinkedHashMap不讲原理TCP 三次握手状态机、可靠传输只会背“SYN、SYN ACK、ACK”HashMap 冲突哈希、负载因子、扩容只会说“数组加链表”后面接不上B 树索引磁盘 IO、树高、范围查询只背“叶子链表”不知为什么需要如果你正在准备 3-5 年经验的后端、客户端或者数据岗位这四类题几乎绕不开。就算不面试把这几块吃透对排查线上问题也有实际帮助。1.2 这套题在面试里的辐射范围这组题还有一个特点都可以从“一句话答案”一直追问到“系统设计级别”。以 LRU 为例你可以只回答“HashMap 加双向链表”也能继续牵扯出缓存淘汰策略、Redis 的近似 LRU、数据库 buffer pool 的管理。面试官可以根据候选人的回答深度快速判断他的经验层级。所以这一期真正要练的不是你记住了多少而是你能不能在不同深度之间自由切换。2. 题目一手写 LRU 缓存别只会背 LinkedHashMap2.1 先想清楚 LRU 到底解决什么问题LRU全称 Least Recently Used最近最少使用。它是一个缓存淘汰策略。真实场景里后台服务不可能每次都去查数据库需要把一部分热数据放在内存里。但内存有限缓存不能无限增长总得把某些数据踢出去。踢谁最简单的原则就是过去一段时间没被访问的未来大概率也不会被访问先把它们淘汰掉。题目通常是这样实现一个LRUCacheget(key)返回 key 对应的 value如果不存在返回 -1put(key, value)写入或更新 key 对应的 value要求 get 和 put 的平均时间复杂度都是 O(1)当缓存容量达到上限时删除最久未被访问的数据。注意最后一个要求它意味着每访问一次数据这条数据的“新鲜度”就要刷新。这不仅是缓存题也是一种非常常见的生产环境需求。2.2 从复杂度要求反推数据结构很多人的第一反应是“用一个数组每次访问把元素移到末尾满了就把头元素丢掉”。这个思路能实现 LRU 语义但不可行因为数组中间移动元素是 O(n)查找元素也是 O(n)。要满足 O(1) 读写必须把两个数据结构组合起来哈希表负责 O(1) 的 key 查找双向链表负责维护访问顺序头部是最近访问的尾部是最久未访问的。为什么线性表不行因为每次命中后要把节点移到头部链表可以把“摘除节点再插入头部”这两步都控制在 O(1)。这里的关键是双向链表不是单向链表。单向链表的问题在于如果要淘汰尾部节点你需要把尾部节点的前一个节点也找出来否则没法把链表的“尾部指针”更新到前一位。而单链表找前驱只能从头遍历时间复杂度退化成 O(n)。双向链表每个节点都有prev指针摘除任意节点都是常数时间。哈希表里的 value 不存普通数据而是存“双向链表的节点引用”或者节点本身。这样当我们通过 key 找到节点后可以立刻拿到它的前驱和后继完成顺序调整。一个小陷阱链表节点里必须存 key不能只存 value。因为当缓存满了要从链表尾部淘汰一个节点时你不仅要从链表里摘除它还要从哈希表里把对应的 key 删掉。如果节点只存 value没有 key你无法在哈希表里定位到要删除的那一项。2.3 可以直接抄的参考实现下面这份 Java 实现是我自己在面试里写出来过也拿去面试过别人的版本。没有用任何第三方依赖看完可以直接抄。import java.util.HashMap; import java.util.Map; public class LRUCache { private final int capacity; private final MapInteger, Node map new HashMap(); // 虚拟头尾节点避免边界判断 private final Node head new Node(0, 0); private final Node tail new Node(0, 0); private static class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key key; this.value value; } } public LRUCache(int capacity) { this.capacity capacity; head.next tail; tail.prev head; } public int get(int key) { Node node map.get(key); if (node null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { Node node map.get(key); if (node null) { Node newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); // 超出容量删除尾部节点 if (map.size() capacity) { Node last tail.prev; removeNode(last); map.remove(last.key); } } else { node.value value; moveToHead(node); } } private void addToHead(Node node) { node.next head.next; node.prev head; head.next.prev node; head.next node; } private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(Node node) { removeNode(node); addToHead(node); } }写这份代码时有几个细节必须处理好大多数情况你不需要判断head.next是否为空因为有了虚拟头尾节点链表永远不会空put里如果 key 已经存在除了更新 value必须moveToHead否则这个节点的“新鲜度”没有刷新删除尾部节点时一定要同时从map删掉对应 key否则 map 里会残留数据后续 get 会拿到过期引用。2.4 面试官常追着问的 5 个点别再停留在“我能写出来”这个层面下面这些问题才是拉分项。追问 1为什么用双向链表不用单向链表刚才说了单链表删除尾部节点时找不到前驱。即使你额外加一个“尾节点前驱”的指针也只能解决尾部删除的问题无法解决任意节点被命中后“摘除再移到头部”的操作。真正命中的节点可能在链表中间单链表要从头遍历过去才能摘除它。追问 2用 LinkedHashMap 不就行了吗Java 的LinkedHashMap(initialCapacity, loadFactor, accessOrdertrue)确实能实现 LRU 语义底层其实就是哈希表加双向链表和手写思路一致。但面试官让你手写是想确认你理解原理而不是会用工具。如果你先答“可以用 LinkedHashMap”最好立刻补一句“它的内部实现就是哈希表加双向链表重写 removeEldestEntry 就可以控制淘汰策略”。追问 3如果把 get 设计成“不调整访问顺序”会有什么后果那 LRU 就退化成了 FIFO。一个在极短时间内被访问一万次的数据和一条一分钟前访问过一次的数据在“不调整顺序”的策略下地位相同。真实缓存里这种热点数据很容易被下一次写入挤出去命中率会明显下降。追问 4线程安全怎么处理直接说“这题默认单线程环境”是一种说法但更专业的回答是如果需要并发安全可以在 get/put 外面加锁或者用ConcurrentHashMap配合分段锁思路但依赖场景。面试官问这个主要想看你是不是知道原生 HashMap 不是线程安全的以及你能否分清“读多写少”和“写多读少”的不同优化方向。追问 5容量为 0 时代码会不会挂这是一个很有杀伤力的边界测试。在容量为 0 的情况下执行put代码会插入新节点然后判断map.size() capacity也就是 1 0成立于是删除尾部节点也就是刚插入的那个节点。整个过程自洽不会出现空指针。这个边界如果你没想过面试时很可能被这个追问问懵。3. 题目二TCP 三次握手为什么是三次不能是两次吗3.1 为什么一道网络题让很多人翻车很多人觉得 TCP 三次握手是送分题因为标准答案早背熟了客户端发 SYN服务端回 SYN ACK客户端再回 ACK。但面试官只要多问一句“为什么不是两次”就倒下一大片。这道题考的不是流程而是状态机思维。TCP 是一个面向连接的可靠传输协议连接的本质是什么是通信双方为了后续传输数据在内存里建立一套状态记录包括双方的初始序号、窗口大小、拥塞控制参数等等。三次握手的核心目标是让双方把“我要发送数据的起始序号”和“对端要发送数据的起始序号”对齐。3.2 用状态机看三次握手不要只记报文名字要记状态迁移。假设客户端是主动方服务端是被动方初始状态客户端 CLOSED服务端 LISTEN客户端发送SYN, seqx进入 SYN_SENT服务端收到回复SYN, seqy, ACK, ackx1进入 SYN_RCVD客户端收到确认服务端的序号回复ACK, acky1进入 ESTABLISHED服务端收到这个 ACK也进入 ESTABLISHED。关键就在第 2 步和第 3 步。第二次握手服务端不但回复了 ACK还携带了自己的 SYN。这意味着“确认你的 SYN 有效”和“我的 SYN 也要你确认”这两个动作被合并到了一起。3.3 为什么两次不够四次又多余先看两次握手的问题。假设只有两次客户端发 SYN服务端回 SYN ACK然后服务端就认为连接建立完成开始分配资源。问题是如果这个 SYN 是网络里滞留很久的旧连接请求客户端早就放弃了现在重新发出来服务端不知道就会为一个无效连接创建资源。另一个更本质的问题两次握手只能保证客户端确认了服务端的接收能力不能保证客户端确认了服务端的发送能力。第二次握手里服务端不但要发 ACK还要发自己的 SYN这需要客户端再回一个 ACK才算闭环。那为什么不干脆做成四次完全可以但没必要。因为第二次握手完全可以把“对客户端 SYN 的确认”和“自己的 SYN”放在同一个报文里同时发出去省掉一次往返。所以三的根本原因是需要两次信息交换来同步序号但其中第二次和第三次可以合并一次收发。它的本质是让双方都知道“我能发你能收你能发我能收”同时完成序号对齐。3.4 容易被继续追问的四次挥手和 TIME_WAIT面试官问完三次握手大概率会顺势问四次挥手。四次挥手比三次握手简单同样要用状态机理解。连接建立后双方都需要关闭。TCP 是全双工每一方的发送通道都要独立关闭主动方发送 FIN进入 FIN_WAIT_1被动方收到 FIN回复 ACK进入 CLOSE_WAIT此时主动方的发方向关闭但被动方还可以继续发数据被动方数据发送完毕发送 FIN进入 LAST_ACK主动方收到 FIN回复 ACK进入 TIME_WAIT等待 2MSL 后彻底关闭。为什么主动方要等 2MSL两个原因一是确保最后的 ACK 能到达被动方如果 ACK 丢了被动方会重发 FIN二是为了让旧的报文在网络中消失避免影响后续新连接。3.5 回答这道题的加分结构我建议用“三次握手在解决什么问题 → 为什么两次不行 → 为什么三次刚好 → 状态如何迁移”这个顺序回答。这样既讲了流程又讲了原理面试官可以从你的回答里看到你理解“可靠传输”的本质。4. 题目三HashMap 哈希冲突后的数据结构面试官到底想听什么4.1 冲突不是 bug是哈希表的宿命哈希表的本质是把大范围 key 映射到小范围数组下标映射函数就是哈希函数。既然是“大映射到小”冲突就是不可避免的。面试从“冲突”切入实际上是在看你对哈希表这个数据结构的基本认知是否扎实。常见的冲突解决策略有两种开放寻址法和链地址法。Java 的 HashMap 用的是链地址法也叫拉链法。做法是数组每个位置挂一个链表所有哈希到同一个下标的元素都放进这个链表。理解链表只是在“冲突发生”时的兜底方案这一点很重要。它并不意味着“桶里有链表就是性能差”。在负载因子合理、哈希函数均匀的前提下每个桶的平均节点数很小链表的查找代价接近常数级。4.2 链地址法和开放寻址法的实际选型开放寻址法的思路是如果当前位置被占了就按某种规则找下一个空位。它所有数据都存放在数组里不需要额外链表节点缓存局部性更好但删除操作很麻烦负载因子也不能太高否则探测次数会暴涨。链地址法则相反它允许负载因子超过 1删除简单但每个节点多存了指针缓存局部性略差。维度链地址法开放寻址法存储方式数组 链表纯数组删除实现直接从链表摘除需要标记删除逻辑更繁琐负载因子可以超过 1通常小于 0.8缓存局部性较差较好典型应用Java HashMapPython dict 的一部分、ThreadLocalMap如果你能说出这个对比面试官会知道你不仅会用 HashMap还理解不同哈希策略在不同语言和场景里的差异。4.3 Java 8 的链表和红黑树是优化不是标配在 Java 8 之前HashMap 的桶里面只有链表。如果哈希函数设计得不好或者恶意构造 key让大量数据落到同一个桶里get 的复杂度会直接退化成 O(n)。Java 8 的优化是当某个桶的节点数超过TREEIFY_THRESHOLD 8并且数组容量超过 64这个桶里的链表会转成红黑树把最坏复杂度从 O(n) 降到 O(log n)。判断链表是否转树的代码通常长这样if (binCount TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); }treeifyBin内部还会先判断数组容量if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) { resize(); }这意味着如果数组容量不到 64即使某个桶里已经有 8 个节点HashMap 也不会立刻树化而是先扩容。扩容后哈希重分布桶里的节点数会减少冲突自然缓解。这个设计非常有意思先用扩容解决问题实在解决不了再上重型数据结构。那为什么阈值选 8网上流传很广的说法是泊松分布。假设负载因子 0.75哈希函数足够均匀一个桶里出现 k 个节点的概率大约等于P(k) (e^(-λ) * λ^k) / k!其中 λ 约为 0.5代入 k8 算出来大概是 6e-8。这个概率已经非常低了。所以“8”不是一个硬性性能指标而是一个安全阈值正常情况下永远到不了 8一旦到了说明出现了极端哈希冲突这时候上红黑树可以兜底。4.4 扩容、hash 函数和高低位异或HashMap 的容量始终是 2 的整数次幂这背后有一个工程便利取模运算hash % capacity可以写成hash (capacity - 1)按位与比取模快得多。但这也带来一个隐患如果hashCode的低位分布不均匀直接拿低位做数组下标会导致大量元素挤在少数几个桶里。Java 8 的答案是在哈希完再做一次扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把高 16 位和低 16 位做异或让高位也能参与到低位的计算里。这个操作不改变哈希值的高位但对数组容量比较小的情况能显著改善低位分布的随机性。扩容方面在 Java 8 里也有优化。每次容量翻倍后旧元素迁移不需要重新计算全部哈希只需要看hash oldCap的结果。如果结果是 0元素留在原位置否则元素下标要加上 oldCap。这个设计用位运算替代了全量重哈希效率高很多。4.5 常见翻车点面试里最常见的翻车回答是HashMap 的 get 是 O(1)。如果你不加限定词面试官立刻会用“最坏情况退化到 O(n)”来反击。更严谨的说法是平均 O(1)最坏 O(n)引入红黑树后最坏 O(log n)。另一个翻车点是完全不提hash()扰动、负载因子、扩容条件。这三者才是面试官判断你是不是真正读过源码的分水岭。你不需要背全源码但至少得说出“负载因子 0.75 是时间空间权衡的结果扩容会触发重哈希哈希函数要考虑高位参与运算”这三个关键点。5. 题目四数据库索引为什么是 B 树不是红黑树也不是哈希索引5.1 一切从磁盘 IO 的代价开始要回答这道题必须先建立“磁盘比内存慢几个数量级”这个前提。数据库的数据量太大不可能全部常驻内存索引文件落在磁盘上。内存随机访问是纳秒级别磁盘随机访问是毫秒级别差了百万倍级别。所以数据库索引设计的第一目标不是“代码效率高”而是“尽量减少磁盘 IO 次数”。一个简单模型是每次访问一个节点如果这个节点不在内存里就要产生一次磁盘 IO。控制树高就是控制查询要访问的层数。5.2 为什么红黑树不适合做数据库索引红黑树是平衡二叉搜索树它保持树高约为 log2(n)。看起来不错但有两个问题。第一树高太高。一亿条数据红黑树高度大约 27 层意味着一次查询在最坏情况下要访问 27 个节点。如果这些节点都不在内存那就要做 27 次磁盘 IO。而 B 树的扇出通常有几百甚至上千树高只有 3 层同样一次查询只要 2 到 3 次 IO。第二红黑树每个节点的空间占用很“小气”。