一、TreeMap 与 TreeSet
TreeMap 和 TreeSet 是 Java 集合框架中具有有序性的集合，它们的底层都依赖于红黑树（一种自平衡的二叉搜索树），能够保证元素（或键）的有序排列。本文先从二叉搜索树入手，再讲解 TreeMap 与 TreeSet 的实际使用。
二叉搜索树
二叉搜索树（BST）是红黑树的基础，它满足以下核心特性：
- 左子树中所有结点的值都小于根结点的值
- 右子树中所有结点的值都大于根结点的值
- 左右子树也分别是二叉搜索树
下面通过代码实现二叉搜索树的查找、插入、删除三大核心操作：
public class BinarySearchTree {
// 定义二叉搜索树的结点结构
static class TreeNode {
public int val; // 结点值
public TreeNode left; // 左孩子引用
public TreeNode right; // 右孩子引用
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode root; // 二叉搜索树的根结点
/**
* 查找二叉搜索树中是否存在指定值
* @param val 待查找的值
* @return 存在返回 true，不存在返回 false
*/
public boolean search(int val) {
TreeNode cur = root;
// 若根结点为空，直接返回 false
if (root == null) {
return false;
}
// 循环遍历二叉搜索树
while (cur != null) {
// 修正：原代码误写为 root.val，应改为 cur.val
if (val < cur.val) {
cur = cur.left; // 目标值更小，向左子树查找
} else if (val > cur.val) {
cur = cur.right; // 目标值更大，向右子树查找
} else {
return true; // 找到目标值，返回 true
}
}
return false; // 遍历完毕未找到，返回 false
}
/**
* 向二叉搜索树中插入指定值（不允许重复值）
* @param val 待插入的值
*/
public void insert(int val) {
// 若根结点为空，直接创建新结点作为根
if (root == null) {
root = new TreeNode(val);
return;
}
TreeNode cur = root;
TreeNode parent = null; // 记录 cur 的父结点，用于后续插入新结点
// 循环找到插入位置
while (cur != null) {
if (val < cur.val) {
parent = cur;
cur = cur.left;
} else if (val > cur.val) {
parent = cur;
cur = cur.right;
} else {
return; // 存在重复值，直接返回（不允许重复插入）
}
}
// 创建新结点
TreeNode newNode = new TreeNode(val);
// 判断新结点应该插入到 parent 的左孩子还是右孩子
if (val < parent.val) {
parent.left = newNode;
} else {
parent.right = newNode;
}
}
/**
* 删除二叉搜索树中指定值的结点
* @param val 待删除的值
*/
public void removeVal(int val) {
TreeNode cur = root;
TreeNode parent = null;
// 循环找到待删除结点 cur 及其父结点 parent
while (cur != null) {
if (val < cur.val) {
parent = cur;
cur = cur.left;
} else if (val > cur.val) {
parent = cur;
cur = cur.right;
} else {
// 找到待删除结点，调用 removeNode 执行删除逻辑
removeNode(parent, cur);
return;
}
}
}
/**
* 核心：执行二叉搜索树的结点删除逻辑（分三种情况）
* @param parent 待删除结点 cur 的父结点
* @param cur 待删除结点
*/
private void removeNode(TreeNode parent, TreeNode cur) {
// 情况1：待删除结点没有左孩子（cur.left == null）
if (cur.left == null) {
// 子情况1.1：待删除结点是根结点
if (cur == root) {
root = root.right;
}
// 子情况1.2：待删除结点是父结点的左孩子
else if (cur == parent.left) {
parent.left = cur.right;
}
// 子情况1.3：待删除结点是父结点的右孩子
else if (cur == parent.right) {
parent.right = cur.right;
}
}
// 情况2：待删除结点没有右孩子（cur.right == null）
else if (cur.right == null) {
// 子情况2.1：待删除结点是根结点
if (cur == root) {
root = cur.left;
}
// 子情况2.2：待删除结点是父结点的左孩子
else if (cur == parent.left) {
parent.left = cur.left;
}
// 子情况2.3：待删除结点是父结点的右孩子
else if (cur == parent.right) {
parent.right = cur.left;
}
}
// 情况3：待删除结点既有左孩子，又有右孩子（采用替换法删除）
else {
// 步骤1：找到 cur 右子树中最小的结点（最左侧结点）target
TreeNode target = cur.right;
TreeNode targetParent = cur; // 记录 target 的父结点
while (target.left != null) {
targetParent = target;
target = target.left;
}
// 步骤2：用 target 的值替换 cur 的值
cur.val = target.val;
// 步骤3：删除 target 结点（target 一定没有左孩子，只需处理右孩子即可）
if (target == targetParent.right) {
targetParent.right = target.right;
} else {
targetParent.left = target.right;
}
}
}
}
TreeMap 的实际使用
TreeMap 是 Map 接口的实现类，底层基于红黑树实现，其键（Key）具有有序性（默认升序，可自定义比较器），同时满足以下核心特性：
Map是接口，无法直接实例化，只能实例化其实现类（TreeMap/HashMap等）TreeMap中的 Key 是唯一的，不允许重复（重复插入会覆盖原有 Value）TreeMap中的 Key 不能为空（会抛出NullPointerException），Value 可以为空- 遍历
TreeMap时，结果会按照 Key 的顺序排列
完整使用示例
import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapTest {
public static void main(String[] args) {
// 1. 创建 TreeMap 实例（Key 为 String 类型，Value 为 Integer 类型，默认按 Key 升序排列）
Map<String, Integer> treeMap = new TreeMap<>();
// 2. put(K key, V value)：插入键值对，Key 重复则覆盖原有 Value
treeMap.put("Hello", 5);
treeMap.put("Halo", 6);
treeMap.put("Meat", 10);
System.out.println("插入后的 TreeMap：" + treeMap);
// 3. get(Object key)：根据 Key 获取对应的 Value，Key 不存在返回 null
int val1 = treeMap.get("Meat");
System.out.println("\"Meat\" 对应的 Value：" + val1);
// 4. getOrDefault(Object key, V defaultValue)：根据 Key 获取 Value，Key 不存在返回默认值
Integer val2 = treeMap.getOrDefault("Halo", 666);
Integer val3 = treeMap.getOrDefault("Hi", 666);
System.out.println("\"Halo\" 对应的 Value（带默认值）：" + val2);
System.out.println("\"Hi\" 对应的 Value（带默认值）：" + val3);
// 5. remove(Object key)：根据 Key 删除对应的键值对，返回被删除的 Value
treeMap.remove("Meat");
System.out.println("删除 \"Meat\" 后的 TreeMap：" + treeMap);
// 6. keySet()：返回所有 Key 组成的不重复 Set 集合
Set<String> keySet = treeMap.keySet();
System.out.println("TreeMap 的所有 Key：" + keySet);
// 7. values()：返回所有 Value 组成的 Collection 集合（允许重复）
Collection<Integer> values = treeMap.values();
System.out.println("TreeMap 的所有 Value：" + values);
// 8. entrySet()：返回所有键值对（Map.Entry）组成的 Set 集合，用于遍历
Set<Map.Entry<String, Integer>> entrySet = treeMap.entrySet();
System.out.println("遍历 TreeMap 的键值对：");
for (Map.Entry<String, Integer> entry : entrySet) {
String key = entry.getKey();
Integer val = entry.getValue();
System.out.println("Key: " + key + " , Value: " + val);
}
// 9. containsKey(Object key)：判断是否包含指定 Key
boolean hasKey = treeMap.containsKey("Hello");
boolean hasKey2 = treeMap.containsKey("hello");
System.out.println("是否包含 Key \"Hello\"：" + hasKey);
System.out.println("是否包含 Key \"hello\"：" + hasKey2);
// 10. containsValue(Object value)：判断是否包含指定 Value
boolean hasValue = treeMap.containsValue(5);
System.out.println("是否包含 Value 5：" + hasValue);
}
}
运行结果参考
插入后的 TreeMap：{Halo=6, Hello=5, Meat=10}
"Meat" 对应的 Value：10
"Halo" 对应的 Value（带默认值）：6
"Hi" 对应的 Value（带默认值）：666
删除 "Meat" 后的 TreeMap：{Halo=6, Hello=5}
TreeMap 的所有 Key：[Halo, Hello]
TreeMap 的所有 Value：[6, 5]
遍历 TreeMap 的键值对：
Key: Halo , Value: 6
Key: Hello , Value: 5
是否包含 Key "Hello"：true
是否包含 Key "hello"：false
是否包含 Value 5：true
TreeSet 的实际使用
TreeSet 是 Set 接口的实现类，底层依赖于 TreeMap 实现（将元素作为 TreeMap 的 Key，Value 为一个固定的空对象），因此它也具有有序性，且元素唯一不重复。
完整使用示例
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
// 1. 创建 TreeSet 实例（存储 String 类型元素，默认升序排列）
TreeSet<String> treeSet = new TreeSet<>();
// 2. add(E e)：添加元素，元素重复则不执行任何操作
treeSet.add("Hello");
treeSet.add("Meat");
treeSet.add("Hello"); // 重复元素，添加失败
System.out.println("添加元素后的 TreeSet：" + treeSet);
// 3. size()：返回集合中有效元素的个数
int size = treeSet.size();
System.out.println("TreeSet 的元素个数：" + size);
// 4. contains(Object o)：判断集合中是否包含指定元素
boolean contains = treeSet.contains("Hello");
System.out.println("是否包含元素 \"Hello\"：" + contains);
// 5. isEmpty()：判断集合是否为空
boolean isEmpty = treeSet.isEmpty();
System.out.println("TreeSet 是否为空：" + isEmpty);
// 6. clear()：清空集合中的所有元素
treeSet.clear();
System.out.println("清空后的 TreeSet：" + treeSet);
System.out.println("清空后是否为空：" + treeSet.isEmpty());
}
}
运行结果参考
添加元素后的 TreeSet：[Hello, Meat]
TreeSet 的元素个数：2
是否包含元素 "Hello"：true
TreeSet 是否为空：false
清空后的 TreeSet：[]
清空后是否为空：true
红黑树与 TreeMap/TreeSet 核心总结
- 红黑树是一种自平衡的二叉搜索树，能够避免二叉搜索树退化为链表的问题，保证增删改查的时间复杂度为 O(logn)
TreeMap底层由红黑树实现，其 Key 具有有序性，且唯一不可为空TreeSet底层依赖TreeMap实现，元素作为TreeMap的 Key，因此元素唯一且有序
二、HashMap 与 HashSet（基于哈希表实现）
HashMap 和 HashSet 是 Java 集合框架中查询效率极高的集合，它们的底层基于**哈希表（数组 + 链表/红黑树）**实现，能够提供平均 O(1) 时间复杂度的增删改查操作。
哈希表的模拟实现
哈希表的核心思想是通过哈希函数将 Key 映射到数组的指定索引，从而实现快速查找。下面通过代码模拟实现一个简单的哈希表（数组 + 链表，即“拉链法”解决哈希冲突）：
public class MyHashBuck {
// 定义哈希表的结点结构（链表结点）
static class Node {
public int key; // 键
public int val; // 值
public Node next; // 下一个结点的引用
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
public Node[] array; // 存储链表头结点的数组
public int usedSize; // 哈希表中有效键值对的个数
public static final double LOAD_FACTOR = 0.75; // 加载因子（默认 0.75，平衡查询效率和空间利用率）
// 构造方法：初始化数组容量为 10
public MyHashBuck() {
this.array = new Node[10];
}
/**
* 向哈希表中插入键值对
* @param key 待插入的键
* @param val 待插入的值
*/
public void put(int key, int val) {
// 步骤1：通过哈希函数（取模）计算 key 对应的数组索引
int index = key % array.length;
// 步骤2：遍历该索引对应的链表，判断 key 是否已存在（存在则覆盖 val）
Node cur = array[index];
while (cur != null) {
if (cur.key == key) {
cur.val = val; // 覆盖原有值
return;
}
cur = cur.next;
}
// 步骤3：key 不存在，采用头插法插入新结点
Node newNode = new Node(key, val);
newNode.next = array[index];
array[index] = newNode;
// 步骤4：有效键值对个数加 1，并判断是否需要扩容
this.usedSize++;
if (calculateLoadFactor() > LOAD_FACTOR) {
grow(); // 扩容
}
}
/**
* 根据 key 从哈希表中获取对应的值
* @param key 待查询的键
* @return 对应的 value，key 不存在返回 -1
*/
public int get(int key) {
// 步骤1：计算 key 对应的数组索引
int index = key % array.length;
// 步骤2：遍历该索引对应的链表，查找 key
Node cur = array[index];
while (cur != null) {
if (cur.key == key) {
return cur.val; // 找到 key，返回对应 value
}
cur = cur.next;
}
return -1; // 未找到 key，返回 -1
}
/**
* 哈希表扩容（扩容为原数组容量的 2 倍）
* 修正：原代码扩容时存在逻辑错误，已优化
*/
private void grow() {
// 步骤1：创建新数组（容量为原数组的 2 倍）
Node[] newArray = new Node[2 * array.length];
// 步骤2：遍历原数组，将所有结点重新哈希到新数组中
for (int i = 0; i < array.length; i++) {
Node cur = array[i];
while (cur != null) {
Node curNext = cur.next; // 记录当前结点的下一个结点（防止链表断裂）
// 步骤3：计算当前结点在新数组中的索引
int newIndex = cur.key % newArray.length;
// 步骤4：头插法插入到新数组对应的链表中
cur.next = newArray[newIndex];
newArray[newIndex] = cur;
// 步骤5：继续遍历原链表的下一个结点
cur = curNext;
}
}
// 步骤6：将哈希表的数组替换为新数组
this.array = newArray;
}
/**
* 计算当前哈希表的加载因子
* @return 加载因子（usedSize / array.length）
*/
private double calculateLoadFactor() {
return usedSize * 1.0 / array.length;
}
}
补充说明
-
HashMap 核心特性
- 底层基于哈希表（JDK 1.8 后为数组 + 链表 + 红黑树）实现，平均查询时间复杂度 O(1)
- Key 唯一不重复，Value 可重复，Key 和 Value 都可以为 null（仅允许一个 Key 为 null）
- 无序集合，遍历结果不保证与插入顺序一致
- 默认初始容量 16，加载因子 0.75，扩容为原容量的 2 倍
-
HashSet 核心特性
- 底层依赖
HashMap实现，元素作为HashMap的 Key，Value 为固定空对象 - 元素唯一不重复，无序集合，允许存储 null 元素（仅一个）
- 核心方法与
TreeSet类似，区别在于底层实现和有序性
- 底层依赖