news 2026/6/15 13:27:01

双列集合HashMap linkHashMap和TreeMap的基本使用和源码剖析:只看这一篇就够了！

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
双列集合HashMap linkHashMap和TreeMap的基本使用和源码剖析:只看这一篇就够了！

目录

一、Map集合的核心概念

一、Map 集合的核心概念

二、Map 的常用实现类

三、Map 的核心注意点

二、HashMap linkHashMap和TreeMap的使用

一、核心特性对比

二、基本使用示例

1. HashMap（无序，高效）

2. LinkedHashMap（保证插入顺序）

3. TreeMap（按 key 排序）

三、适用场景

总结

三、HashMap linkHashMap和TreeMap源码剖析

一、HashMap 源码核心剖析

1. 核心成员变量

2. 核心内部类（Node & TreeNode）

3. 核心方法：put 方法（插入元素）

4. 核心方法：resize 方法（扩容）

二、LinkedHashMap 源码核心剖析

1. 核心成员变量 & 内部类

2. 核心特性实现：重写关键方法

三、TreeMap 源码核心剖析

1. 核心成员变量

2. 核心内部类（红黑树节点）

3. 核心方法：put 方法

4. 红黑树平衡调整（fixAfterInsertion）

总结

四、总结

HashMap linkHashMap和TreeMap是java中Map集合非常重要的双列集合,了解其基本使用和源码的内容,有助于我们加深对java集合的理解以及其对我们在后续面试找工作方面也有着巨大的作用,那么话不多说,让我们开始这趟旅程吧。

一、Map集合的核心概念

  • 一、Map 集合的核心概念

    Map 是 Java 集合框架中双列集合的顶层接口（java.util.Map），和 List/Set（单列集合）不同，它存储的是键值对（Key-Value）数据，核心特点：

  • 键（Key）唯一：同一个 Map 中不能有重复的 Key（如果重复放入相同 Key，新的 Value 会覆盖旧的）；
  • 值（Value）可重复：不同的 Key 可以对应相同的 Value；
  • Key 和 Value 都可以是任意引用类型（基本类型会自动装箱为包装类，如 int → Integer）；
  • 可以把 Map 理解为 “字典”：Key 是 “单词”，Value 是 “单词的解释”，通过单词能快速找到解释。

  • 二、Map 的常用实现类

    日常开发中不会直接用 Map 接口，而是用它的实现类，最常用的有 3 种：

    实现类核心特点适用场景
    HashMap基于哈希表实现，无序，查询 / 增删效率高（O (1)），线程不安全绝大多数日常场景（非并发）
    LinkedHashMap继承 HashMap，底层维护链表，能保留插入顺序需要按插入顺序遍历键值对
    TreeMap基于红黑树实现，会按 Key 的自然顺序（或自定义比较器）排序，线程不安全需要对 Key 排序的场景
    Hashtable早期实现，线程安全但效率低，不允许 Key/Value 为 null基本被 ConcurrentHashM

  • 三、Map 的核心注意点

  • HashMap 的 Key 为什么能保证唯一？Key 的唯一性依赖hashCode()和equals()方法：

    • 先通过hashCode()计算哈希值，确定存储位置；
    • 如果哈希值相同，再通过equals()比较内容，确保 Key 唯一。所以自定义类作为 HashMap 的 Key 时，必须重写hashCode()和equals()，否则可能出现重复 Key。

  • null 值处理：

    • HashMap 允许 Key 和 Value 为 null（但 Key 只能有一个 null）；
    • Hashtable 不允许 Key/Value 为 null，否则抛空指针异常。

  • 线程安全：

    • HashMap/LinkedHashMap/TreeMap 都是线程不安全的，多线程环境下使用会有并发问题；
    • 并发场景用java.util.concurrent.ConcurrentHashMap（替代 Hashtable，效率更高）。

二、HashMap linkHashMap和TreeMap的使用

一、核心特性对比

在开始使用前，先明确三者的核心区别，这能帮你快速选择合适的 Map：

特性HashMapLinkedHashMapTreeMap
底层实现哈希表（数组 + 链表 / 红黑树）哈希表 + 双向链表红黑树（自平衡排序二叉树）
有序性无序（不保证插入 / 遍历顺序）有序（保证插入顺序）有序（按 key 自然排序 / 自定义排序）
允许 null key/value允许（仅 1 个 null key）允许（仅 1 个 null key）不允许 null key（会抛 NPE）
线程安全非线程安全非线程安全非线程安全
查找 / 插入效率高（O (1)）高（略低于 HashMap）中（O (log n)）

二、基本使用示例

1. HashMap（无序，高效）
import java.util.HashMap; import java.util.Map; import java.util.Set; public class HashMapDemo { public static void main(String[] args) { // 1. 创建 HashMap 对象（key 为 String，value 为 Integer） Map<String, Integer> hashMap = new HashMap<>(); // 2. 新增元素（put） hashMap.put("苹果", 10); hashMap.put("香蕉", 5); hashMap.put("橙子", 8); hashMap.put(null, 0); // 允许 null key System.out.println("初始 HashMap：" + hashMap); // 输出顺序不固定 // 3. 修改元素（重复 put 同一个 key 会覆盖 value） hashMap.put("香蕉", 7); System.out.println("修改后 HashMap：" + hashMap); // 4. 查询元素（get） int appleNum = hashMap.get("苹果"); System.out.println("苹果的数量：" + appleNum); // 查找不存在的 key，返回 null Integer grapeNum = hashMap.get("葡萄"); System.out.println("葡萄的数量：" + grapeNum); // 5. 删除元素（remove） hashMap.remove(null); System.out.println("删除 null 后：" + hashMap); // 6. 遍历（推荐 entrySet 方式，效率更高） Set<Map.Entry<String, Integer>> entrySet = hashMap.entrySet(); for (Map.Entry<String, Integer> entry : entrySet) { System.out.println("key：" + entry.getKey() + "，value：" + entry.getValue()); } } }
2. LinkedHashMap（保证插入顺序）

LinkedHashMap 是 HashMap 的子类，用法几乎一致，核心区别是遍历顺序和插入顺序一致：

import java.util.LinkedHashMap; import java.util.Map; public class LinkedHashMapDemo { public static void main(String[] args) { // 1. 创建 LinkedHashMap 对象 Map<String, Integer> linkedHashMap = new LinkedHashMap<>(); // 2. 按顺序新增元素 linkedHashMap.put("苹果", 10); linkedHashMap.put("香蕉", 5); linkedHashMap.put("橙子", 8); // 输出顺序和插入顺序完全一致（苹果→香蕉→橙子） System.out.println("LinkedHashMap：" + linkedHashMap); // 3. 其他操作（修改、删除、遍历）和 HashMap 完全相同 linkedHashMap.put("香蕉", 7); System.out.println("修改后 LinkedHashMap：" + linkedHashMap); } }
3. TreeMap（按 key 排序）

TreeMap 会按 key 的自然顺序（如字符串按字母序、数字按大小）排序，也支持自定义排序：

import java.util.Comparator; import java.util.Map; import java.util.TreeMap; public class TreeMapDemo { public static void main(String[] args) { // 方式1：默认自然排序（字符串按字母序） Map<String, Integer> treeMap1 = new TreeMap<>(); treeMap1.put("banana", 5); treeMap1.put("apple", 10); treeMap1.put("orange", 8); // 输出顺序：apple→banana→orange（按字母序排序） System.out.println("自然排序 TreeMap：" + treeMap1); // 方式2：自定义排序（按 key 长度倒序） Map<String, Integer> treeMap2 = new TreeMap<>(new Comparator<String>() { @Override public int compare(String s1, String s2) { // 倒序：s2 长度 - s1 长度 return s2.length() - s1.length(); } }); treeMap2.put("banana", 5); treeMap2.put("apple", 10); treeMap2.put("orange", 8); // 输出顺序：banana/orange（6位）→ apple（5位） System.out.println("自定义排序 TreeMap：" + treeMap2); // 注意：TreeMap 不允许 null key，否则抛 NullPointerException // treeMap1.put(null, 0); // 运行报错 } }

三、适用场景

  • HashMap：优先选择，适用于无需关注顺序、追求高效查找 / 插入的场景（如缓存、快速键值对查询）。
  • LinkedHashMap：需要保留插入顺序的场景（如记录访问日志、实现 LRU 缓存）。
  • TreeMap：需要按 key 排序的场景（如排行榜、按字母序展示数据、范围查询）。

总结

  1. HashMap：无序、高效，允许 null key，是最常用的 Map 实现。
  2. LinkedHashMap：继承 HashMap，核心优势是保证插入顺序，性能略低于 HashMap。
  3. TreeMap：基于红黑树实现，按 key 排序（自然 / 自定义），不允许 null key，查找效率略低但支持排序和范围查询。

核心选择原则：无顺序需求用 HashMap，要插入顺序用 LinkedHashMap，要排序用 TreeMap。

三、HashMap linkHashMap和TreeMap源码剖析

一、HashMap 源码核心剖析

HashMap 是三者的基础，先吃透它的源码，LinkedHashMap 和 TreeMap 就容易理解了。

1. 核心成员变量
// 默认初始容量（必须是2的幂） static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16 // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 链表转红黑树的阈值（链表长度≥8时转换） static final int TREEIFY_THRESHOLD = 8; // 红黑树转链表的阈值（扩容后树节点数≤6时转换） static final int UNTREEIFY_THRESHOLD = 6; // 树化的最小容量（数组容量≥64才会树化，否则只扩容） static final int MIN_TREEIFY_CAPACITY = 64; // 存储元素的数组（Node<K,V>[] 类型，每个元素是链表/红黑树的头节点） transient Node<K,V>[] table; // 元素个数 transient int size; // 结构修改次数（用于快速失败机制） transient int modCount; // 扩容阈值（capacity * loadFactor） int threshold; // 负载因子 final float loadFactor;
2. 核心内部类（Node & TreeNode）
// 基础节点（链表节点） static class Node<K,V> implements Map.Entry<K,V> { final int hash; // key的哈希值（优化后的hash，减少哈希冲突） final K key; V value; Node<K,V> next; // 指向下一个节点的指针（链表） Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } } // 红黑树节点（继承自LinkedHashMap.Entry，间接继承Node） static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // 父节点 TreeNode<K,V> left; // 左子节点 TreeNode<K,V> right; // 右子节点 TreeNode<K,V> prev; // 前驱节点（用于删除） boolean red; // 节点颜色（红/黑） }
3. 核心方法：put 方法（插入元素）

put 是 HashMap 最核心的方法，逻辑如下：

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // 真正的插入逻辑（final方法，不可重写） final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 1. 如果数组为空，先扩容（resize）初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2. 计算索引（i = (n - 1) & hash），如果该位置为空，直接新建节点 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 3. 如果该位置的节点key和hash都匹配，直接覆盖value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 4. 如果是红黑树节点，调用树的插入方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 5. 如果是链表，遍历链表 else { for (int binCount = 0; ; ++binCount) { // 遍历到链表尾部，新建节点插入 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 链表长度≥8，触发树化（还要判断数组容量≥64） if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // 找到匹配的key，跳出循环（后续覆盖value） if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 6. 覆盖已有key的value if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // LinkedHashMap会重写此方法 return oldValue; } } // 7. 结构修改次数+1 ++modCount; // 8. 元素个数超过阈值，触发扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); // LinkedHashMap会重写此方法 return null; }
4. 核心方法：resize 方法（扩容）

扩容是 HashMap 保证性能的关键，核心逻辑：

  • 新容量 = 原容量 × 2（保证是 2 的幂）
  • 重新计算每个节点的索引，迁移到新数组
  • 红黑树会拆分成两个链表 / 红黑树，减少迁移成本

二、LinkedHashMap 源码核心剖析

LinkedHashMap 是 HashMap 的子类，核心是在 HashMap 基础上增加了双向链表，维护插入 / 访问顺序。

1. 核心成员变量 & 内部类
// 双向链表的头节点（最早插入/访问的节点） transient LinkedHashMap.Entry<K,V> head; // 双向链表的尾节点（最新插入/访问的节点） transient LinkedHashMap.Entry<K,V> tail; // 访问顺序（true：按访问顺序；false：按插入顺序，默认false） final boolean accessOrder; // 核心内部类：继承HashMap.Node，增加before/after指针（双向链表） static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; // 前驱、后继节点 Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }
2. 核心特性实现：重写关键方法

LinkedHashMap 几乎没有重写 put 方法，而是通过重写 HashMap 的钩子方法实现有序：

// 1. 新建节点时，把节点加入双向链表尾部 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); linkNodeLast(p); // 把节点链接到双向链表尾部 return p; } // 2. 访问节点时（get/put已存在的key），把节点移到链表尾部（accessOrder=true时生效） void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } } // 3. 插入新节点后，判断是否需要删除最老的节点（LRU缓存实现核心） void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first; // removeEldestEntry默认返回false，重写此方法可实现LRU if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } }

三、TreeMap 源码核心剖析

TreeMap 不继承 HashMap，而是基于红黑树实现，核心依赖NavigableMap和Comparator。

1. 核心成员变量
// 红黑树的根节点 private transient Entry<K,V> root; // 元素个数 private transient int size = 0; // 结构修改次数 private transient int modCount = 0; // 比较器（null则用key的自然排序） private final Comparator<? super K> comparator;
2. 核心内部类（红黑树节点）
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; // 左子节点（小值） Entry<K,V> right; // 右子节点（大值） Entry<K,V> parent; // 父节点 boolean color = BLACK; // 节点颜色（默认黑） Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } }
3. 核心方法：put 方法

TreeMap 的 put 本质是红黑树的插入 + 平衡调整：

public V put(K key, V value) { Entry<K,V> t = root; // 1. 根节点为空，直接新建根节点 if (t == null) { compare(key, key); // 检查key是否可比较（抛NPE/ClassCastException） root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; Comparator<? super K> cpr = comparator; // 2. 使用比较器/自然排序找到插入位置 if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; // 小于当前节点，走左子树 else if (cmp > 0) t = t.right; // 大于当前节点，走右子树 else return t.setValue(value); // 等于，覆盖value } while (t != null); } else { // 自然排序（key必须实现Comparable接口） if (key == null) throw new NullPointerException(); // 不允许null key @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } // 3. 新建节点插入红黑树 Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; // 4. 调整红黑树平衡（核心：变色、旋转） fixAfterInsertion(e); size++; modCount++; return null; }
4. 红黑树平衡调整（fixAfterInsertion）

红黑树的核心是插入 / 删除后通过变色、左旋、右旋维持平衡，保证树的高度在log n级别，这是 TreeMap 有序且高效的关键。

总结

  1. HashMap：核心是数组 + 链表 / 红黑树，通过哈希算法定位元素，putVal处理插入逻辑，resize处理扩容，负载因子 0.75 平衡空间和时间效率。
  2. LinkedHashMap：继承 HashMap，通过双向链表维护顺序，重写newNode/afterNodeAccess等钩子方法实现插入 / 访问顺序，是实现 LRU 缓存的天然选择。
  3. TreeMap：基于红黑树实现，依赖Comparator或Comparable实现 key 排序，put方法核心是红黑树的插入 + 平衡调整，不允许 null key。

四、总结

HashMap、linkHashMap和TreeMap是Map集合中十分重要的双列集合，通过对其基本使用的了解和对其底层源码的剖析，有助于我们更好地理解其核心，这对我们以后得java学习之旅打下了坚实的基础，最后希望大家的java学习之旅畅通无阻，文章如有错误欢迎私信我，我会及时解决，如果我的内容对你有帮助和启发，请点赞、评论、收藏。你们的支持就是我更新最大的动力，那么我们下期再见！

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/6/10 17:13:23

Live Avatar音频同步问题怎么解？输入质量优化实战案例

Live Avatar音频同步问题怎么解&#xff1f;输入质量优化实战案例 1. 为什么Live Avatar的口型总跟不上声音&#xff1f; 你是不是也遇到过这样的情况&#xff1a;视频里数字人张着嘴&#xff0c;但声音却慢半拍&#xff1b;或者嘴型在动&#xff0c;可完全对不上发音&#x…

作者头像 李华
网站建设 2026/6/15 13:23:12

确保项目合规：Vivado License使用规范说明

以下是对您提供的博文《确保项目合规&#xff1a;Vivado License使用规范深度技术分析》的 全面润色与专业升级版 。本次优化严格遵循您的要求&#xff1a; ✅ 彻底消除AI生成痕迹&#xff0c;语言更贴近一线FPGA工程师/IT合规官的真实表达&#xff1b; ✅ 打破模板化结构&…

作者头像 李华
网站建设 2026/6/10 2:18:34

Open-AutoGLM在生活服务场景的应用，效率翻倍

Open-AutoGLM在生活服务场景的应用&#xff0c;效率翻倍 你有没有过这样的时刻&#xff1a; 想点一份外卖&#xff0c;却在美团和饿了么之间反复切换比价&#xff1b; 想关注一个博主&#xff0c;得手动打开抖音、搜索ID、点进主页、再点关注&#xff1b; 想查个公交路线&…

作者头像 李华
网站建设 2026/6/13 16:11:53

模型加载失败？MODELSCOPE_ENDPOINT配置正确方法

模型加载失败&#xff1f;MODELSCOPE_ENDPOINT配置正确方法 你是不是也遇到过这样的情况&#xff1a;明明代码写得没问题&#xff0c;pip install modelscope 也装好了&#xff0c;可一运行 pipeline(task..., modeliic/speech_fsmn_vad_zh-cn-16k-common-pytorch) 就卡住、报…

作者头像 李华
网站建设 2026/6/6 13:59:22

ComfyUI工作流迁移实战指南：从中级到专家的效率提升路径

ComfyUI工作流迁移实战指南&#xff1a;从中级到专家的效率提升路径 【免费下载链接】ComfyUI 最强大且模块化的具有图形/节点界面的稳定扩散GUI。 项目地址: https://gitcode.com/GitHub_Trending/co/ComfyUI 如何在保持创作连续性的同时&#xff0c;实现工作流在不同环…

作者头像 李华