第3章：搜索（Searching）
一、导读
1.1 本章学习目标
第3章介绍符号表和散列表，这是实现高效搜索的核心数据结构。搜索是计算机最基本的操作之一。本章核心目标：
- 理解符号表的抽象：键值对的基本操作接口
- 掌握二叉搜索树（BST）：插入、查找、删除的实现
- 了解平衡搜索树：为什么需要红黑树？
- 掌握散列表：哈希函数和冲突解决策略
- 学会分析搜索算法的性能：平均情况和最坏情况
- 了解Java的TreeMap和HashMap实现
1.2 为什么本章如此重要
搜索是几乎所有应用的核心功能——数据库查询、文件系统、缓存、编译器符号表，都需要高效的搜索数据结构。二叉搜索树和散列表是两种最重要的搜索结构，理解它们的原理和性能特征，是设计高效系统的基础。
1.3 核心问题引导
二叉搜索树在什么情况下会退化为链表？如何避免？
红黑树如何保证O(log n)的最坏情况？旋转操作的作用是什么？
散列表的负载因子是什么？为什么需要在0.5-0.75之间？
链地址法和线性探测法各有什么优缺点？
好的哈希函数应该满足什么条件？
为什么Java的HashMap使用链地址法而不是线性探测？
二、核心概念详解
3.1 符号表
符号表是一种存储键值对的数据结构，支持以下基本操作：
put(key, value)：插入或更新键值对get(key)：获取键对应的值delete(key)：删除键值对contains(key)：检查键是否存在
java
public interface SymbolTable<Key, Value> {
void put(Key key, Value val);
Value get(Key key);
void delete(Key key);
boolean contains(Key key);
boolean isEmpty();
int size();
Iterable<Key> keys();
}3.2 二叉搜索树（BST）
BST的性质：对于每个节点，左子树所有键小于它，右子树所有键大于它。
java
public class BST<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
private Key key;
private Value val;
private Node left, right;
private int size;
public Node(Key key, Value val, int size) {
this.key = key;
this.val = val;
this.size = size;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null) return 0;
return x.size;
}
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x.val;
}
public void put(Key key, Value val) {
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);
else if (cmp > 0) x.right = put(x.right, key, val);
else x.val = val;
x.size = 1 + size(x.left) + size(x.right);
return x;
}
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) return x;
return min(x.left);
}
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node x) {
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.size = 1 + size(x.left) + size(x.right);
return x;
}
public void delete(Key key) {
root = delete(root, key);
}
private Node delete(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);
else if (cmp > 0) x.right = delete(x.right, key);
else {
if (x.right == null) return x.left;
if (x.left == null) return x.right;
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.size = 1 + size(x.left) + size(x.right);
return x;
}
}分析：
- 平均情况（随机插入）：查找、插入、删除都是O(log n)
- 最坏情况（有序插入）：退化为链表，O(n)
- 空间：O(n)
3.3 平衡搜索树
为了避免BST退化，需要保持树的平衡。红黑树是最常用的平衡搜索树：
红黑树的性质：
每个节点要么是红色，要么是黑色
根节点是黑色
每个叶子节点（NIL）是黑色
如果一个节点是红色，则它的两个子节点都是黑色
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
这些性质保证了树的高度不超过2log(n+1)，从而保证O(log n)的操作时间。
Java的TreeMap就是基于红黑树实现的。
3.4 散列表
散列表通过哈希函数将键映射到数组位置，实现O(1)的平均查找时间。
3.4.1 哈希函数
好的哈希函数应该：
- 均匀分布：将键均匀地分散到各个位置
- 确定性：相同的键总是映射到相同的位置
- 高效：计算速度快
java
// Java的hashCode()
// 整数
int hash = key.hashCode();
hash = hash ^ (hash >>> 16); // 混合高位和低位
int index = (hash & 0x7fffffff) % M;
// 字符串的hashCode
// "abc" -> 'a' * 31^2 + 'b' * 31 + 'c'3.4.2 链地址法
每个数组位置维护一个链表，冲突的键值对放在同一个链表中：
java
public class SeparateChainingHashST<Key, Value> {
private int M = 97; // 数组大小（素数）
private Node[] st = new Node[M];
private static class Node {
private Object key;
private Object val;
private Node next;
public Node(Object key, Object val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
public Value get(Key key) {
int i = hash(key);
for (Node x = st[i]; x != null; x = x.next) {
if (key.equals(x.key))
return (Value) x.val;
}
return null;
}
public void put(Key key, Value val) {
int i = hash(key);
for (Node x = st[i]; x != null; x = x.next) {
if (key.equals(x.key)) {
x.val = val;
return;
}
}
st[i] = new Node(key, val, st[i]);
}
}3.4.3 线性探测法
冲突时寻找下一个空位置：
java
public class LinearProbingHashST<Key, Value> {
private int M = 30001;
private Key[] keys = (Key[]) new Object[M];
private Value[] vals = (Value[]) new Object[M];
private int n = 0; // 元素个数
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
public void put(Key key, Value val) {
if (n >= M / 2) resize(2 * M); // 负载因子0.5时扩容
int i = hash(key);
for (; keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
n++;
}
public Value get(Key key) {
for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (key.equals(keys[i]))
return vals[i];
}
return null;
}
public void delete(Key key) {
int i = hash(key);
while (keys[i] != null) {
if (key.equals(keys[i])) {
keys[i] = null;
vals[i] = null;
n--;
// 重新插入聚簇中的后续元素
i = (i + 1) % M;
while (keys[i] != null) {
Key k = (Key) keys[i];
Value v = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(k, v);
i = (i + 1) % M;
}
if (n > 0 && n <= M / 8) resize(M / 2);
return;
}
i = (i + 1) % M;
}
}
private void resize(int capacity) {
LinearProbingHashST<Key, Value> temp =
new LinearProbingHashST<>();
temp.M = capacity;
temp.keys = (Key[]) new Object[capacity];
temp.vals = (Value[]) new Object[capacity];
for (int i = 0; i < M; i++) {
if (keys[i] != null)
temp.put((Key) keys[i], (Value) vals[i]);
}
this.M = temp.M;
this.keys = temp.keys;
this.vals = temp.vals;
}
}分析：
- 平均情况：查找、插入、删除都是O(1)（负载因子合理时）
- 最坏情况：所有键哈希到同一位置，O(n)
- 空间：O(M)，M是数组大小
三、实战案例
3.1 词频统计
java
public class FrequencyCounter {
public static void main(String[] args) {
BST<String, Integer> st = new BST<>();
// 读取文本并统计词频
String text = "the quick brown fox jumps over the lazy dog the fox";
String[] words = text.split("\\s+");
for (String word : words) {
int freq = st.get(word) != null ? st.get(word) : 0;
st.put(word, freq + 1);
}
// 找出出现最多的词
String maxWord = "";
int maxFreq = 0;
for (String word : st.keys()) {
int freq = st.get(word);
if (freq > maxFreq) {
maxFreq = freq;
maxWord = word;
}
}
System.out.println(maxWord + ": " + maxFreq);
}
}3.2 缓存实现（LRU Cache）
java
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true); // accessOrder=true
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // 访问1，使其变为最近使用
cache.put(4, "four"); // 淘汰最久未使用的2
System.out.println(cache); // {3=three, 1=one, 4=four}
}
}四、本章小结
第3章介绍了搜索的核心数据结构：
符号表：键值对的抽象，定义基本操作接口。
BST：平均O(log n)，但最坏O(n)。有序插入会退化。
平衡搜索树：红黑树保证O(log n)最坏情况。Java TreeMap的实现基础。
散列表：平均O(1)，通过哈希函数直接定位。链地址法和线性探测法是两种冲突解决策略。
选择依据：需要有序遍历用BST/红黑树，追求平均性能用散列表。
五、思考与练习
思考题
为什么BST的delete操作比put和get复杂得多？
红黑树的旋转操作如何恢复平衡性质？
散列表的负载因子为什么不能太大也不能太小？
链地址法和线性探测法在缓存友好性上有什么区别？
Java的HashMap为什么使用链地址法+红黑树（Java 8+）？
编程练习
实现BST的中序遍历，验证输出是否有序。
实现一个简单的哈希函数，并测试其在不同输入下的分布情况。
使用散列表实现一个拼写检查器。