目录一、为什么需要Map和Set1.1 从实际问题出发1.2 两种搜索模型二、二叉搜索树TreeMap和TreeSet的底层基石2.1 什么是二叉搜索树2.2 查找操作2.3 插入操作2.4 删除操作难点2.5 BST的性能问题三、Map接口详解3.1 Map概述3.2 Map的核心方法3.3 遍历Map的三种方式3.4 TreeMap vs HashMap四、Set接口详解4.1 Set概述4.2 Set的核心方法4.3 Set的遍历4.4 TreeSet vs HashSet五、哈希表HashMap和HashSet的底层基石5.1 哈希表的核心思想5.2 哈希冲突5.3 负载因子5.4 解决冲突开散列哈希桶5.5 手写一个简单的哈希表5.6 自定义类型作为HashMap的Key六、实战演练6.1 统计单词出现次数6.2 找出数组中只出现一次的数字6.3 找出两个数组的交集七、总结与对比7.1 整体架构7.2 核心要点7.3 如何选择写在前面本文基于《Map和Set》课程内容整理结合个人学习笔记和实践经验编写。旨在帮助读者系统掌握Map和Set两大集合体系以及背后的数据结构原理。如需深入学习建议配合Oracle官方文档和JDK源码阅读。一、为什么需要Map和Set1.1 从实际问题出发想象一下这些场景通讯录输入联系人姓名立刻查到电话号码词典输入英文单词立刻显示中文释义去重统计统计一篇文章中出现了多少个不同的单词缓存系统根据用户ID快速获取用户信息这些场景都有一个共同点——搜索。但这里的搜索和我们之前学的二分查找不太一样数据是动态变化的随时可能插入新数据或删除旧数据。Map和Set正是Java为我们提供的动态搜索容器。1.2 两种搜索模型模型存储内容典型场景对应接口纯Key模型​只存Key查单词是否在词典中SetKey-Value模型​存键值对查姓名对应的电话Map打个比方Set就像一个会员名单你只能知道某人是不是会员Map则像一本通讯录通过姓名可以查到电话号码。二、二叉搜索树TreeMap和TreeSet的底层基石2.1 什么是二叉搜索树二叉搜索树Binary Search Tree简称BST是一种特殊的二叉树它满足以下性质左子树所有节点的值都小于根节点的值右子树所有节点的值都大于根节点的值左右子树也都是二叉搜索树5 / \ 3 7 / \ / \ 1 4 6 8核心思想利用二分查找的思路组织数据使得查找效率从O(n)提升到O(log n)。2.2 查找操作public TreeNode search(int key) { TreeNode cur root; while (cur ! null) { if (key cur.key) { return cur; // 找到了 } else if (key cur.key) { cur cur.left; // 去左子树找 } else { cur cur.right; // 去右子树找 } } return null; // 没找到 }查找过程每次比较都能排除一半的节点就像翻字典一样——你要查的字如果比当前页大就往后面翻否则往前翻。2.3 插入操作public boolean insert(int key) { if (root null) { root new TreeNode(key); return true; } TreeNode cur root; TreeNode parent null; while (cur ! null) { if (key cur.key) { return false; // 已存在插入失败 } else if (key cur.key) { parent cur; cur cur.left; } else { parent cur; cur cur.right; } } // 找到插入位置 TreeNode node new TreeNode(key); if (key parent.key) { parent.left node; } else { parent.right node; } return true; }插入逻辑先查找如果找到相同key则返回falseBST不允许重复如果没找到就在查找路径上的最后一个节点处插入。2.4 删除操作难点删除是BST中最复杂的操作需要分三种情况讨论public boolean remove(int key) { TreeNode cur root; TreeNode parent null; // 先找到要删除的节点 while (cur ! null) { if (key cur.key) { break; // 找到了 } else if (key cur.key) { parent cur; cur cur.left; } else { parent cur; cur cur.right; } } if (cur null) { return false; // 没找到 } // 情况1cur没有左孩子 if (cur.left null) { if (cur root) { root cur.right; } else if (cur parent.left) { parent.left cur.right; } else { parent.right cur.right; } } // 情况2cur没有右孩子 else if (cur.right null) { if (cur root) { root cur.left; } else if (cur parent.left) { parent.left cur.left; } else { parent.right cur.left; } } // 情况3cur既有左孩子又有右孩子 else { // 在右子树中找最小的节点中序下的第一个节点 TreeNode targetParent cur; TreeNode target cur.right; while (target.left ! null) { targetParent target; target target.left; } // 用target的值替换cur cur.key target.key; // 删除target节点 if (target targetParent.left) { targetParent.left target.right; } else { targetParent.right target.right; } } return true; }情况3的原理当要删除的节点有两个孩子时用右子树中最小的节点或左子树中最大的节点的值替换当前节点然后删除那个替身节点。这样既保持了BST的性质又避免了复杂的结构调整。2.5 BST的性能问题BST的性能取决于树的形状5 1 / \ \ 3 7 2 / \ \ \ 1 4 8 3 \ 4 \ 5完全二叉树查找效率 O(log n) ✅单支树查找效率 O(n) ❌退化成了链表问题如果插入顺序不当BST会退化为单支树性能大打折扣。解决方案引入平衡机制——红黑树。TreeMap和TreeSet底层使用的就是红黑树它通过颜色约束和旋转操作保证树的高度始终保持在O(log n)。三、Map接口详解3.1 Map概述Map是一个接口存储的是Key, Value​ 键值对Key唯一Value可以重复。MapString, String map new TreeMap(); map.put(林冲, 豹子头); map.put(武松, 行者);3.2 Map的核心方法方法说明返回值含义put(K key, V value)插入键值对返回旧value不存在返回nullget(Object key)获取value不存在返回nullgetOrDefault(K key, V defaultValue)获取value带默认值不存在返回defaultValueremove(Object key)删除键值对返回被删除的valuecontainsKey(Object key)判断是否包含keyO(log n)containsValue(Object value)判断是否包含valueO(n)keySet()获取所有key的Set可用于遍历keyvalues()获取所有value的Collection可用于遍历valueentrySet()获取所有键值对的Set可用于同时遍历key和valuesize()返回键值对数量isEmpty()判断是否为空3.3 遍历Map的三种方式MapString, String map new TreeMap(); map.put(林冲, 豹子头); map.put(武松, 行者); map.put(宋江, 及时雨); // 方式一遍历key再通过key获取value for (String key : map.keySet()) { System.out.println(key --- map.get(key)); } // 方式二遍历value只能拿到值拿不到key for (String value : map.values()) { System.out.println(value); } // 方式三遍历键值对Entry推荐 for (Map.EntryString, String entry : map.entrySet()) { System.out.println(entry.getKey() --- entry.getValue()); }3.4 TreeMap vs HashMap对比维度TreeMapHashMap底层结构红黑树哈希表数组链表/红黑树时间复杂度O(log n)O(1)是否有序Key有序自然顺序或Comparator无序Key是否可为null不可以抛NullPointerException可以Value是否可为null可以可以适用场景需要Key有序追求高性能不在意顺序四、Set接口详解4.1 Set概述Set是一个接口继承自Collection只存储Key且Key唯一。它本质上是一个阉割版的Map——底层就是用Map实现的只是把value统一设为一个固定的Object对象。SetString set new TreeSet(); set.add(apple); set.add(banana);4.2 Set的核心方法方法说明add(E e)添加元素重复返回falseremove(Object o)删除元素contains(Object o)判断是否包含size()返回元素个数isEmpty()判断是否为空clear()清空集合iterator()返回迭代器4.3 Set的遍历SetString set new TreeSet(); set.add(apple); set.add(orange); set.add(banana); // 方式一增强for for (String s : set) { System.out.println(s); } // 方式二迭代器 IteratorString it set.iterator(); while (it.hasNext()) { System.out.println(it.next()); }4.4 TreeSet vs HashSet对比维度TreeSetHashSet底层结构红黑树TreeMap哈希表HashMap时间复杂度O(log n)O(1)是否有序有序无序Key是否可为null不可以可以适用场景需要有序去重高性能去重五、哈希表HashMap和HashSet的底层基石5.1 哈希表的核心思想有没有一种方法不经过任何比较直接通过关键字找到对应的存储位置答案是哈希表。它通过一个哈希函数将关键字映射到一个存储位置存储位置 hash(key) % 数组长度比如要存储集合 {1, 7, 6, 4, 5, 9}数组长度为10hash(1) 1 % 10 1 → 存到下标1 hash(7) 7 % 10 7 → 存到下标7 hash(4) 4 % 10 4 → 存到下标4 ...5.2 哈希冲突如果我们要再插入44hash(44) 44 % 10 4 → 下标4已经被4占了这就是哈希冲突不同的关键字通过哈希函数算出了相同的地址。冲突是无法完全避免的因为数组长度有限我们能做的是尽量降低冲突率并在冲突发生时妥善处理。5.3 负载因子负载因子 已存储元素个数 / 数组长度负载因子 0.75 表示数组已经装了75%负载因子越大冲突概率越高性能越差。Java的HashMap默认负载因子为0.75当超过这个值时会进行扩容resize将数组扩大为原来的2倍然后重新哈希所有元素。5.4 解决冲突开散列哈希桶Java的HashMap采用的是开散列也叫链地址法来解决冲突数组的每个位置不是一个元素而是一个链表的头节点发生冲突的元素挂在同一个链表中数组[0] → [1] → [2] → [3] → [4] → ... ↓ [4] → [44] → null当链表过长时超过8个链表会转为红黑树保证最坏情况下的查找效率仍然是O(log n)。5.5 手写一个简单的哈希表public class MyHashTable { private static class Node { int key; int value; Node next; public Node(int key, int value) { this.key key; this.value value; } } private Node[] array; private int size; private static final double LOAD_FACTOR 0.75; public MyHashTable() { array new Node[8]; size 0; } // 插入 public int put(int key, int value) { int index key % array.length; // 查找是否已存在 for (Node cur array[index]; cur ! null; cur cur.next) { if (key cur.key) { int oldValue cur.value; cur.value value; return oldValue; } } // 头插法插入新节点 Node node new Node(key, value); node.next array[index]; array[index] node; size; // 检查是否需要扩容 if (size * 1.0 / array.length LOAD_FACTOR) { resize(); } return -1; } // 查找 public int get(int key) { int index key % array.length; for (Node cur array[index]; cur ! null; cur cur.next) { if (key cur.key) { return cur.value; } } return -1; } // 扩容 private void resize() { Node[] newArray new Node[array.length * 2]; for (int i 0; i array.length; i) { Node cur array[i]; while (cur ! null) { Node next cur.next; // 重新计算在新数组中的位置 int newIndex cur.key % newArray.length; // 头插法 cur.next newArray[newIndex]; newArray[newIndex] cur; cur next; } } array newArray; } }5.6 自定义类型作为HashMap的Key如果要用自定义类作为HashMap的key必须同时覆写equals和hashCode方法并且保证equals相等的对象hashCode一定相等hashCode相等的对象equals不一定相等可能发生哈希冲突public class Person { private String idCard; private String name; Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Person person (Person) o; return Objects.equals(idCard, person.idCard); } Override public int hashCode() { return Objects.hash(idCard); } }六、实战演练6.1 统计单词出现次数public MapString, Integer countWords(String text) { MapString, Integer wordCount new HashMap(); String[] words text.split(\\s); for (String word : words) { // getOrDefault如果不存在默认值为0 wordCount.put(word, wordCount.getOrDefault(word, 0) 1); } return wordCount; }6.2 找出数组中只出现一次的数字public int singleNumber(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { if (set.contains(num)) { set.remove(num); // 第二次出现删除 } else { set.add(num); // 第一次出现添加 } } // 最后剩下的就是只出现一次的数字 return set.iterator().next(); }6.3 找出两个数组的交集public int[] intersection(int[] nums1, int[] nums2) { SetInteger set1 new HashSet(); for (int num : nums1) { set1.add(num); } SetInteger resultSet new HashSet(); for (int num : nums2) { if (set1.contains(num)) { resultSet.add(num); } } // 转换为数组 int[] result new int[resultSet.size()]; int i 0; for (int num : resultSet) { result[i] num; } return result; }七、总结与对比7.1 整体架构Map (接口) Set (接口继承Collection) ├── TreeMap (红黑树) ├── TreeSet (红黑树) ├── HashMap (哈希表) ├── HashSet (哈希表) └── LinkedHashMap (哈希表链表) └── LinkedHashSet (哈希表链表)7.2 核心要点知识点关键内容二叉搜索树​左小右大查找O(log n)可能退化为单支树红黑树​平衡的BSTTreeMap/TreeSet底层Map​存储Key-Value键值对Key唯一Set​只存储Key底层用Map实现哈希表​通过哈希函数直接定位理想O(1)哈希冲突​不可避免用链地址法解决负载因子​默认0.75超过则扩容equals和hashCode​自定义类型作为Key时必须同时覆写7.3 如何选择需求推荐方案需要Key有序TreeMap / TreeSet追求性能不在意顺序HashMap / HashSet需要保留插入顺序LinkedHashMap / LinkedHashSet需要统计频次HashMap需要去重HashSet如果你觉得这篇文章对你有帮助欢迎点赞收藏。后续我们将继续深入Java集合框架的更多内容敬请期待注本文为个人学习总结所有代码示例均为独立编写。建议读者在学习过程中结合JDK官方文档和源码进行验证。