本系列可作为JAVA学习系列的笔记文中提到的一些练习的代码小编会将代码复制下来大家复制下来就可以练习了方便大家学习。点赞关注不迷路您的点赞、关注和收藏是对小编最大的支持和鼓励系列文章目录JAVA初阶---------已更完JAVA数据结构 DAY1-集合和时空复杂度JAVA数据结构 DAY2-包装类和泛型JAVA数据结构 DAY3-List接口JAVA数据结构 DAY4-ArrayListJAVA数据结构 DAY5-LinkedListJAVA数据结构 DAY6-栈和队列JAVA数据结构 DAY7-二叉树JAVA数据结构 DAY8-堆JAVA数据结构 DAY9 equals、Comparable、Comparator 与 PriorityQueue 深度解析JAVA数据结构 DAY10-排序JAVA数据结构 DAY11-Set和Map拓展目录手把手教你用 ArrayList 实现杨辉三角从逻辑推导到每行代码详解链表高频 6 题精讲 | 从入门到熟练掌握链表操作二叉树高频题精讲 | 从入门到熟练掌握二叉树操作二叉树高频题精讲 | 从入门到熟练掌握二叉树操作2二叉树高频题精讲 | 从入门到熟练掌握二叉树操作3目录目录系列文章目录拓展目录目录前言一、前置基础二叉搜索树BST1.1 二叉搜索树的核心性质1.2 核心操作查找、插入、删除1查找2插入3删除难点1.3 性能与问题1.4 二叉搜索树的 Java 简易实现二、Map 和 Set动态查找的核心容器2.1 两种核心模型2.2 整体体系结构三、Map 接口Key-Value 键值对映射3.1 核心内部类Map.Entry3.2 Map 的常用 API3.3 TreeMap 与 HashMap 的核心区别3.4 TreeMap 实战示例四、Set 接口纯 Key 的唯一集合4.1 Set 的常用 API4.2 TreeSet 与 HashSet 的核心区别4.3 TreeSet 实战示例五、HashMap/HashSet 底层哈希表散列表5.1 哈希表的核心概念5.2 哈希冲突不可避免的问题1冲突定义2冲突的必然性5.3 降低冲突率哈希函数设计 负载因子调节1哈希函数设计原则2常用哈希函数3负载因子调节重点① 负载因子定义② 负载因子与冲突率的关系③ Java 中的负载因子5.4 解决哈希冲突闭散列 vs 开散列1闭散列开放定址法2开散列哈希桶 / 链地址法【Java 采用】① 核心思想② 实现流程③ 核心优势④ 冲突严重的解决5.5 哈希表的 Java 简易实现哈希桶5.6 哈希表的性能分析5.7 Java 中哈希表的核心注意事项六、Map/Set 的核心总结与应用场景6.1 核心总结6.2 典型应用场景6.3 经典 OJ 练习七、总结总结前言小编作为新晋码农一枚会定期整理一些写的比较好的代码作为自己的学习笔记会试着做一下批注和补充如转载或者参考他人文献会标明出处非商用如有侵权会删改欢迎大家斧正和讨论在 Java 集合框架中Map 和 Set 是处理动态查找场景的核心容器与传统的数组、链表不同它们针对高效搜索、插入、删除做了专门优化底层分别基于红黑树和哈希表实现对应 TreeMap/TreeSet、HashMap/HashSet 两大核心系列。本文将从基础的二叉搜索树出发逐步拆解 Map 和 Set 的设计思想、底层原理、常用 API 及实际应用帮你彻底掌握这一核心知识点。一、前置基础二叉搜索树BSTTreeMap 和 TreeSet 的底层是红黑树近似平衡的二叉搜索树因此理解二叉搜索树是掌握这两个集合的前提。1.1 二叉搜索树的核心性质二叉搜索树又称二叉排序树满足左子树所有节点值小于根节点值右子树所有节点值大于根节点值左右子树也分别为二叉搜索树树中节点的 key 唯一无重复。1.2 核心操作查找、插入、删除1查找从根节点开始若目标 key 等于根节点 key 则找到若小于则遍历左子树大于则遍历右子树直到节点为空未找到。时间复杂度最优 O (log₂N)完全二叉树最差 O (N)单支树。2插入树为空时直接将新节点作为根节点树非空时按查找逻辑找到插入位置父节点若 key 已存在则插入失败否则根据 key 大小插入到父节点的左 / 右子节点。3删除难点设待删除节点为cur其父节点为parent分三种情况处理cur 左子树为空直接将 cur 的右子树接在 parent 的对应位置cur 为根则根更新为 cur.rightcur 右子树为空直接将 cur 的左子树接在 parent 的对应位置cur 为根则根更新为 cur.leftcur 左右子树均存在采用替换法在 cur 的右子树中找中序第一个节点key 最小用其值覆盖 cur再删除该最小节点。1.3 性能与问题最优情况完全二叉树平均查找长度 O (log₂N)最差情况单支树退化为链表平均查找长度 O (N/2)核心问题插入次序会导致树的结构失衡性能骤降。红黑树通过颜色标记 旋转规则解决了这一问题保证树的高度始终为 O (log₂N)是 TreeMap/TreeSet 的底层实现。1.4 二叉搜索树的 Java 简易实现public class BinarySearchTree { public static class Node { int key; Node left; Node right; public Node(int key) { this.key key; } } private Node root null; // 查找 public Node search(int key) { Node 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; } // 插入 public boolean insert(int key) { if (root null) { root new Node(key); return true; } Node cur root; Node 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; } } Node node new Node(key); if (key parent.key) parent.left node; else parent.right node; return true; } // 删除需补充具体逻辑 public boolean remove(int key) { Node cur root; Node 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; // 补充三种删除情况的逻辑 return true; } }二、Map 和 Set动态查找的核心容器Map 和 Set 是为动态查找设计的集合支持随时插入、删除、查找区别于静态查找的二分查找要求序列有序不适合频繁修改适用于 “通讯录查询”“单词去重”“键值对映射” 等场景。2.1 两种核心模型Map 和 Set 的设计基于两种数据模型也是二者的核心区别纯 Key 模型Set仅存储唯一的 Key核心功能是去重 查找例如 “判断单词是否在词典中”Key-Value 模型Map存储键值对Key 唯一Value 可重复核心功能是根据 Key 查找 Value例如 “姓名对应考试成绩”。2.2 整体体系结构Map独立接口不继承 Collection实现类为 TreeMap红黑树、HashMap哈希表Set继承 Collection 接口底层基于 Map 实现将 Key 作为 Set 元素Value 为默认空对象实现类为 TreeSet红黑树、HashSet哈希表、LinkedHashSet哈希表 双向链表保留插入顺序。三、Map 接口Key-Value 键值对映射Map 是存储K,V键值对的接口Key 唯一且不可直接修改Value 可重复、可修改核心实现类为 TreeMap 和 HashMap。3.1 核心内部类Map.EntryK,VMap 内部用Map.EntryK,V封装单个键值对提供键值对的获取和修改方法无设置 Key 的方法Key 不可直接修改方法解释K getKey()返回当前 Entry 的 KeyV getValue()返回当前 Entry 的 ValueV setValue(V value)修改当前 Entry 的 Value返回旧值3.2 Map 的常用 APIMap 的核心方法围绕 Key 的增删改查和键值对遍历展开所有方法均为接口方法由实现类实现方法解释V get(Object key)根据 Key 获取 ValueKey 不存在返回 nullV getOrDefault(Object key, V defaultValue)根据 Key 获取 ValueKey 不存在返回默认值V put(K key, V value)插入 / 修改键值对Key 不存在则插入返回 nullKey 存在则修改 Value返回旧值V remove(Object key)删除 Key 对应的键值对返回该 Key 的 ValueSetK keySet()返回所有 Key 的 Set 集合Key 唯一CollectionV values()返回所有 Value 的 Collection 集合Value 可重复SetMap.EntryK,V entrySet()返回所有键值对的 Set 集合用于遍历boolean containsKey(Object key)判断是否包含指定 Keyboolean containsValue(Object value)判断是否包含指定 Value3.3 TreeMap 与 HashMap 的核心区别TreeMap 基于红黑树实现HashMap 基于哈希表实现二者特性差异显著决定了各自的应用场景特性TreeMapHashMap底层结构红黑树哈希桶数组 链表 / 红黑树时间复杂度插入 / 删除 / 查找均为 O (log₂N)插入 / 删除 / 查找均为 O (1)理想情况Key 是否有序按 Key 的自然顺序 / 自定义比较器排序无序JDK8 后为插入顺序非排序空值支持Key 不可为 nullValue 可为 nullKey 和 Value 均可为 null核心要求Key 必须实现 Comparable 接口或自定义比较器否则抛 ClassCastException自定义类型 Key 必须覆写 equals () 和 hashCode ()核心区别基于比较器实现元素排序和查找基于哈希函数计算地址实现快速查找应用场景需按 Key 有序遍历的场景无需 Key 有序追求极致查找性能的场景3.4 TreeMap 实战示例import java.util.Map; import java.util.TreeMap; public class TreeMapTest { public static void main(String[] args) { MapString, String heroMap new TreeMap(); // 插入键值对 heroMap.put(林冲, 豹子头); heroMap.put(鲁智深, 花和尚); heroMap.put(武松, 行者); heroMap.put(李逵, 黑旋风); System.out.println(集合大小 heroMap.size()); // 4 System.out.println(原始集合 heroMap); // 按Key自然排序 // 修改Value String oldValue heroMap.put(李逵, 铁牛); System.out.println(李逵旧绰号 oldValue); // 黑旋风 // 获取Value System.out.println(heroMap.get(鲁智深)); // 花和尚 System.out.println(heroMap.getOrDefault(史进, 九纹龙)); // 九纹龙 // 判断包含 System.out.println(heroMap.containsKey(林冲)); // true System.out.println(heroMap.containsValue(九纹龙)); // false // 遍历Key for (String key : heroMap.keySet()) { System.out.print(key ); } System.out.println(); // 遍历Value for (String value : heroMap.values()) { System.out.print(value ); } System.out.println(); // 遍历键值对推荐 for (Map.EntryString, String entry : heroMap.entrySet()) { System.out.println(entry.getKey() ---- entry.getValue()); } } }四、Set 接口纯 Key 的唯一集合Set 继承自 Collection 接口仅存储唯一的 Key核心功能是去重和查找底层基于 Map 实现将 Key 作为 Set 元素Value 为一个固定的空 Object核心实现类为 TreeSet 和 HashSet。4.1 Set 的常用 APISet 的方法与 Collection 接口基本一致无新增方法核心围绕元素的增删改查和去重方法解释boolean add(E e)添加元素元素已存在则添加失败返回 falseboolean remove(Object o)删除指定元素元素不存在则返回 falseboolean contains(Object o)判断集合是否包含指定元素int size()返回集合元素个数boolean isEmpty()判断集合是否为空IteratorE iterator()返回迭代器用于遍历元素void clear()清空集合boolean addAll(Collection? extends E c)将集合 c 的元素添加到 Set 中实现去重4.2 TreeSet 与 HashSet 的核心区别与 TreeMap/HashMap 的区别对应TreeSet 基于红黑树HashSet 基于哈希表LinkedHashSet 是 HashSet 的子类在哈希表基础上维护了双向链表保留元素的插入顺序特性TreeSetHashSetLinkedHashSet底层结构红黑树哈希桶哈希桶 双向链表时间复杂度O(log₂N)O(1)O(1)Key 是否有序自然排序 / 自定义排序无序按插入顺序排序空值支持Key 不可为 nullKey 可为 nullKey 可为 null核心要求Key 需实现 Comparable 接口自定义 Key 需覆写 equals () 和 hashCode ()同 HashSet应用场景需有序遍历的去重场景无需有序追求性能的去重场景需保留插入顺序的去重场景4.3 TreeSet 实战示例import java.util.Iterator; import java.util.Set; import java.util.TreeSet; public class TreeSetTest { public static void main(String[] args) { SetString fruitSet new TreeSet(); // 添加元素 fruitSet.add(apple); fruitSet.add(orange); fruitSet.add(peach); fruitSet.add(banana); System.out.println(集合大小 fruitSet.size()); // 4 System.out.println(原始集合 fruitSet); // 按自然排序 // 重复添加返回false boolean isAdd fruitSet.add(apple); System.out.println(是否添加成功 isAdd); // false // 判断包含 System.out.println(fruitSet.contains(apple)); // true System.out.println(fruitSet.contains(watermelon)); // false // 删除元素 fruitSet.remove(apple); System.out.println(删除后集合 fruitSet); // [banana, orange, peach] // 迭代器遍历 IteratorString it fruitSet.iterator(); while (it.hasNext()) { System.out.print(it.next() ); } } }五、HashMap/HashSet 底层哈希表散列表HashMap 和 HashSet 的底层是哈希表是实现 O (1) 时间复杂度查找的核心也是 Java 集合中最常用的容器其设计围绕哈希函数、冲突解决、负载因子三大核心展开。5.1 哈希表的核心概念哈希表的核心思想是通过哈希函数hashFunc让元素的Key与存储位置建立一一映射实现一次计算直接找到元素无需比较。哈希函数将 Key 转换为哈希表数组下标的函数例如hash(key) key % 数组长度哈希表根据哈希函数构造的存储结构底层为数组哈希桶每个数组元素对应一个链表 / 红黑树解决冲突核心优势插入、删除、查找的时间复杂度均为 O (1)理想情况无冲突。5.2 哈希冲突不可避免的问题1冲突定义两个不同的 Keyki ≠ kj通过哈希函数计算得到相同的哈希地址hash(ki) hash(kj)该现象称为哈希冲突 / 哈希碰撞这两个 Key 称为同义词。2冲突的必然性哈希表底层数组的容量是有限的而待存储的 Key 数量是无限的根据鸽巢原理冲突必然发生我们能做的是降低冲突率。5.3 降低冲突率哈希函数设计 负载因子调节1哈希函数设计原则定义域包含所有待存储 Key值域在0 ~ 数组长度-1之间计算出的地址均匀分布在数组中减少冲突函数计算简单提升效率。2常用哈希函数函数名称实现方式适用场景直接定制法Hash(Key) A*Key B线性函数Key 范围小且连续的场景除留余数法Hash(Key) Key % pp 为≤数组长度的质数最常用通用场景平方取中法将 Key 平方后抽取中间几位作为地址未知 Key 分布Key 位数较少的场景折叠法将 Key 分割为若干部分叠加求和后取后几位Key 位数较多的场景随机数法Hash(Key) random(Key)Key 长度不固定的场景数学分析法抽取 Key 中分布均匀的几位作为地址已知 Key 分布的场景如手机号Java 中哈希函数自定义类型需覆写hashCode()方法JDK 会对hashCode()的结果进行二次哈希减少哈希冲突。3负载因子调节重点① 负载因子定义负载因子α 填入表中的元素个数 / 哈希表数组长度是哈希表装满程度的标志。② 负载因子与冲突率的关系α越大哈希表中元素越多冲突率越高α越小元素越少冲突率越低但空间利用率也越低。③ Java 中的负载因子Java 中 HashMap 的默认负载因子为0.75当实际负载因子超过 0.75 时会触发数组扩容扩容为原长度的 2 倍通过降低负载因子变相降低冲突率。注意开放定址法的负载因子需控制在 0.7~0.8 以下否则 CPU 缓存不命中率会指数级上升。5.4 解决哈希冲突闭散列 vs 开散列当哈希冲突发生时有两种核心解决方式Java 中 HashMap 采用开散列哈希桶。1闭散列开放定址法当发生冲突时在哈希表中寻找下一个空位置存放元素常用两种探测方式线性探测从冲突位置开始依次向后查找空位置例如Hi (H0 i) % 数组长度i1,2,3...缺陷容易产生数据堆积冲突位置附近的位置被连续占用进一步提高冲突率删除不能直接物理删除需采用伪删除标记为已删除否则会影响后续查找。二次探测从冲突位置开始按平方数查找空位置例如Hi (H0 ± i²) % 数组长度i1,2,3...优势解决了数据堆积问题冲突分布更均匀要求数组长度为质数且负载因子≤0.5否则可能找不到空位置。闭散列整体缺陷空间利用率低是哈希表的次要解决冲突方式。2开散列哈希桶 / 链地址法【Java 采用】① 核心思想哈希表底层为数组哈希桶每个数组元素对应一个单链表JDK8 后当链表长度≥8 且数组长度≥64 时转为红黑树发生冲突的 Key被放入同一个数组元素对应的链表 / 红黑树中。② 实现流程通过哈希函数计算 Key 的哈希地址得到数组下标若该下标对应的桶为空直接将元素作为链表头节点存入若该桶已存在元素将元素添加到链表尾部JDK8/ 头部JDK7查找时先计算下标再在对应桶的链表 / 红黑树中查找 Key。③ 核心优势空间利用率高无需预留大量空位置无数据堆积问题冲突仅影响单个桶支持物理删除不影响其他元素查找。④ 冲突严重的解决若单个桶的冲突过于严重链表过长可将桶的底层结构从链表改为哈希表或红黑树将大集合的搜索问题转化为小集合的搜索问题。5.5 哈希表的 Java 简易实现哈希桶public class HashBucket { // 哈希桶节点存储Key-Value private static class Node { private int key; private 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; // 负载因子阈值 // 构造方法初始化数组长度为8 public HashBucket() { array new Node[8]; size 0; } // 插入/修改键值对 public int put(int key, int value) { int index key % array.length; // 遍历链表若Key存在则修改Value for (Node cur array[index]; cur ! null; cur cur.next) { if (cur.key key) { int oldValue cur.value; cur.value value; return oldValue; } } // Key不存在头插法插入新节点 Node node new Node(key, value); node.next array[index]; array[index] node; size; // 负载因子超过阈值扩容 if (loadFactor() LOAD_FACTOR) { resize(); } 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 index cur.key % newArray.length; // 头插法插入新数组 cur.next newArray[index]; newArray[index] cur; cur next; } } array newArray; // 替换为新数组 } // 计算当前负载因子 private double loadFactor() { return size * 1.0 / array.length; } // 根据Key获取Value public int get(int key) { int index key % array.length; Node cur array[index]; while (cur ! null) { if (cur.key key) { return cur.value; } cur cur.next; } return -1; // Key不存在 } }5.6 哈希表的性能分析在实际使用中哈希表的冲突率被控制在较低水平每个桶的链表 / 红黑树长度为常数因此插入、删除、查找的平均时间复杂度为 O (1)当冲突严重时如哈希函数设计不合理时间复杂度会退化为 O (log₂N)红黑树或 O (N)链表。5.7 Java 中哈希表的核心注意事项自定义类型作为 HashMap 的 Key 或 HashSet 的元素时必须同时覆写 equals () 和 hashCode () 方法且满足equals () 相等的对象hashCode () 必须相等保证相同的对象映射到同一个哈希桶hashCode () 相等的对象equals () 不一定相等允许哈希冲突冲突后通过 equals () 判断是否为同一对象。若仅覆写 equals ()未覆写 hashCode ()会导致相同的对象生成不同的哈希地址无法正确去重和查找。六、Map/Set 的核心总结与应用场景6.1 核心总结Tree 系列TreeMap/TreeSet底层红黑树平衡二叉搜索树特性Key 有序时间复杂度 O (log₂N)Key 不可为 nullTreeMap/TreeSet要求Key 需实现 Comparable 接口或自定义比较器。Hash 系列HashMap/HashSet底层哈希桶数组 链表 / 红黑树特性Key 无序时间复杂度 O (1)Key/Value 可为 nullHashMap/HashSet要求自定义 Key 需覆写 equals () 和 hashCode ()。LinkedHashSet底层哈希桶 双向链表特性保留插入顺序时间复杂度 O (1)兼具 HashSet 的性能和有序性。6.2 典型应用场景场景推荐容器原因按姓名 / 学号有序查询信息TreeMap/TreeSet需 Key 有序遍历通讯录快速查询姓名→电话HashMap无需有序追求 O (1) 查找性能数组 / 集合去重HashSet/LinkedHashSet高效去重LinkedHashSet 可保留插入顺序统计单词出现次数HashMapString, IntegerKey 为单词Value 为次数快速统计和查询缓存系统Key→数据HashMap高速存取符合缓存的性能要求6.3 经典 OJ 练习掌握 Map/Set 后可解决以下经典算法题巩固知识点只出现一次的数字利用 HashSet 的去重特性宝石与石头利用 HashSet 存储宝石快速判断石头是否为宝石坏键盘打字利用 HashSet 存储正常按键筛选坏键前 K 个高频单词利用 HashMap 统计频率结合排序 / 堆实现复制带随机指针的链表利用 HashMap 建立原节点→新节点的映射。注这里将会更新一个链接包含OJ练习的记录和联系网址链接。七、总结Map 和 Set 是 Java 集合框架中处理动态查找的核心其设计分别基于红黑树和哈希表两大数据结构对应 Tree 系列和 Hash 系列二者各有优劣若需要Key 有序选择 TreeMap/TreeSet牺牲一点性能换取有序性若追求极致性能无需有序选择 HashMap/HashSet是日常开发的首选若需要保留插入顺序且高效选择 LinkedHashSet/LinkedHashMap。掌握 Map/Set 的关键不仅要熟记 API更要理解其底层原理二叉搜索树、红黑树、哈希表尤其是哈希表的哈希函数、冲突解决、负载因子这也是面试的高频考点。只有理解底层才能在实际开发中选择合适的容器写出高效、健壮的代码。总结以上就是今天要讲的内容本文简单记录了java数据结构仅作为一份简单的笔记使用大家根据注释理解您的点赞关注收藏就是对小编最大的鼓励
JAVA数据结构 DAY11-Set和Map
本系列可作为JAVA学习系列的笔记文中提到的一些练习的代码小编会将代码复制下来大家复制下来就可以练习了方便大家学习。点赞关注不迷路您的点赞、关注和收藏是对小编最大的支持和鼓励系列文章目录JAVA初阶---------已更完JAVA数据结构 DAY1-集合和时空复杂度JAVA数据结构 DAY2-包装类和泛型JAVA数据结构 DAY3-List接口JAVA数据结构 DAY4-ArrayListJAVA数据结构 DAY5-LinkedListJAVA数据结构 DAY6-栈和队列JAVA数据结构 DAY7-二叉树JAVA数据结构 DAY8-堆JAVA数据结构 DAY9 equals、Comparable、Comparator 与 PriorityQueue 深度解析JAVA数据结构 DAY10-排序JAVA数据结构 DAY11-Set和Map拓展目录手把手教你用 ArrayList 实现杨辉三角从逻辑推导到每行代码详解链表高频 6 题精讲 | 从入门到熟练掌握链表操作二叉树高频题精讲 | 从入门到熟练掌握二叉树操作二叉树高频题精讲 | 从入门到熟练掌握二叉树操作2二叉树高频题精讲 | 从入门到熟练掌握二叉树操作3目录目录系列文章目录拓展目录目录前言一、前置基础二叉搜索树BST1.1 二叉搜索树的核心性质1.2 核心操作查找、插入、删除1查找2插入3删除难点1.3 性能与问题1.4 二叉搜索树的 Java 简易实现二、Map 和 Set动态查找的核心容器2.1 两种核心模型2.2 整体体系结构三、Map 接口Key-Value 键值对映射3.1 核心内部类Map.Entry3.2 Map 的常用 API3.3 TreeMap 与 HashMap 的核心区别3.4 TreeMap 实战示例四、Set 接口纯 Key 的唯一集合4.1 Set 的常用 API4.2 TreeSet 与 HashSet 的核心区别4.3 TreeSet 实战示例五、HashMap/HashSet 底层哈希表散列表5.1 哈希表的核心概念5.2 哈希冲突不可避免的问题1冲突定义2冲突的必然性5.3 降低冲突率哈希函数设计 负载因子调节1哈希函数设计原则2常用哈希函数3负载因子调节重点① 负载因子定义② 负载因子与冲突率的关系③ Java 中的负载因子5.4 解决哈希冲突闭散列 vs 开散列1闭散列开放定址法2开散列哈希桶 / 链地址法【Java 采用】① 核心思想② 实现流程③ 核心优势④ 冲突严重的解决5.5 哈希表的 Java 简易实现哈希桶5.6 哈希表的性能分析5.7 Java 中哈希表的核心注意事项六、Map/Set 的核心总结与应用场景6.1 核心总结6.2 典型应用场景6.3 经典 OJ 练习七、总结总结前言小编作为新晋码农一枚会定期整理一些写的比较好的代码作为自己的学习笔记会试着做一下批注和补充如转载或者参考他人文献会标明出处非商用如有侵权会删改欢迎大家斧正和讨论在 Java 集合框架中Map 和 Set 是处理动态查找场景的核心容器与传统的数组、链表不同它们针对高效搜索、插入、删除做了专门优化底层分别基于红黑树和哈希表实现对应 TreeMap/TreeSet、HashMap/HashSet 两大核心系列。本文将从基础的二叉搜索树出发逐步拆解 Map 和 Set 的设计思想、底层原理、常用 API 及实际应用帮你彻底掌握这一核心知识点。一、前置基础二叉搜索树BSTTreeMap 和 TreeSet 的底层是红黑树近似平衡的二叉搜索树因此理解二叉搜索树是掌握这两个集合的前提。1.1 二叉搜索树的核心性质二叉搜索树又称二叉排序树满足左子树所有节点值小于根节点值右子树所有节点值大于根节点值左右子树也分别为二叉搜索树树中节点的 key 唯一无重复。1.2 核心操作查找、插入、删除1查找从根节点开始若目标 key 等于根节点 key 则找到若小于则遍历左子树大于则遍历右子树直到节点为空未找到。时间复杂度最优 O (log₂N)完全二叉树最差 O (N)单支树。2插入树为空时直接将新节点作为根节点树非空时按查找逻辑找到插入位置父节点若 key 已存在则插入失败否则根据 key 大小插入到父节点的左 / 右子节点。3删除难点设待删除节点为cur其父节点为parent分三种情况处理cur 左子树为空直接将 cur 的右子树接在 parent 的对应位置cur 为根则根更新为 cur.rightcur 右子树为空直接将 cur 的左子树接在 parent 的对应位置cur 为根则根更新为 cur.leftcur 左右子树均存在采用替换法在 cur 的右子树中找中序第一个节点key 最小用其值覆盖 cur再删除该最小节点。1.3 性能与问题最优情况完全二叉树平均查找长度 O (log₂N)最差情况单支树退化为链表平均查找长度 O (N/2)核心问题插入次序会导致树的结构失衡性能骤降。红黑树通过颜色标记 旋转规则解决了这一问题保证树的高度始终为 O (log₂N)是 TreeMap/TreeSet 的底层实现。1.4 二叉搜索树的 Java 简易实现public class BinarySearchTree { public static class Node { int key; Node left; Node right; public Node(int key) { this.key key; } } private Node root null; // 查找 public Node search(int key) { Node 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; } // 插入 public boolean insert(int key) { if (root null) { root new Node(key); return true; } Node cur root; Node 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; } } Node node new Node(key); if (key parent.key) parent.left node; else parent.right node; return true; } // 删除需补充具体逻辑 public boolean remove(int key) { Node cur root; Node 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; // 补充三种删除情况的逻辑 return true; } }二、Map 和 Set动态查找的核心容器Map 和 Set 是为动态查找设计的集合支持随时插入、删除、查找区别于静态查找的二分查找要求序列有序不适合频繁修改适用于 “通讯录查询”“单词去重”“键值对映射” 等场景。2.1 两种核心模型Map 和 Set 的设计基于两种数据模型也是二者的核心区别纯 Key 模型Set仅存储唯一的 Key核心功能是去重 查找例如 “判断单词是否在词典中”Key-Value 模型Map存储键值对Key 唯一Value 可重复核心功能是根据 Key 查找 Value例如 “姓名对应考试成绩”。2.2 整体体系结构Map独立接口不继承 Collection实现类为 TreeMap红黑树、HashMap哈希表Set继承 Collection 接口底层基于 Map 实现将 Key 作为 Set 元素Value 为默认空对象实现类为 TreeSet红黑树、HashSet哈希表、LinkedHashSet哈希表 双向链表保留插入顺序。三、Map 接口Key-Value 键值对映射Map 是存储K,V键值对的接口Key 唯一且不可直接修改Value 可重复、可修改核心实现类为 TreeMap 和 HashMap。3.1 核心内部类Map.EntryK,VMap 内部用Map.EntryK,V封装单个键值对提供键值对的获取和修改方法无设置 Key 的方法Key 不可直接修改方法解释K getKey()返回当前 Entry 的 KeyV getValue()返回当前 Entry 的 ValueV setValue(V value)修改当前 Entry 的 Value返回旧值3.2 Map 的常用 APIMap 的核心方法围绕 Key 的增删改查和键值对遍历展开所有方法均为接口方法由实现类实现方法解释V get(Object key)根据 Key 获取 ValueKey 不存在返回 nullV getOrDefault(Object key, V defaultValue)根据 Key 获取 ValueKey 不存在返回默认值V put(K key, V value)插入 / 修改键值对Key 不存在则插入返回 nullKey 存在则修改 Value返回旧值V remove(Object key)删除 Key 对应的键值对返回该 Key 的 ValueSetK keySet()返回所有 Key 的 Set 集合Key 唯一CollectionV values()返回所有 Value 的 Collection 集合Value 可重复SetMap.EntryK,V entrySet()返回所有键值对的 Set 集合用于遍历boolean containsKey(Object key)判断是否包含指定 Keyboolean containsValue(Object value)判断是否包含指定 Value3.3 TreeMap 与 HashMap 的核心区别TreeMap 基于红黑树实现HashMap 基于哈希表实现二者特性差异显著决定了各自的应用场景特性TreeMapHashMap底层结构红黑树哈希桶数组 链表 / 红黑树时间复杂度插入 / 删除 / 查找均为 O (log₂N)插入 / 删除 / 查找均为 O (1)理想情况Key 是否有序按 Key 的自然顺序 / 自定义比较器排序无序JDK8 后为插入顺序非排序空值支持Key 不可为 nullValue 可为 nullKey 和 Value 均可为 null核心要求Key 必须实现 Comparable 接口或自定义比较器否则抛 ClassCastException自定义类型 Key 必须覆写 equals () 和 hashCode ()核心区别基于比较器实现元素排序和查找基于哈希函数计算地址实现快速查找应用场景需按 Key 有序遍历的场景无需 Key 有序追求极致查找性能的场景3.4 TreeMap 实战示例import java.util.Map; import java.util.TreeMap; public class TreeMapTest { public static void main(String[] args) { MapString, String heroMap new TreeMap(); // 插入键值对 heroMap.put(林冲, 豹子头); heroMap.put(鲁智深, 花和尚); heroMap.put(武松, 行者); heroMap.put(李逵, 黑旋风); System.out.println(集合大小 heroMap.size()); // 4 System.out.println(原始集合 heroMap); // 按Key自然排序 // 修改Value String oldValue heroMap.put(李逵, 铁牛); System.out.println(李逵旧绰号 oldValue); // 黑旋风 // 获取Value System.out.println(heroMap.get(鲁智深)); // 花和尚 System.out.println(heroMap.getOrDefault(史进, 九纹龙)); // 九纹龙 // 判断包含 System.out.println(heroMap.containsKey(林冲)); // true System.out.println(heroMap.containsValue(九纹龙)); // false // 遍历Key for (String key : heroMap.keySet()) { System.out.print(key ); } System.out.println(); // 遍历Value for (String value : heroMap.values()) { System.out.print(value ); } System.out.println(); // 遍历键值对推荐 for (Map.EntryString, String entry : heroMap.entrySet()) { System.out.println(entry.getKey() ---- entry.getValue()); } } }四、Set 接口纯 Key 的唯一集合Set 继承自 Collection 接口仅存储唯一的 Key核心功能是去重和查找底层基于 Map 实现将 Key 作为 Set 元素Value 为一个固定的空 Object核心实现类为 TreeSet 和 HashSet。4.1 Set 的常用 APISet 的方法与 Collection 接口基本一致无新增方法核心围绕元素的增删改查和去重方法解释boolean add(E e)添加元素元素已存在则添加失败返回 falseboolean remove(Object o)删除指定元素元素不存在则返回 falseboolean contains(Object o)判断集合是否包含指定元素int size()返回集合元素个数boolean isEmpty()判断集合是否为空IteratorE iterator()返回迭代器用于遍历元素void clear()清空集合boolean addAll(Collection? extends E c)将集合 c 的元素添加到 Set 中实现去重4.2 TreeSet 与 HashSet 的核心区别与 TreeMap/HashMap 的区别对应TreeSet 基于红黑树HashSet 基于哈希表LinkedHashSet 是 HashSet 的子类在哈希表基础上维护了双向链表保留元素的插入顺序特性TreeSetHashSetLinkedHashSet底层结构红黑树哈希桶哈希桶 双向链表时间复杂度O(log₂N)O(1)O(1)Key 是否有序自然排序 / 自定义排序无序按插入顺序排序空值支持Key 不可为 nullKey 可为 nullKey 可为 null核心要求Key 需实现 Comparable 接口自定义 Key 需覆写 equals () 和 hashCode ()同 HashSet应用场景需有序遍历的去重场景无需有序追求性能的去重场景需保留插入顺序的去重场景4.3 TreeSet 实战示例import java.util.Iterator; import java.util.Set; import java.util.TreeSet; public class TreeSetTest { public static void main(String[] args) { SetString fruitSet new TreeSet(); // 添加元素 fruitSet.add(apple); fruitSet.add(orange); fruitSet.add(peach); fruitSet.add(banana); System.out.println(集合大小 fruitSet.size()); // 4 System.out.println(原始集合 fruitSet); // 按自然排序 // 重复添加返回false boolean isAdd fruitSet.add(apple); System.out.println(是否添加成功 isAdd); // false // 判断包含 System.out.println(fruitSet.contains(apple)); // true System.out.println(fruitSet.contains(watermelon)); // false // 删除元素 fruitSet.remove(apple); System.out.println(删除后集合 fruitSet); // [banana, orange, peach] // 迭代器遍历 IteratorString it fruitSet.iterator(); while (it.hasNext()) { System.out.print(it.next() ); } } }五、HashMap/HashSet 底层哈希表散列表HashMap 和 HashSet 的底层是哈希表是实现 O (1) 时间复杂度查找的核心也是 Java 集合中最常用的容器其设计围绕哈希函数、冲突解决、负载因子三大核心展开。5.1 哈希表的核心概念哈希表的核心思想是通过哈希函数hashFunc让元素的Key与存储位置建立一一映射实现一次计算直接找到元素无需比较。哈希函数将 Key 转换为哈希表数组下标的函数例如hash(key) key % 数组长度哈希表根据哈希函数构造的存储结构底层为数组哈希桶每个数组元素对应一个链表 / 红黑树解决冲突核心优势插入、删除、查找的时间复杂度均为 O (1)理想情况无冲突。5.2 哈希冲突不可避免的问题1冲突定义两个不同的 Keyki ≠ kj通过哈希函数计算得到相同的哈希地址hash(ki) hash(kj)该现象称为哈希冲突 / 哈希碰撞这两个 Key 称为同义词。2冲突的必然性哈希表底层数组的容量是有限的而待存储的 Key 数量是无限的根据鸽巢原理冲突必然发生我们能做的是降低冲突率。5.3 降低冲突率哈希函数设计 负载因子调节1哈希函数设计原则定义域包含所有待存储 Key值域在0 ~ 数组长度-1之间计算出的地址均匀分布在数组中减少冲突函数计算简单提升效率。2常用哈希函数函数名称实现方式适用场景直接定制法Hash(Key) A*Key B线性函数Key 范围小且连续的场景除留余数法Hash(Key) Key % pp 为≤数组长度的质数最常用通用场景平方取中法将 Key 平方后抽取中间几位作为地址未知 Key 分布Key 位数较少的场景折叠法将 Key 分割为若干部分叠加求和后取后几位Key 位数较多的场景随机数法Hash(Key) random(Key)Key 长度不固定的场景数学分析法抽取 Key 中分布均匀的几位作为地址已知 Key 分布的场景如手机号Java 中哈希函数自定义类型需覆写hashCode()方法JDK 会对hashCode()的结果进行二次哈希减少哈希冲突。3负载因子调节重点① 负载因子定义负载因子α 填入表中的元素个数 / 哈希表数组长度是哈希表装满程度的标志。② 负载因子与冲突率的关系α越大哈希表中元素越多冲突率越高α越小元素越少冲突率越低但空间利用率也越低。③ Java 中的负载因子Java 中 HashMap 的默认负载因子为0.75当实际负载因子超过 0.75 时会触发数组扩容扩容为原长度的 2 倍通过降低负载因子变相降低冲突率。注意开放定址法的负载因子需控制在 0.7~0.8 以下否则 CPU 缓存不命中率会指数级上升。5.4 解决哈希冲突闭散列 vs 开散列当哈希冲突发生时有两种核心解决方式Java 中 HashMap 采用开散列哈希桶。1闭散列开放定址法当发生冲突时在哈希表中寻找下一个空位置存放元素常用两种探测方式线性探测从冲突位置开始依次向后查找空位置例如Hi (H0 i) % 数组长度i1,2,3...缺陷容易产生数据堆积冲突位置附近的位置被连续占用进一步提高冲突率删除不能直接物理删除需采用伪删除标记为已删除否则会影响后续查找。二次探测从冲突位置开始按平方数查找空位置例如Hi (H0 ± i²) % 数组长度i1,2,3...优势解决了数据堆积问题冲突分布更均匀要求数组长度为质数且负载因子≤0.5否则可能找不到空位置。闭散列整体缺陷空间利用率低是哈希表的次要解决冲突方式。2开散列哈希桶 / 链地址法【Java 采用】① 核心思想哈希表底层为数组哈希桶每个数组元素对应一个单链表JDK8 后当链表长度≥8 且数组长度≥64 时转为红黑树发生冲突的 Key被放入同一个数组元素对应的链表 / 红黑树中。② 实现流程通过哈希函数计算 Key 的哈希地址得到数组下标若该下标对应的桶为空直接将元素作为链表头节点存入若该桶已存在元素将元素添加到链表尾部JDK8/ 头部JDK7查找时先计算下标再在对应桶的链表 / 红黑树中查找 Key。③ 核心优势空间利用率高无需预留大量空位置无数据堆积问题冲突仅影响单个桶支持物理删除不影响其他元素查找。④ 冲突严重的解决若单个桶的冲突过于严重链表过长可将桶的底层结构从链表改为哈希表或红黑树将大集合的搜索问题转化为小集合的搜索问题。5.5 哈希表的 Java 简易实现哈希桶public class HashBucket { // 哈希桶节点存储Key-Value private static class Node { private int key; private 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; // 负载因子阈值 // 构造方法初始化数组长度为8 public HashBucket() { array new Node[8]; size 0; } // 插入/修改键值对 public int put(int key, int value) { int index key % array.length; // 遍历链表若Key存在则修改Value for (Node cur array[index]; cur ! null; cur cur.next) { if (cur.key key) { int oldValue cur.value; cur.value value; return oldValue; } } // Key不存在头插法插入新节点 Node node new Node(key, value); node.next array[index]; array[index] node; size; // 负载因子超过阈值扩容 if (loadFactor() LOAD_FACTOR) { resize(); } 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 index cur.key % newArray.length; // 头插法插入新数组 cur.next newArray[index]; newArray[index] cur; cur next; } } array newArray; // 替换为新数组 } // 计算当前负载因子 private double loadFactor() { return size * 1.0 / array.length; } // 根据Key获取Value public int get(int key) { int index key % array.length; Node cur array[index]; while (cur ! null) { if (cur.key key) { return cur.value; } cur cur.next; } return -1; // Key不存在 } }5.6 哈希表的性能分析在实际使用中哈希表的冲突率被控制在较低水平每个桶的链表 / 红黑树长度为常数因此插入、删除、查找的平均时间复杂度为 O (1)当冲突严重时如哈希函数设计不合理时间复杂度会退化为 O (log₂N)红黑树或 O (N)链表。5.7 Java 中哈希表的核心注意事项自定义类型作为 HashMap 的 Key 或 HashSet 的元素时必须同时覆写 equals () 和 hashCode () 方法且满足equals () 相等的对象hashCode () 必须相等保证相同的对象映射到同一个哈希桶hashCode () 相等的对象equals () 不一定相等允许哈希冲突冲突后通过 equals () 判断是否为同一对象。若仅覆写 equals ()未覆写 hashCode ()会导致相同的对象生成不同的哈希地址无法正确去重和查找。六、Map/Set 的核心总结与应用场景6.1 核心总结Tree 系列TreeMap/TreeSet底层红黑树平衡二叉搜索树特性Key 有序时间复杂度 O (log₂N)Key 不可为 nullTreeMap/TreeSet要求Key 需实现 Comparable 接口或自定义比较器。Hash 系列HashMap/HashSet底层哈希桶数组 链表 / 红黑树特性Key 无序时间复杂度 O (1)Key/Value 可为 nullHashMap/HashSet要求自定义 Key 需覆写 equals () 和 hashCode ()。LinkedHashSet底层哈希桶 双向链表特性保留插入顺序时间复杂度 O (1)兼具 HashSet 的性能和有序性。6.2 典型应用场景场景推荐容器原因按姓名 / 学号有序查询信息TreeMap/TreeSet需 Key 有序遍历通讯录快速查询姓名→电话HashMap无需有序追求 O (1) 查找性能数组 / 集合去重HashSet/LinkedHashSet高效去重LinkedHashSet 可保留插入顺序统计单词出现次数HashMapString, IntegerKey 为单词Value 为次数快速统计和查询缓存系统Key→数据HashMap高速存取符合缓存的性能要求6.3 经典 OJ 练习掌握 Map/Set 后可解决以下经典算法题巩固知识点只出现一次的数字利用 HashSet 的去重特性宝石与石头利用 HashSet 存储宝石快速判断石头是否为宝石坏键盘打字利用 HashSet 存储正常按键筛选坏键前 K 个高频单词利用 HashMap 统计频率结合排序 / 堆实现复制带随机指针的链表利用 HashMap 建立原节点→新节点的映射。注这里将会更新一个链接包含OJ练习的记录和联系网址链接。七、总结Map 和 Set 是 Java 集合框架中处理动态查找的核心其设计分别基于红黑树和哈希表两大数据结构对应 Tree 系列和 Hash 系列二者各有优劣若需要Key 有序选择 TreeMap/TreeSet牺牲一点性能换取有序性若追求极致性能无需有序选择 HashMap/HashSet是日常开发的首选若需要保留插入顺序且高效选择 LinkedHashSet/LinkedHashMap。掌握 Map/Set 的关键不仅要熟记 API更要理解其底层原理二叉搜索树、红黑树、哈希表尤其是哈希表的哈希函数、冲突解决、负载因子这也是面试的高频考点。只有理解底层才能在实际开发中选择合适的容器写出高效、健壮的代码。总结以上就是今天要讲的内容本文简单记录了java数据结构仅作为一份简单的笔记使用大家根据注释理解您的点赞关注收藏就是对小编最大的鼓励
