算法与数据结构（二）：哈希表、树与堆
导语：本篇覆盖数据结构面试的三大主战场——哈希表（冲突解决与布隆过滤器）、树（遍历、BST、AVL/红黑树/B+树、跳表）与堆（建堆、堆排、Top K），并补齐 Trie 与并查集。树与堆的关键实现均给出 Java 代码。共 16 题。
一、哈希表
1. 哈希表的原理是什么？哈希冲突如何解决？
答： 哈希表通过哈希函数把 key 映射到数组下标，实现平均 O(1) 的增删查。但不同 key 可能映射到同一位置，即哈希冲突（鸽巢原理，几乎不可避免），主流解决方案有两类：
| 方案 | 原理 | 优点 | 缺点 | 代表实现 |
|---|---|---|---|---|
| 链地址法（拉链法） | 每个桶挂一条链表（或红黑树） | 简单、可容纳任意多冲突、删除方便 | 链表节点有指针开销、缓存不友好 | HashMap、Redis dict |
| 开放寻址法 | 冲突时按规则探测下一个空槽 | 无指针开销、缓存友好 | 删除需"墓碑标记"、易聚集、装填率不能太高 | ThreadLocalMap（线性探测） |
开放寻址的三种探测方式：
- 线性探测：
(h + 1) % n、(h + 2) % n…… 简单但会产生一次聚集（连续占用区越来越长）； - 二次探测：
h ± 1², ± 2², ± 3²…… 缓解一次聚集，但可能探测不到部分槽位； - 双重哈希：用第二个哈希函数决定步长，
(h₁ + i × h₂) % n，分布最均匀。
HashMap的细节：JDK 8 中，链表长度 ≥ 8 且数组容量 ≥ 64 时转为红黑树（查询从O(n)降到O(log n)），节点数降到 6 时退回链表；8 与 6 之间的间隔是为了避免频繁转换。
2. 为什么 HashMap 容量是 2 的幂？负载因子为什么是 0.75？
答：
容量取 2 的幂的原因：定位桶下标用 (n - 1) & hash 代替 hash % n。只有当 n 是 2 的幂时，n - 1 的二进制才全是 1，此时 & 运算才等价于取模且更快（位运算 vs 除法）。此外扩容为 2 倍后，元素要么留在原位置、要么移到「原位置 + oldCap」，无需重算哈希。
负载因子 0.75 的原因：这是时间与空间的折中——
- 因子过小（如 0.5）：冲突少、查询快，但数组空闲多、空间浪费且扩容频繁；
- 因子过大（如 1.0）：空间利用率高，但冲突剧增、链表/树变长、查询变慢；
- 0.75 在泊松分布下使冲突概率与空间利用率达到较好平衡（且
容量 × 0.75计算方便）。
可调优：追求时间可调小（用更多内存换更少冲突），追求空间可调大（慎用，冲突会显著上升）。
3. 什么是布隆过滤器？为什么它不能删除元素？
答： 布隆过滤器（Bloom Filter） = 一个位数组 + k 个独立的哈希函数，用于判断元素"可能存在"或"一定不存在"，空间效率极高。
流程：
- 添加：用 k 个哈希函数算出 k 个下标，把位数组对应位置置 1；
- 查询：同样算 k 个下标，只要有一位是 0 → 一定不存在；全为 1 → 可能存在（也可能是别的元素碰巧把这些位置置 1 了）。
核心特性：
| 判断结果 | 是否可靠 |
|---|---|
| 说"不存在" | 100% 准确（无假阴性） |
| 说"存在" | 可能误判（有假阳性，但与"不存在"的误判不同） |
为什么不能删除：一个位可能被多个元素共享地置为 1。若把某元素对应的位清零，会连带影响其他元素的判断，产生假阴性——这是不可接受的。
解决删除问题：使用计数布隆过滤器（每个位改成计数器，添加 +1、删除 -1），代价是空间开销大增。
应用：缓存穿透防护（先查布隆过滤器，不存在直接返回）、Redis 大 key 判重、爬虫 URL 去重、HBase/LevelDB 的 LSM-Tree 查询加速。
二、二叉树
4. 二叉树有哪些常见类型？
答：
| 类型 | 定义 | 特点 |
|---|---|---|
| 满二叉树 | 每层都是满的，所有叶节点同层 | 节点数 2^h - 1 |
| 完全二叉树 | 除最后一层外都满，且最后一层节点靠左连续排列 | 可用数组存储，是堆的前提 |
| 二叉搜索树（BST） | 左子树全部 < 根 < 右子树全部 | 中序遍历有序，但可能退化成链表 |
| 平衡二叉树（AVL） | BST + 任意节点左右子树高度差 ≤ 1 | 查询最优，但插删旋转频繁 |
| 红黑树 | BST + 颜色约束实现的弱平衡 | 插删旋转少，工程上更常用 |
| 堆 | 完全二叉树 + 堆序性 | 最值 O(1)，插入删除 O(log n) |
关键前提：讨论"平衡二叉树"时，先要是二叉搜索树——只有 BST 才需要平衡来保证查询效率。这一点常被忽略。
5. 二叉树的四种遍历如何实现？
答： 前/中/后序属于 DFS（靠递归或栈），层序属于 BFS（靠队列）。
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}1）前序 / 中序 / 后序（递归，最直观）——区别只在访问根的位置：
// 前序：根 → 左 → 右
public void preorder(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
// 中序：左 → 根 → 右（BST 中序遍历得到升序序列）
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) return;
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
// 后序：左 → 右 → 根（适合自底向上汇总，如求高度、路径和）
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) return;
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}2）中序（迭代，用栈模拟递归）——面试常考"不用递归怎么写"：
public List<Integer> inorderIterative(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) { // 一路向左，沿途压栈
stack.push(cur);
cur = cur.left;
}
cur = stack.pop(); // 弹出即"左子树处理完"，访问根
res.add(cur.val);
cur = cur.right; // 转向右子树
}
return res;
}3）层序（BFS + 队列，按层分组）：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(); // 关键：先记录本层节点数，实现按层切分
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
res.add(level);
}
return res;
}进阶：Morris 遍历可用
O(1)空间完成中序遍历（利用叶节点的空右指针建"线索"），但会临时破坏树结构，面试中作为加分项即可。复杂度：时间均为
O(n)；递归空间为O(h)（h为树高，最坏退化为O(n)）；层序空间为O(w)（w为最大层宽）。
6. 如何由前序 + 中序遍历序列构造二叉树？
答： 核心是利用前序确定根、利用中序划分左右子树：
- 前序的第一个元素是根；
- 在中序中找到该根的位置，左边是左子树、右边是右子树；
- 用哈希表预存「值 → 中序下标」，把查找从
O(n)降到O(1)，整体O(n)。
private Map<Integer, Integer> indexMap; // 中序序列里：值 -> 下标
public TreeNode buildTree(int[] preorder, int[] inorder) {
indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) indexMap.put(inorder[i], i);
return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preL, int preR, int inL, int inR) {
if (preL > preR) return null;
int rootVal = preorder[preL]; // 前序首个 = 根
TreeNode root = new TreeNode(rootVal);
int inRoot = indexMap.get(rootVal); // 根在中序中的位置
int leftSize = inRoot - inL; // 左子树节点数
root.left = build(preorder, preL + 1, preL + leftSize, inL, inRoot - 1);
root.right = build(preorder, preL + leftSize + 1, preR, inRoot + 1, inR);
return root;
}追问：后序 + 中序也能唯一确定一棵树（后序的最后一个是根）。但前序 + 后序无法唯一确定——因为无法区分"只有左子树"和"只有右子树"这两种情况，解不唯一。
三、二叉搜索树与平衡树
7. 什么是二叉搜索树（BST）？为什么最坏会退化为 O(n)？
答： BST 满足：任意节点，左子树所有值 < 该节点值 < 右子树所有值。
- 中序遍历得到升序序列——这是 BST 最重要的性质，很多题（验证 BST、第 K 小元素）都围绕它；
- 平均查询/插入/删除
O(log n)（树高为log n）。
退化的原因：BST 的形态完全取决于插入顺序。若按有序序列依次插入（如 1,2,3,4,5），BST 会退化成一条链表，树高变成 n，所有操作退化为 O(n)。
解决方案：引入自平衡机制，在插删时通过旋转维持树高在 O(log n)——
- AVL 树：严格平衡（|左右子树高度差| ≤ 1），查询最优；
- 红黑树：弱平衡（最长路径 ≤ 2 × 最短路径），插删旋转次数少。
判断 BST 的常见错误写法：只比较
root.left.val < root.val < root.right.val——这只能保证局部有序，无法保证全局。正确做法是传递上下界（(low, high)区间），或用中序遍历验证严格递增。
8. AVL 树与红黑树的区别？
答：
| 维度 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡强度 | 严格平衡（高度差 ≤ 1） | 弱平衡（最长路径 ≤ 2×最短路径） |
| 树高 | 更矮（约 1.44 log n） | 略高（≤ 2 log n） |
| 查询性能 | 更优 | 稍逊 |
| 插入/删除性能 | 较差（可能需多次旋转） | 更优（插入 ≤ 2 次旋转 + 变色） |
| 适用场景 | 读远多于写 | 读写都频繁（通用） |
| 典型应用 | 教学、内存索引 | TreeMap/TreeSet、HashMap 树化、epoll 的 fd 集合、Linux 进程调度 CFS |
一句话选型：读多写少用 AVL，读写均衡用红黑树。工程实践几乎都选红黑树——因为真实系统中写操作并不少，AVL 频繁旋转的代价抵消了它查询上的优势。
9. 红黑树的五大性质是什么？
答： 红黑树在 BST 基础上追加颜色约束：
- 每个节点非红即黑；
- 根节点是黑色；
- 所有叶子节点（NIL 哨兵）都是黑色；
- 红色节点的两个子节点必须是黑色（即不存在连续的红色节点）；
- 从任一节点到其所有后代 NIL 节点的路径上，黑色节点数量相同（黑高一致）。
这些约束如何保证 O(log n)：
- 由性质 4，从根到叶的最长路径上，红黑交替出现，而黑节点数固定（性质 5）；
- 因此最长路径 ≤ 2 × 最短路径，树高被限制在
O(log n)内； - 插入/删除通过变色 + 旋转（左旋/右旋）恢复被破坏的性质，插入最多 2 次旋转即可修复。
记忆口诀："根黑、叶黑、红不连、黑高同"。
10. B 树与 B+ 树的区别？为什么 MySQL 索引用 B+ 树？
答： 二者都是多路平衡查找树，为磁盘存储而设计（降低树高，减少磁盘 I/O 次数）。
| 维度 | B 树 | B+ 树 |
|---|---|---|
| 数据存放位置 | 所有节点（含非叶节点）都存数据 | 只有叶子节点存数据，非叶节点仅存索引 |
| 非叶节点容量 | 被数据占用，能放的键更少 | 只存键，单节点能容纳更多键 → 树更矮 |
| 查询稳定性 | 命中位置不同，耗时不同（可能在根就返回） | 每次都走到叶子，查询耗时稳定 |
| 范围查询 | 需反复中序遍历回溯，较差 | 叶子节点用双向链表串起，范围扫描极快 |
| 典型应用 | 文件系统索引（如某些 FS 的元数据） | MySQL InnoDB 索引、数据库聚集索引 |
为什么 MySQL 选 B+ 树：
- 树更矮：非叶节点不存数据，单节点能放更多键，3~4 层即可支撑千万级数据，磁盘 I/O 次数少；
- 范围查询高效：叶子节点的链表让
BETWEEN、ORDER BY、>这类范围扫描顺序读取，无需回溯上层的树； - 查询性能稳定：所有查询都走到叶子，耗时一致，便于估算。
面试加分点（变体差异）：经典教材（CLRS）中 B 树是「n 个键对应 n+1 个子指针」；而 MySQL InnoDB 的实现是「n 个键对应 n 个子指针」（每个槽位既存键又存子页号）。面试时说明"是哪一种变体"即可，不必纠结唯一答案。
11. 什么是跳表？Redis 为什么用跳表而不是红黑树？
答： 跳表（Skip List） 是在有序链表之上抽取多层索引的结构，查找时从最高层开始、逐层下降，实现类似二分的跳跃：
- 平均查找/插入/删除均为
O(log n)，空间O(n)； - 实现比对平衡树简单得多（不需要旋转，只靠随机层高 + 指针维护），因此更易正确实现与调试；
- 缺点：依赖随机化，最坏情况仍是
O(n)（概率极低）。
Redis 用跳表实现 ZSet 的原因：
- 范围查询友好：
ZRANGE、ZRANGEBYSCORE这类有序范围操作，跳表只需在底层链表顺序前进，天然高效——这点与 B+ 树叶子链表同理； - 实现简单、易维护：相比红黑树的旋转与变色，跳表的插入删除逻辑直观，代码量小、bug 少（Redis 作者明确提到这点）；
- 并发/内存可控：虽然 Redis 主线程单线程执行，但跳表的结构也更利于实现"随机层高"来平衡，而不用维护平衡因子；
- 性能相当：两者都是
O(log n)，跳表在范围查询上还略有优势。
注意：Redis 的 ZSet 是
跳表 + 哈希表的组合——哈希表负责O(1)按成员查分数，跳表负责按分数排序与范围查询。
四、堆
12. 什么是堆？建堆为什么是 O(n)（而不是 O(n log n)）？
答： 堆是满足堆序性的完全二叉树：
- 大顶堆：每个节点 ≥ 其子节点（堆顶是最大值）；
- 小顶堆：每个节点 ≤ 其子节点（堆顶是最小值）。
数组存储的下标关系（利用完全二叉树的"靠左连续"特性，无需指针）：
左孩子 = 2i + 1
右孩子 = 2i + 2
父节点 = (i - 1) / 2建堆的实现——从最后一个非叶节点开始，逐个下沉：
private void swap(int[] heap, int i, int j) {
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
// 下沉：把 i 处的元素调整到合适位置，维持大顶堆性质
private void siftDown(int[] heap, int i, int size) {
while (true) {
int left = 2 * i + 1, right = 2 * i + 2, largest = i;
if (left < size && heap[left] > heap[largest]) largest = left;
if (right < size && heap[right] > heap[largest]) largest = right;
if (largest == i) break; // 已满足堆序性，结束
swap(heap, i, largest);
i = largest; // 继续向下调整
}
}
// 建堆：从最后一个非叶节点 (n/2 - 1) 开始向前逐个下沉 —— O(n)
public void buildHeap(int[] heap) {
for (int i = heap.length / 2 - 1; i >= 0; i--) {
siftDown(heap, i, heap.length);
}
}为什么建堆是 O(n) 而不是 O(n log n)：
- 单次
siftDown的代价取决于节点的高度，而非log n； - 完全二叉树中高度为 h 的节点约有
n / 2^(h+1)个——即绝大多数节点在底层、高度很小； - 总代价 =
Σ (h × n / 2^(h+1))，该级数收敛到常数，因此是O(n)。
直观理解：底层节点几乎不用下沉（本身就是叶子），只有根节点才可能下沉
log n层，但根只有 1 个。若反过来"从根开始往上调整"（逐个插入式建堆），每次代价是O(log n)，就会得到O(n log n)——这两种写法的差异正是考点。
13. 堆排序如何实现？
答： 三步：建大顶堆 → 交换堆顶与末尾 → 缩小堆范围并重新下沉。
public void heapSort(int[] nums) {
buildHeap(nums); // 1. 建大顶堆，O(n)
for (int end = nums.length - 1; end > 0; end--) {
swap(nums, 0, end); // 2. 堆顶（当前最大值）换到已排序区前端
siftDown(nums, 0, end); // 3. 剩余 [0, end) 重新调整为大顶堆
}
}性能对比：
| 维度 | 堆排序 | 快速排序 | 归并排序 |
|---|---|---|---|
| 平均/最坏时间 | O(n log n) / O(n log n) | O(n log n) / O(n²) | O(n log n) / O(n log n) |
| 额外空间 | O(1) | O(log n)（递归栈） | O(n) |
| 稳定性 | 不稳定 | 不稳定 | 稳定 |
| 特点 | 最坏也是 n log n 且空间 O(1) | 常数最小、实际最快 | 稳定、适合外部排序与链表 |
为什么工程上仍偏爱快排：堆排序的"跳跃式访问"（
i、2i+1、2i+2）对 CPU 缓存极不友好，实际常数因子远大于快排；因此Arrays.sort()对基本类型用的是双轴快排，对对象数组用归并（TimSort）以保证稳定性。
14. 如何用堆求 Top K 与数据流中位数？
答：
1）Top K / 第 K 大元素——维护大小为 K 的小顶堆
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); // Java 默认小顶堆
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) minHeap.poll(); // 堆内始终只保留最大的 K 个
}
return minHeap.peek(); // 堆顶就是第 K 大
}| 方案 | 时间 | 空间 | 适用 |
|---|---|---|---|
| 全排序后取第 K 个 | O(n log n) | O(log n) | 数据量小 |
| 大小为 K 的小顶堆 | O(n log k) | O(k) | 数据量大 / 流式数据（n 很大、k 很小） |
| 快速选择（QuickSelect） | 平均 O(n)，最坏 O(n²) | O(1) | 数据可全量放入内存、只需一次答案 |
2）数据流中位数——大顶堆 + 小顶堆（各存一半）
class MedianFinder {
// 大顶堆：存较小的一半，堆顶是这一半的最大值
private final PriorityQueue<Integer> small = new PriorityQueue<>((a, b) -> b - a);
// 小顶堆：存较大的一半，堆顶是这一半的最小值
private final PriorityQueue<Integer> large = new PriorityQueue<>();
public void addNum(int num) {
if (small.isEmpty() || num <= small.peek()) small.offer(num);
else large.offer(num);
// 平衡两堆：大小差不超过 1
if (small.size() > large.size() + 1) large.offer(small.poll());
else if (large.size() > small.size()) small.offer(large.poll());
}
public double findMedian() {
if (small.size() > large.size()) return small.peek(); // 奇数个
return (small.peek() + large.peek()) / 2.0; // 偶数个取平均
}
}关键点：
small用(a, b) -> b - a构造为大顶堆（Java 的PriorityQueue默认是小顶堆）；两堆维持"small元素数 ≥large且相差不超过 1"，则中位数必然出现在两个堆顶。
五、其他常用结构
15. 什么是 Trie（前缀树）？如何实现？
答： Trie（字典树/前缀树） 是一棵多叉树，用边的字符表示路径、节点表示某个前缀，根节点不含字符。核心优势是按前缀查找只需 O(词长)，与词典中词的数量无关。
应用：搜索框自动补全、拼写检查、IP 路由最长前缀匹配、敏感词过滤、词频统计。
class Trie {
private static class Node {
Node[] children = new Node[26]; // 假定只含小写字母；字符集大时可换 HashMap
boolean isEnd; // 是否是某个单词的结尾
}
private final Node root = new Node();
public void insert(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (cur.children[idx] == null) cur.children[idx] = new Node();
cur = cur.children[idx];
}
cur.isEnd = true;
}
public boolean search(String word) { // 精确匹配
Node node = find(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) { // 前缀匹配
return find(prefix) != null;
}
private Node find(String s) {
Node cur = root;
for (char c : s.toCharArray()) {
int idx = c - 'a';
if (cur.children[idx] == null) return null;
cur = cur.children[idx];
}
return cur;
}
}
isEnd标记必不可少：没有它，insert("app")后就无法区分"插入了app"与"只插入了apple而app只是其前缀"。这也是search与startsWith的唯一区别。空间优化：把
Node[26]换成HashMap<Character, Node>可节省稀疏节点的空间，代价是常数变大。
16. 什么是并查集？如何实现路径压缩与按秩合并？
答： 并查集（Union-Find / Disjoint Set） 用于维护不相交集合的合并与查询，支持两个操作：
find(x)：查x属于哪个集合（返回代表元/根节点）；union(x, y)：把两个集合合并。
两个关键优化：
| 优化 | 作用 |
|---|---|
| 路径压缩 | find 时把沿途节点直接挂到根上，让树变"扁平"，后续查询更快 |
| 按秩/按大小合并 | 合并时把矮树挂到高树下（或小集合并入大集合），避免树退化成链 |
两者结合后，单次操作的均摊复杂度为 O(α(n))（α 是反阿克曼函数，增长极慢，实际可视为 O(1)）。
class UnionFind {
private final int[] parent;
private final int[] rank; // 秩：近似树高
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i; // 初始化：各自为独立集合
}
// 查找根 + 路径压缩（递归写法会把沿途节点直接挂到根上）
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false; // 已在同一集合
if (rank[rx] < rank[ry]) parent[rx] = ry; // 矮树挂到高树下
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; } // 等高时任选，并增高秩
return true;
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}典型题目：
省份数量（图连通分量计数）、冗余连接（在图上找多余的边）、朋友圈、被围绕的区域、等式方程的可满足性、Kruskal 最小生成树（见第五篇）。一句话辨别：题目出现「连通性」「是否属于同一组」「合并集合」就该想到并查集。