Java 搜索型数据结构全解：二叉搜索树、Map/Set 体系与哈希表
在 Java 中，搜索型数据结构主要包括二叉搜索树（BST）、Map/Set 体系以及哈希表（Hash Table）。它们各自适用于不同的场景，具有不同的性能特征和实现方式。以下是全面解析：
一、二叉搜索树（Binary Search Tree, BST）
1. 定义与性质
- 若左子树非空，则左子树上所有节点的值小于根节点；
- 若右子树非空，则右子树上所有节点的值大于根节点；
- 左右子树本身也是二叉搜索树。
中序遍历 BST 得到的是升序序列。
2. 基本操作
- 查找：从根开始，比较目标值与当前节点，决定向左或向右递归。
- 插入：找到合适位置（叶子节点），插入新节点。
- 删除（较复杂）：
- 删除叶子节点：直接移除；
- 删除只有一个子节点的节点：用子节点替代；
- 删除有两个子节点的节点：找中序后继（右子树最小值）或前驱（左子树最大值）替换。
3. 性能分析
- 最好情况（平衡树）：高度为 $O(\log n)$，操作时间复杂度为 $O(\log n)$；
- 最坏情况（退化为链表）：高度为 $O(n)$，操作退化为 $O(n)$。
Java 中
TreeMap和TreeSet的底层是红黑树（一种自平衡 BST），保证最坏情况仍为 $O(\log n)$。
二、Map 与 Set 体系
Java 集合框架中，Map和Set是专门用于高效查找的接口。
1. Map 接口
- 存储键值对（Key-Value），键不可重复。
- 常见实现：
HashMap：基于哈希表，无序，允许null键/值；TreeMap：基于红黑树，按键排序，不允许null键。
2. Set 接口
- 存储不重复元素，可视为
Map的键集合。 - 常见实现：
HashSet：基于HashMap，无序；TreeSet：基于TreeMap，元素自然排序或自定义排序。
3. 使用场景
| 数据结构 | 底层实现 | 是否有序 | 是否允许 null | 时间复杂度（平均） |
|---|---|---|---|---|
HashMap | 哈希表 | 否 | 是 | $O(1)$ |
TreeMap | 红黑树 | 是 | 否 | $O(\log n)$ |
HashSet | 哈希表 | 否 | 是 | $O(1)$ |
TreeSet | 红黑树 | 是 | 否 | $O(\log n)$ |
三、哈希表（Hash Table）
1. 核心思想
- 通过哈希函数将键映射到数组索引，实现O(1) 平均查找。
2. 哈希冲突
- 定义：不同键映射到同一索引。
- 解决方法：
- 开放地址法（闭散列）：线性探测、二次探测等；
- 链地址法（开散列/哈希桶）：每个桶是一个链表（Java 8+ 优化为红黑树，当链表长度 ≥ 8）。
3. 负载因子（Load Factor）
- 定义：$\text{负载因子} = \frac{\text{元素数量}}{\text{桶数量}}$；
- Java 默认负载因子为0.75，超过则扩容（rehash）。
4. Java 中的实现
HashMap内部使用数组 + 链表/红黑树；- 初始容量为 16，扩容时翻倍。
四、总结对比
| 特性 | 二叉搜索树 | 哈希表 |
|---|---|---|
| 有序性 | 支持（中序遍历） | 不支持（除非 LinkedHashMap） |
| 最坏时间复杂度 | $O(n)$（未平衡） | $O(n)$（极端哈希冲突） |
| 平均时间复杂度 | $O(\log n)$（平衡） | $O(1)$ |
| 空间开销 | 较低（仅指针） | 较高（需预留空间防冲突） |
| 适用场景 | 需要有序、范围查询 | 快速查找、插入、删除 |
实际开发中：
- 需要快速查找且无需顺序→ 用
HashMap/HashSet；- 需要有序或范围操作（如
floorKey,subSet）→ 用TreeMap/TreeSet。
希望这份全解能帮助你深入理解 Java 中的搜索型数据结构！