引言在 Java 集合框架的大家族里List、Queue、Map、Set 是我们最常打交道的四大角色。如果说 List 解决的是有序存储与索引访问的问题Queue 解决的是先进先出的排队问题那么Map 和 Set解决的就是另一个高频需求——快速查找。想象一下这些场景通讯录里根据姓名秒查电话号码统计一篇文章中每个单词出现的频次去重一个数组并判断某个元素是否已经出现过。这些操作如果用 List 来做每次都要从头遍历时间复杂度 O(N)数据量一大就慢得离谱。而 Map 和 Set 正是为动态查找而生的——它们能让插入、删除、查找的效率从 O(N) 提升到 O(logN) 甚至 O(1)。这篇文章将从底层数据结构出发带你搞懂 Map 和 Set 的来龙去脉先从二叉搜索树说起理解 TreeMap / TreeSet 为什么是有序的再通过代码实战掌握它们的常用 API 和选型策略。至于 HashMap / HashSet 背后的哈希表原理我们留到下一篇单独展开。目录引言1.搜索树Map 与 Set 的底层基石1.1 什么是二叉搜索树1.2 查找、插入与删除操作1.3 性能分析与退化问题1.4 与 Java 类集的关系2.Map 和 Set 概述2.1 纯 Key 模型与 Key-Value 模型2.2 类继承体系总览3.Map 的使用3.1 Map 接口核心方法3.2 Map.Entry 键值对3.3 TreeMap 与 HashMap 的区别3.4 代码实战TreeMap 常用操作4.Set 的使用4.1 Set 接口核心方法4.2 TreeSet 与 HashSet 的区别4.3 代码实战TreeSet 常用操作总结与选型建议1.搜索树Map 与 Set 的底层基石1.1 什么是二叉搜索树二叉搜索树BSTBinary Search Tree又称二叉排序树。它要么是空树要么满足以下三条性质若左子树不为空则左子树上所有节点的值都小于根节点的值若右子树不为空则右子树上所有节点的值都大于根节点的值左右子树本身也分别是一棵二叉搜索树。这种左小右大的结构使得查找操作可以像二分查找一样每次排除掉一半的搜索空间。1.2 查找、插入与删除操作查找从根节点出发若根节点 key 等于目标值则返回若目标值小于根节点 key则去左子树找否则去右子树找。直到找到或遇到 null。插入空树直接插入非空树则按查找逻辑走到空位挂在父节点的左或右孩子位置。删除难点分三种情况讨论——情况处理方式待删节点左孩子为空用右孩子顶替根节点则直接改 root待删节点右孩子为空用左孩子顶替左右孩子都不为空找右子树中序下的第一个节点即右子树最小值来替换待删节点的值再删除那个替代节点package tree; class BinarySearchNode{ public int data; public BinarySearchNode rightnull; public BinarySearchNode leftnull; public BinarySearchNode(int data){ this.datadata; } } public class BinarySearchTree { private BinarySearchNode rootnull; //查找 public BinarySearchNode find(int data){ BinarySearchNode curroot; while(cur!null){ if(datacur.data){ curcur.left;//往左找 }else if(datacur.data){ curcur.right; } else{ return cur; } } return null; } //插入 public boolean insert(int data){ if(rootnull){ rootnew BinarySearchNode(data); return true; } //寻找要插入的位置 BinarySearchNode curroot; BinarySearchNode parentnull; while(cur!null){ if(datacur.data){ parentcur; curcur.left; } else if(datacur.data){ parentcur; curcur.right; }else{ return false;//相等约定过这个树不存在相同的元素 } } BinarySearchNode newNodenew BinarySearchNode(data); if(dataparent.data){ parent.leftnewNode; } else if(dataparent.data){ parent.rightnewNode; } return true; } //删除 public boolean delete(int data){ //先查找对应节点是那个 BinarySearchNode curroot; BinarySearchNode parentnull; while(cur!null){ if(datacur.data){ parentcur; curcur.left; } else if(datacur.data){ parentcur; curcur.right; } else{ removeNode(cur,parent); return true; } } return false; // 找不到节点返回false } private void removeNode(BinarySearchNode cur,BinarySearchNode parent){ //分三种情况 if(cur.leftnull){ //1.cur没有左子树 if(curroot){ rootcur.right; } else if(cur parent.right){ parent.rightcur.right; }else if(cur parent.left){ parent.leftcur.right; } } else if(cur.rightnull){ //cur没有右子树 if(curroot){ //cur就是根节点 rootcur.left; } else if(curparent.right){ parent.rightcur.left; }else if(curparent.left){ parent.leftcur.left; } } else{ //cur两个子树 //a 在右子树中找到最左侧元素(右子树中最小值)同时记录父节点 BinarySearchNode goatcur.right; BinarySearchNode goatParentcur; while(goat.left ! null){ goatParentgoat; goatgoat.left; } //b 把goat节点的值赋值到cur中 cur.datagoat.data; //c 把goat删除掉我们认为goat一定没有左子树的 if(goatgoatParent.left ){ goatParent.left goat.right; } else{ goatParent.rightgoat.right; } } } public static void main(String[] args) { BinarySearchTree treenew BinarySearchTree(); tree.insert(1); tree.insert(2); tree.insert(3); tree.insert(4); BinarySearchNode resulttree.find(4); System.out.println(result); tree.delete(4); } } }1.3 性能分析与退化问题插入和删除都必须先查找所以查找效率代表了二叉搜索树中各操作的性能。最优情况树接近完全二叉树平均查找长度为O(logN)最差情况树退化成单支链表平均查找长度为O(N)。同一个关键字集合按不同顺序插入会得到完全不同的树结构。如果按 3→4→5→6→7→8→9 的顺序插入树就退化成了右单支链表性能直接从对数级掉到线性级。这就是为什么 Java 中的 TreeMap 和 TreeSet 不直接使用普通二叉搜索树而是使用红黑树——红黑树是一棵近似平衡的二叉搜索树通过颜色标记和旋转操作保证树不会退化从而始终维持 O(logN) 的操作效率。1.4 与 Java 类集的关系TreeMap 和 TreeSet 在 Java 中就是利用搜索树红黑树实现的 Map 和 Set。理解了二叉搜索树的增删查逻辑就理解了 TreeMap / TreeSet 的核心原理。2.Map 和 Set 概述2.1 纯 Key 模型与 Key-Value 模型搜索的数据分为两种模型纯 Key 模型只存关键字本身用来判断某个元素在不在集合中。比如查一个单词是否在词典里、快速判断某个名字是否已存在。Set 就是这种模型。Key-Value 模型存键值对每个 Key 对应一个 Value。比如统计单词出现次数 单词, 次数、梁山好汉的绰号 姓名, 绰号。Map 就是这种模型。以前常见的静态查找方式——直接遍历 O(N)、二分查找 O(logN)——都不适合动态场景边查边插入删除。Map 和 Set 正是为动态查找设计的集合容器。2.2 类继承体系总览关键区别Set 继承自 Collection只存 Key且 Key 唯一不重复Map 不继承 Collection存 Key-Value 键值对Key 唯一Value 可重复。3.Map 的使用3.1 Map 接口核心方法方法解释V get(Object key)返回 key 对应的 valueV getOrDefault(Object key, V defaultValue)key 存在返回 value不存在返回默认值V put(K key, V value)插入键值对key 已存在则替换旧 value 并返回旧值V remove(Object key)删除 key 对应的键值对返回被删除的 valueSetK keySet()返回所有 key 组成的不重复集合CollectionV values()返回所有 value 组成的可重复集合SetMap.EntryK,V entrySet()返回所有键值对映射关系集合boolean containsKey(Object key)判断是否包含某个 keyboolean containsValue(Object value)判断是否包含某个 value注意事项Map 是接口不能直接实例化需用 TreeMap 或 HashMapMap 中 Key 唯一Value 可以重复TreeMap 中 key 不能为 null否则抛 NPEvalue 可以为 nullHashMap 的 key 和 value 都可以为 nullKey 不能直接修改要改 key 只能先 remove 再重新 put。3.2 Map.Entry 键值对Map.EntryK,V 是 Map 内部用来存放 key, value 映射关系的内部类主要方法K getKey()获取 entry 中的 keyV getValue()获取 entry 中的 valueV setValue(V value)修改 value注意没有 setKey 方法遍历 Map 的标准方式就是通过 entrySet() 获取所有 Entry逐个取出 key 和 value。3.3 TreeMap 与 HashMap 的区别对比项TreeMapHashMap底层结构红黑树哈希桶数组链表/红黑树插入/删除/查找O(logN)O(1) 平均是否有序Key 按大小排序插入顺序无序线程安全不安全不安全比较要求Key 必须可比较否则 ClassCastException需覆写 equals 和 hashCode典型场景需要 Key 有序输出不关心顺序追求查找性能3.4 代码实战TreeMap 常用操作import java.util.TreeMap; import java.util.Map; public class SetMapDemo{ public static void testMap() { MapString, String m new TreeMap(); // put(key, value)插入键值对key 不存在返回 null存在则替换并返回旧值 m.put(林冲, 豹子头); m.put(鲁智深, 花和尚); m.put(武松, 行者); m.put(宋江, 及时雨); m.put(李逵, 黑旋风); System.out.println(m.size()); // 5 // get(key)key 存在返回 value不存在返回 null System.out.println(m.get(鲁智深)); // 花和尚 System.out.println(m.get(史进)); // null // getOrDefaultkey 不存在时返回默认值而非 null System.out.println(m.getOrDefault(李逵, 铁牛)); // 黑旋风key存在 System.out.println(m.getOrDefault(史进, 九纹龙)); // 九纹龙key不存在返回默认值 // containsKeyO(logN)按红黑树性质查找 System.out.println(m.containsKey(林冲)); // true System.out.println(m.containsKey(史进)); // false // containsValueO(N)需要遍历 System.out.println(m.containsValue(豹子头)); // true // 遍历所有 key for (String s : m.keySet()) { System.out.print(s ); } // 遍历所有 value for (String s : m.values()) { System.out.print(s ); } // 遍历所有键值对推荐方式 for (Map.EntryString, String entry : m.entrySet()) { System.out.println(entry.getKey() --- entry.getValue()); } } }4.Set 的使用4.1 Set 接口核心方法方法解释boolean add(E e)添加元素重复元素添加失败返回 falseboolean contains(Object o)判断 o 是否在集合中boolean remove(Object o)删除集合中的 oint size()返回元素个数boolean isEmpty()判断是否为空IteratorE iterator()返回迭代器void clear()清空集合注意事项Set 继承自 Collection只存 Key且 Key 必须唯一TreeSet 底层是用 Map 实现的——把元素作为 Key一个固定的 Object 对象作为 Value 存入 TreeMapSet 最大的功能就是去重TreeSet 不能插入 nullHashSet 可以LinkedHashSet 在 HashSet 基础上维护了一个双向链表记录元素的插入次序。4.2 TreeSet 与 HashSet 的区别对比项TreeSetHashSet底层结构红黑树哈希桶插入/删除/查找O(logN)O(1) 平均是否有序Key 有序不一定有序线程安全不安全不安全比较要求Key 必须可比较需覆写 equals 和 hashCode典型场景需要有序输出不关心顺序追求性能4.3 代码实战TreeSet 常用操作下面是一个更完整的 Set Map 综合示例覆盖了增删查改和两种遍历方式import java.util.TreeSet; import java.util.Iterator; import java.util.Set; public class SetMapDemo{ public static void testSet() { SetString s new TreeSet(); // add(key)key 不存在返回 true已存在返回 false boolean isIn s.add(apple); // true s.add(orange); s.add(peach); s.add(banana); System.out.println(s.size()); // 4 System.out.println(s); // [apple, banana, orange, peach] —— 自动排序 // 重复元素不会被添加 isIn s.add(apple); // false // contains(key)存在返回 true不存在返回 false System.out.println(s.contains(apple)); // true System.out.println(s.contains(watermelon)); // false // remove(key)存在删除成功返回 true s.remove(apple); System.out.println(s); // [banana, orange, peach] // 迭代器遍历 IteratorString it s.iterator(); while (it.hasNext()) { System.out.print(it.next() ); } } }总结与选型建议回顾全文我们从底层到上层完整走过了 Map 和 Set 的知识链路底层基石是搜索树二叉搜索树的左小右大性质支撑了查找、插入、删除的基本逻辑但普通 BST 可能退化成单支树性能从 O(logN) 掉到 O(N)红黑树通过近似平衡解决了退化问题成为 TreeMap / TreeSet 的底层实现。Map 和 Set 是两种查找模型Set 纯 Key 模型核心功能是去重和判存Map Key-Value 模型核心功能是按键查值。常用实现类的选型需求场景推荐选择理由只需要快速判重/去重不关心顺序HashSetO(1) 平均查找性能最好需要元素自动排序输出TreeSet红黑树保证 Key 有序需要记录插入顺序LinkedHashSet维护双向链表按键查值不关心顺序HashMapO(1) 平均查找需要 Key 有序遍历如按字典序TreeMap红黑树自动排序需要记录插入顺序的 MapLinkedHashMapHashMap 双向链表关于 HashMap / HashSet 的底层它们基于哈希表实现查找效率为 O(1)但哈希冲突、负载因子、扩容等原理涉及内容较多我们留到下一篇文章专门讲解。一句话总结TreeMap/TreeSet 胜在有序HashMap/HashSet 胜在快速选型时先问自己需不需要排序——需要排序选 Tree 系列追求速度选 Hash 系列。