02 · 栈、队列与哈希表

栈和队列是"受限的线性表"，限制反而是它们的价值。哈希表是"用空间换 O(1)"的极致交易。

一句话本质

• 栈：只在一端进出，所以"后进先出"——它天然适合处理"嵌套"和"回溯"。
• 队列：一端进一端出，所以"先进先出"——它天然适合处理"排队"和"逐层推进"。
• 哈希表：用哈希函数把 key 直接算成数组下标，跳过"查找"这个过程。

生活类比

结构	场景
栈	一摞盘子：只能从最上面拿；浏览器后退（最近的先退）；Ctrl+Z
队列	排队买奶茶：先来先走；打印机任务队列
双端队列	地铁闸机双向都能过（两端都能进出）
优先队列	急诊分诊：不是先来先看，是最严重的先看（本质是堆）
哈希表	超市存包柜：凭号码直接开柜，不用一个个找

核心机制

一、栈：为什么"受限"反而有用

        +-----+
        |  3  | < top（只能从这里进出）
        +-----+
        |  2  |
        +-----+
        |  1  |
        +-----+

它解决的问题：任何"最近的那个还没处理完，就来了新的"场景。

场景	为什么是栈
函数调用	调 A 里调 B，B 返回后必须回到 A 的那一行 > 用栈保存返回地址
括号匹配	遇到左括号压栈，右括号弹栈比对 > 最近没闭合的先闭合
表达式求值	后缀表达式计算、中缀转后缀
撤销操作	最近的操作最先撤销
DFS	深度优先就是"一条路走到黑，走不通退回上一步"
浏览器后退	最近访问的先退

函数调用栈是理解"递归"的关键：每次递归都在栈上压一帧（参数、局部变量、返回地址）。递归太深会栈溢出，因为栈空间有限（通常 1~8MB）。

二、队列：为什么"排队"需要专门的结构

     +---+---+---+---+
出 < | 1 | 2 | 3 |   | < 入
     +---+---+---+---+
      front        rear

用数组实现队列的坑：出队后 front 后移，前面空出来的位置浪费了。两种解法：

1. 循环队列：rear = (rear + 1) % capacity，把数组当环用。
2. 链表实现：天然没有空间浪费。

循环队列的判空/判满（高频细节）：

保留一个空位：
  空：front == rear
  满：(rear + 1) % capacity == front
  > 实际容量是 capacity - 1

或者用 size 变量记录元素个数（更直观，推荐）

变体：

• 双端队列（Deque）：两端都能进出。滑动窗口最大值就用它。
• 优先队列：出队顺序按优先级，不是按时间。实现是堆（见 03 篇）。
• 阻塞队列：空了消费者等，满了生产者等——线程池、消息队列的基础。

三、哈希表：三个必须搞清的问题

问题 1：哈希函数怎么设计

index = hash(key) % capacity

要求：

• 计算快（不能比遍历还慢）
• 分布均匀（减少冲突）
• 相同 key 必须得到相同值（否则查不到）

工程优化：当 capacity 是 2 的幂时，hash % capacity 等价于 hash & (capacity - 1)，位运算比取模快得多。这就是为什么 HashMap 的容量总是 2 的幂。

代价：2 的幂会让"低位相同的 hash"全部冲突，所以 HashMap 会把 hash 值再"扰动"一次（h ^ (h >>> 16)，把高 16 位异或到低 16 位），让高位也参与运算。

问题 2：冲突怎么解决

方案 A：链地址法（拉链）

bucket[0] > [k1,v1] > [k3,v3] > null
bucket[1] > null
bucket[2] > [k2,v2] > null

冲突的元素挂在同一个桶的链表上。HashMap 用这个。

方案 B：开放寻址法

冲突了就往后找下一个空位：
  index, index+1, index+2, ...

• 优点：不用指针，缓存友好，空间紧凑。
• 缺点：删除麻烦（不能直接置空，要打"墓碑"标记）；装太满会性能骤降。

ThreadLocalMap（Java）、Python 的 dict 用这个思路。

问题 3：扩容（rehash）

负载因子 = 元素数 / 桶数
HashMap 默认 0.75
  > 超过就扩容为 2 倍，所有元素重新计算下标

为什么要有负载因子：装得太满 > 冲突概率急剧上升 > 链表变长 > 查找退化。

为什么是 0.75：权衡空间和时间。太小浪费空间，太大冲突多。0.75 是数学上（泊松分布）算出来的经验值。

扩容为什么是 2 倍：因为容量是 2 的幂，扩容后每个元素要么留在原位，要么移动到"原位 + 旧容量"——不需要重新算哈希，只需看 hash 的一个新增位是 0 还是 1。这让 rehash 快很多。

Java 8 的优化：链表长度 ≥ 8 且桶数 ≥ 64 时，链表转成红黑树，查找从 O(n) 变成 O(log n)。防止极端情况下（恶意构造的 hash 冲突）性能崩塌。

为什么这么设计

反事实 1：如果没有栈，函数怎么返回

每个函数调用都要记录"返回到哪一行、局部变量是什么"。没有栈的话：

• 要么把这些存到堆里（要手动管理，极慢）
• 要么只支持一层调用（不可能）

栈的"后进先出"恰好匹配"函数调用的嵌套结构"——最后被调用的函数最先返回。这不是巧合，是结构匹配。

反事实 2：如果没有哈希表，查找要多久

1000 万个 key，用数组或链表查一个：O(n)，平均 500 万次比较。 哈希表：算一次哈希 + 访问一次数组，O(1)。

代价：需要额外 2~3 倍的空间（桶要留空位），且失去了顺序（无法范围查询、无法排序遍历）。这就是数据库索引不用哈希的原因。

反事实 3：如果负载因子是 1.0

桶全满，冲突概率极高。理论上链地址法还能工作，但平均链表长度会飙升，查找退化成 O(n)。

极端例子：如果哈希函数很差（所有 key 都映射到同一个桶），哈希表直接退化成链表。

面试怎么问

Q：栈和队列的区别？各用在什么场景？

区别在"进出顺序"：栈 LIFO，队列 FIFO。 场景要具体：栈用于函数调用、括号匹配、DFS、撤销；队列用于 BFS、任务调度、生产者消费者、消息队列。

Q：怎么用两个栈实现一个队列？

入队压入 in 栈；出队时如果 out 栈空，把 in 全部倒入 out，然后从 out 弹出。 关键点：每个元素最多被移动两次，所以摊销 O(1)。

Q：哈希表怎么解决冲突？

两种：链地址法（冲突挂链表，Java HashMap）和开放寻址法（往后找空位，ThreadLocalMap）。 加分：说清各自的优劣——拉链法删除简单但缓存不友好；开放寻址缓存友好但删除要打墓碑标记。

Q：HashMap 为什么容量是 2 的幂？

两个原因：① hash & (n-1) 比 hash % n 快；② 扩容时元素只需判断"留在原位还是移到原位+n"，不用重算哈希。

Q：HashMap 为什么线程不安全？

三个典型问题：① 并发 put 可能覆盖彼此的数据；② JDK 7 的头插法在并发扩容时可能形成环形链表，导致 get 死循环；③ size 计数不准。 解法：ConcurrentHashMap（JDK 8 用 CAS + synchronized 锁单个桶）。

追问链：

哈希表查找为什么 O(1)？
  > 怎么算下标？（hash % capacity）
    > 冲突了怎么办？（拉链 / 开放寻址）
      > 装太满会怎样？（冲突变多，退化成 O(n)）
        > 怎么避免？（负载因子 + 扩容）
          > 扩容为什么要重新分配？（容量变了，下标全变）
            > 为什么容量取 2 的幂？（位运算 + 扩容只需判断一位）

和其他知识的连接

• < 来自 复杂度与数组、链表：栈/队列/哈希表都可以用数组或链表实现，选型依据同 01 篇
• > 影响 树与堆：优先队列的实现是堆；HashMap 冲突严重时转红黑树
• > 影响 图与并查集：BFS 用队列，DFS 用栈（或递归）
• > 影响 索引与 B+ 树：哈希索引只支持等值查询，就是因为哈希打散了顺序
• > 影响 调度与并发同步：CPU 分给谁，共享数据谁先动：阻塞队列是生产者-消费者模型的载体
• > 影响 工程实践：Redis 的字典（渐进式 rehash）、LRU（哈希 + 双向链表）、消息队列

自测 3 问

Q1：为什么"两个栈实现队列"是摊销 O(1)？

点开看答案

因为每个元素最多被移动两次：一次是从 in 倒入 out，一次是被弹出。

考虑 n 次操作（n 次入队 + n 次出队）：

• n 次入队：每次 O(1)，共 O(n)
• 出队：每次 out 空了才倒一次，总共倒 n 个元素，共 O(n)
• 总代价 O(n)，平均到 2n 次操作 > 摊销 O(1)

注意单次最坏情况仍是 O(n)（那一次要倒整个栈），但摊销是 O(1)。这和 ArrayList 扩容是同一类分析。

Q2：哈希表的 O(1) 是最坏情况还是平均情况？

点开看答案

平均情况。

最坏情况是 O(n)：所有 key 都冲突到同一个桶，退化成链表。

现实中能否发生：

• 哈希函数差 > 容易发生。
• 恶意攻击（哈希碰撞攻击）> 攻击者构造大量同 hash 的参数，让服务器 CPU 打满。这是真实的 DoS 手法（2011 年多个语言受影响）。

所以 Java 8 加了"链表转红黑树"（≥8 个转），把最坏情况从 O(n) 降到 O(log n)。

面试标准答法："平均 O(1)，最坏 O(n)；工程上通过好的哈希函数 + 扩容 + 红黑树把最坏情况兜住"。

Q3：为什么循环队列要"牺牲一个位置"？

点开看答案

因为如果 front == rear 既可能表示"空"也可能表示"满"，无法区分。

两种解法：

1. 牺牲一个位置：满的条件是 (rear+1) % cap == front，此时实际只能存 cap-1 个元素。
2. 加一个 size 变量：size == 0 是空，size == cap 是满。更直观，也不浪费空间，推荐。

第三种（不推荐）：用标志位记录"最后一次操作是入队还是出队"，靠它区分空和满。逻辑绕，容易错。

类比失效处 / 易错点

• "一摞盘子"会让人以为栈只能存少量。栈的容量取决于实现，可以动态扩容（但函数调用栈通常是固定大小的，所以会溢出）。
• "优先队列"不是队列。它不保证 FIFO，只保证"优先级最高的先出"，底层是堆，不是链表。
• 哈希表的"O(1)"忽略了哈希函数的开销。如果 key 是长字符串，算哈希本身是 O(长度)——所以缓存哈希值（Java 的 String 就缓存了 hash）。
• HashMap 的遍历顺序不是插入顺序。要插入顺序用 LinkedHashMap，要排序用 TreeMap。
• 开放寻址法删除不能直接置空。置空会切断后续元素的探测链，必须用"墓碑"标记。

✅ 验收清单

• 能说出栈的 4 个典型应用场景，并解释"为什么嵌套结构天然适合栈"
• 能写出循环队列的判空/判满条件，并解释为什么要"牺牲一个位置"
• 能说清哈希表冲突的两种解法，各举一个真实实现（HashMap / ThreadLocalMap）
• 能解释 HashMap 容量为什么是 2 的幂（要说出两个理由）
• 能解释负载因子 0.75 的意义，以及扩容为什么是 2 倍
• 能用"摊销分析"讲清"两个栈实现队列"的复杂度
• 能说出哈希表 O(1) 是平均而非最坏，以及 Java 8 怎么兜住最坏情况
• 合上书，用自己的话讲 3 分钟，中途不卡壳