Java 集合框架核心：TreeMap、TreeSet 与哈希表实战详解

一、TreeMap 与 TreeSet1. 核心思路二叉搜索树TreeMap 与 TreeSet 的底层核心数据结构是二叉搜索树Binary Search TreeBST它是一种特殊的二叉树。二叉搜索树具有以下两个关键性质二叉搜索树中的任何一个子树本身也是一棵二叉搜索树。与堆相比二叉搜索树严格区分左右子树的大小关系而堆只保证父节点与子节点之间的堆序不区分左右子树的大小。2. 二叉搜索树的定义二叉搜索树的定义需要严谨表述对于任意节点其左子树中所有节点的值都小于该节点的值其右子树中所有节点的值都大于该节点的值。即左子树 根节点 右子树。易错点提示这里强调的是所有节点而不是直接子节点。例如根节点的右子树的左子树中的节点也必须大于根节点的值。面试中常问为什么二叉搜索树的中序遍历结果是有序的因为中序遍历的顺序是左-根-右而左子树所有节点都小于根节点、右子树所有节点都大于根节点所以中序遍历天然得到升序序列。3. 查找3.1 算法思路用待查找元素与根节点比较看大小关系如果相等则找到了如果待查找元素更小则去左子树找反之则去右子树找。查找过程类似于二分查找每次比较都能排除一半的搜索范围。3.2 代码实现// 查找 public BinarySearchNode find(int data){ BinarySearchNode cur root; while (cur ! null) { if (cur.data data) { cur cur.left; } else if (cur.data data) { cur cur.right; } else { return cur; } } return null; }易错点提示原代码中变量名误写为date应统一为data数据。比较逻辑本身是正确的cur.data data说明当前节点值大于目标值应去左子树找更小的值。3.3 时间复杂度二叉搜索树查找的时间复杂度平均情况为 O(logN)此时树接近平衡最坏情况为 O(N)此时树退化为单链表例如按升序插入元素。4. 插入4.1 算法思路插入新元素后仍然要保持二叉搜索树的性质。从根节点开始按照大小关系向下查找插入位置直到找到空位为止。4.2 代码实现// 插入 public boolean insert(int data){ BinarySearchNode cur root; if (root null) { root new BinarySearchNode(data); return true; } BinarySearchNode parent null; while (cur ! null) { if (cur.data data) { parent cur; cur cur.right; } else if (cur.data data) { parent cur; cur cur.left; } else { return false; // 已存在相同值插入失败 } } // 此时 cur 为空判断插入到 parent 的左子树还是右子树 BinarySearchNode newNode new BinarySearchNode(data); if (parent.data newNode.data) { parent.left newNode; } else { parent.right newNode; } return true; }易错点提示插入的时间复杂度与查找相同平均 O(logN)最坏 O(N)。注意插入时不能破坏二叉搜索树的性质新节点只能作为叶子节点插入。5. 删除5.1 算法思路删除操作分两步第一步先查找待删除元素的位置不存在则无需删除第二步针对该元素进行删除。删除时根据待删除节点的子树情况分三种情形处理左子树为空直接让父节点指向待删除节点的右子树。右子树为空直接让父节点指向待删除节点的左子树。左右子树均非空使用移花接木法找到右子树中最左侧的节点即右子树中的最小值用该节点的值替换待删除节点的值然后删除这个最小值节点。5.2 代码实现// 删除 public boolean remove(int data){ BinarySearchNode cur root; BinarySearchNode parent null; while (cur ! null) { if (cur.data data) { parent cur; cur cur.left; } else if (cur.data data) { parent cur; cur cur.right; } else { removeHelper(cur, parent); return true; } } return false; } public void removeHelper(BinarySearchNode cur, BinarySearchNode parent){ if (cur.left null) { if (cur root) { root cur.right; } else if (cur parent.left) { parent.left cur.right; } else if (cur parent.right) { parent.right cur.right; } } else if (cur.right null) { if (cur root) { root cur.left; } else if (cur parent.left) { parent.left cur.left; } else if (cur parent.right) { parent.right cur.left; } } else { // 移花接木把 cur.right 的最小值替换到 cur 位置然后删除最小值节点 BinarySearchNode goat cur.right; BinarySearchNode goatParent cur; while (goat.left ! null) { goatParent goat; goat goat.left; } cur.data goat.data; // 此时 goat 一定没有左子树 if (goatParent.left goat) { goatParent.left goat.right; } else { goatParent.right goat.right; } } }易错点提示删除逻辑是完整的边界情况删除根节点、goatParent.right goat都已正确处理。删除的时间复杂度同样为平均 O(logN)最坏 O(N)。面试常问为什么删除左右子树都非空的节点时要选择右子树的最小值或左子树的最大值来替换因为这样才能保证替换后仍然满足二叉搜索树的性质。6. 补充TreeMap / TreeSet 的底层实现需要特别说明的是Java 中的TreeMap 和 TreeSet 底层使用的是红黑树而不是普通的二叉搜索树。红黑树是一种自平衡的二叉搜索树它通过颜色约束和旋转操作保证树的高度始终维持在 O(logN) 级别从而避免普通二叉搜索树在极端情况下退化为链表的问题。面试常问角度红黑树与普通二叉搜索树的区别是什么红黑树通过以下五条性质保证平衡节点是红色或黑色根节点是黑色所有叶子节点NIL是黑色红色节点的两个子节点都是黑色从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。二、Set 和 Map1. Set —— 集合1.1 核心应用场景Set 最核心的应用场景是查找它不擅长遍历。与之相对List、ArrayList、LinkedList 不擅长查找但擅长遍历。实例化方式SetT set new TreeSet();1.2 迭代器遍历通过迭代器 Iterator 针对集合中的元素一个一个地访问IteratorString iterator set.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); }foreach 是迭代器的简化写法本质上是编译器对迭代器模式的语法糖。1.3 主要方法插入set.add();查找set.contains();删除set.remove();1.4 复杂度分析TreeSet 基于红黑树实现其查找、插入、删除的时间复杂度均为O(logN)空间复杂度为O(N)。原文档中空间复杂度 O(logN)的说法是不准确的应为 O(N)因为需要存储所有元素。易错点提示TreeSet 与 HashSet 的复杂度需要分开说明。TreeSet 基于红黑树操作复杂度为 O(logN)HashSet 基于哈希表操作复杂度平均为 O(1)。选择时如果需要有序集合用 TreeSet如果只关心查找速度用 HashSet。2. Map —— 映射2.1 基本概念Map 主要表示一个关联关系由键值对key-value构成。核心目标是根据 key 快速找到 value。实例化方式MapT, T map new TreeMap();第一个 T 是 key 的类型第二个 T 是 value 的类型两个类型不一定相等。2.2 主要方法根据 key 插入/修改 valuemap.put(及时雨, 宋江);根据 key 获取 valueString value map.get(及时雨);根据 key 删除键值对map.remove(及时雨);2.3 遍历方式Java 中 Map 并不支持直接遍历需要转换为 EntrySet 后才能遍历for (Map.EntryString, String entry : map.entrySet()) { System.out.println(entry.getKey() : entry.getValue()); }2.4 注意事项只能修改 value不能修改 key。只能通过 key 找 value不能反过来。value 可以是任意类型但 key 的类型必须是可比较类型实现了 Comparable 接口。2.5 复杂度分析TreeMap 基于红黑树查找、插入、删除的时间复杂度均为O(logN)空间复杂度为O(N)。易错点提示TreeMap 与 HashMap 如何选择如果需要按键的自然顺序遍历选择 TreeMap如果只追求查找性能选择 HashMap。另外HashMap 与 HashTable 的区别HashMap 非线程安全、允许 null 键和 null 值HashTable 线程安全方法加 synchronized、不允许 null 键和 null 值。HashMap 的扩容机制当元素个数超过负载因子与容量的乘积时容量翻倍并重新哈希。三、哈希表Hash1. 基本结构哈希表本质上是由数组和链表组合而成的数据结构。需要澄清的是哈希表并不是使用数组下标来保存 key、使用数组的值来保存 value而是通过哈希函数将 key 映射到数组下标数组的每个位置存储一个链表哈希桶链表的节点保存 key-value 键值对。key 允许多种不同类型需要通过哈希函数映射到数组下标上从而实现 O(1) 复杂度的存储。2. 哈希值计算方式哈希值的计算方式为int index key % arr.length。无论哪种哈希函数最终都需要通过取模运算映射到数组下标。3. 哈希冲突把一个范围大的区间映射到范围小的区间可能会产生冲突两个不同的 key 映射到同一个下标上。解决方案有两种线性探测闭散列发现冲突后继续往后找直到下一个空闲位置。哈希桶开散列数组的元素不是单个 value而是哈希桶构成的链表冲突的元素挂在同一个链表中。易错点提示面试常问两种冲突解决方案的区别和适用场景。线性探测闭散列实现简单但容易产生聚集现象删除操作需要特殊处理标记删除哈希桶开散列是 Java HashMap 采用的方式冲突处理更灵活删除操作简单但需要额外的链表节点开销。4. 负载因子当负载因子达到一定阈值时哈希表会自动扩容。负载因子的计算公式为负载因子 总的元素个数 / 数组长度。5. TreeMap 与 HashMap 的选择如果需要把元素按照顺序来组织使用 TreeMap因为其中序遍历是有序序列如果只追求查找效率使用 HashMap。6. 简单哈希表实现6.1 算法思路根据 key 算出哈希值找到对应下标。根据下标取出链表。检查 key 在链表中是否已经存在如果存在直接修改对应的 value如果不存在才真正使用头插法插入节点。6.2 代码实现package Hash; class Node { public int key; public int value; public Node next; public Node(int key, int value) { this.key key; this.value value; } } public class MyHash { public Node[] arr new Node[1000]; private int size 0; private int myHashCode(int key) { return key % arr.length; } // 插入和修改 public void put(int key, int value) { // 获得 key 值计算数组下标 int index myHashCode(key); // 根据下标获取链表 Node head arr[index]; // 使用 key 寻找链表里面有没有 for (Node cur head; cur ! null; cur cur.next) { if (cur.key key) { // 修改值 cur.value value; return; } } // 如果循环结束没有找到则把键值对头插 Node newNode new Node(key, value); newNode.next head; arr[index] newNode; size; if (loadFactor() 0.75) { realloc(); } } // 负载因子总元素个数 / 数组长度 public double loadFactor() { return (double) size / arr.length; } // 数组扩容外层循环拆链表内层循环挂链表 private void realloc() { Node[] newArray new Node[arr.length * 2]; for (int i 0; i arr.length; i) { Node next null; for (Node cur arr[i]; cur ! null; cur next) { next cur.next; int index cur.key % newArray.length; cur.next newArray[index]; newArray[index] cur; } } this.arr newArray; } // 查找元素找到了返回 value没找到返回 null public Integer get(int key) { int index myHashCode(key); Node head arr[index]; for (Node cur head; cur ! null; cur cur.next) { if (cur.key key) { return cur.value; } } return null; } // 删除 public void remove(int key) { int index myHashCode(key); Node head arr[index]; if (head null) { return; // 链表为空直接返回 } if (head.key key) { arr[index] head.next; return; } Node prev head; Node cur head.next; while (cur ! null) {