核心内容摘要
探寻川渝风情：不止于“BBB”的文化魅力
目录
Map集合的核心概念
Map 集合的核心概念
Map 的常用实现类
Map 的核心注意点
HashMap linkHashMap和TreeMap的使用
核心特性对比
基本使用示例
HashMap无序高效
LinkedHashMap保证插入顺序
TreeMap按 key 排序
适用场景
总结
HashMap linkHashMap和TreeMap源码剖析
HashMap 源码核心剖析
核心成员变量
核心内部类Node TreeNode
核心方法put 方法插入元素
核心方法resize 方法扩容
LinkedHashMap 源码核心剖析
核心成员变量 内部类
核心特性实现重写关键方法
TreeMap 源码核心剖析
核心成员变量
核心内部类红黑树节点
核心方法put 方法
红黑树平衡调整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 可以对应相同的 ValueKey 和 Value 都可以是任意引用类型基本类型会自动装箱为包装类如 int → Integer可以把 Map 理解为 “字典”Key 是 “单词”Value 是 “单词的解释”通过单词能快速找到解释。
Map 的常用实现类日常开发中不会直接用 Map 接口而是用它的实现类最常用的有 3 种实现类核心特点适用场景HashMap基于哈希表实现无序查询 / 增删效率高O (
线程不安全绝大多数日常场景非并发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 只能有一个 nullHashtable 不允许 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 (
高略低于 HashMap中O (log n)
基本使用示例
HashMap无序高效import java.util.HashMap; import java.util.Map; import java.util.Set; public class HashMapDemo { public static void main(String[] args) { //
创建 HashMap 对象key 为 Stringvalue 为 Integer MapString, Integer hashMap new HashMap(); //
新增元素put hashMap.put(苹果,
; hashMap.put(香蕉,
; hashMap.put(橙子,
; hashMap.put(null,
; // 允许 null key System.out.println(初始 HashMap hashMap); // 输出顺序不固定 //
修改元素重复 put 同一个 key 会覆盖 value hashMap.put(香蕉,
; System.out.println(修改后 HashMap hashMap); //
查询元素get int appleNum hashMap.get(苹果); System.out.println(苹果的数量 appleNum); // 查找不存在的 key返回 null Integer grapeNum hashMap.get(葡萄); System.out.println(葡萄的数量 grapeNum); //
删除元素remove hashMap.remove(null); System.out.println(删除 null 后 hashMap); //
遍历推荐 entrySet 方式效率更高 SetMap.EntryString, Integer entrySet hashMap.entrySet(); for (Map.EntryString, Integer entry : entrySet) { System.out.println(key entry.getKey() value entry.getValue()); } } }
LinkedHashMap保证插入顺序LinkedHashMap 是 HashMap 的子类用法几乎一致核心区别是遍历顺序和插入顺序一致import java.util.LinkedHashMap; import java.util.Map; public class LinkedHashMapDemo { public static void main(String[] args) { //
创建 LinkedHashMap 对象 MapString, Integer linkedHashMap new LinkedHashMap(); //
按顺序新增元素 linkedHashMap.put(苹果,
; linkedHashMap.put(香蕉,
; linkedHashMap.put(橙子,
; // 输出顺序和插入顺序完全一致苹果→香蕉→橙子 System.out.println(LinkedHashMap linkedHashMap); //
其他操作修改、删除、遍历和 HashMap 完全相同 linkedHashMap.put(香蕉,
; System.out.println(修改后 LinkedHashMap linkedHashMap); } }
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默认自然排序字符串按字母序 MapString, Integer treeMap1 new TreeMap(); treeMap
put(banana,
; treeMap
put(apple,
; treeMap
put(orange,
; // 输出顺序apple→banana→orange按字母序排序 System.out.println(自然排序 TreeMap treeMap
; // 方式2自定义排序按 key 长度倒序 MapString, Integer treeMap2 new TreeMap(new ComparatorString() { Override public int compare(String s1, String s
{ // 倒序s2 长度 - s1 长度 return s
length() - s
length(); } }); treeMap
put(banana,
; treeMap
put(apple,
; treeMap
put(orange,
; // 输出顺序banana/orange6位→ apple5位 System.out.println(自定义排序 TreeMap treeMap
; // 注意TreeMap 不允许 null key否则抛 NullPointerException // treeMap
put(null,
; // 运行报错 } }
适用场景HashMap优先选择适用于无需关注顺序、追求高效查找 / 插入的场景如缓存、快速键值对查询。
LinkedHashMap需要保留插入顺序的场景如记录访问日志、实现 LRU 缓存。
TreeMap需要按 key 排序的场景如排行榜、按字母序展示数据、范围查询。
总结HashMap无序、高效允许 null key是最常用的 Map 实现。
LinkedHashMap继承 HashMap核心优势是保证插入顺序性能略低于 HashMap。
TreeMap基于红黑树实现按 key 排序自然 / 自定义不允许 null key查找效率略低但支持排序和范围查询。
核心选择原则无顺序需求用 HashMap要插入顺序用 LinkedHashMap要排序用 TreeMap。
HashMap linkHashMap和TreeMap源码剖析
HashMap 源码核心剖析HashMap 是三者的基础先吃透它的源码LinkedHashMap 和 TreeMap 就容易理解了。
核心成员变量// 默认初始容量必须是2的幂 static final int DEFAULT_INITIAL_CAPACITY 1 4; // 16 // 最大容量 static final int MAXIMUM_CAPACITY 1 30; // 默认负载因子 static final float DEFAULT_LOAD_FACTOR
75f; // 链表转红黑树的阈值链表长度≥8时转换 static final int TREEIFY_THRESHOLD 8; // 红黑树转链表的阈值扩容后树节点数≤6时转换 static final int UNTREEIFY_THRESHOLD 6; // 树化的最小容量数组容量≥64才会树化否则只扩容 static final int MIN_TREEIFY_CAPACITY 64; // 存储元素的数组NodeK,V[] 类型每个元素是链表/红黑树的头节点 transient NodeK,V[] table; // 元素个数 transient int size; // 结构修改次数用于快速失败机制 transient int modCount; // 扩容阈值capacity * loadFactor int threshold; // 负载因子 final float loadFactor;
核心内部类Node TreeNode// 基础节点链表节点 static class NodeK,V implements Map.EntryK,V { final int hash; // key的哈希值优化后的hash减少哈希冲突 final K key; V value; NodeK,V next; // 指向下一个节点的指针链表 Node(int hash, K key, V value, NodeK,V next) { this.hash hash; this.key key; this.value value; this.next next; } } // 红黑树节点继承自LinkedHashMap.Entry间接继承Node static final class TreeNodeK,V extends LinkedHashMap.EntryK,V { TreeNodeK,V parent; // 父节点 TreeNodeK,V left; // 左子节点 TreeNodeK,V right; // 右子节点 TreeNodeK,V prev; // 前驱节点用于删除 boolean red; // 节点颜色红/黑 }
核心方法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) { NodeK,V[] tab; NodeK,V p; int n, i; //
如果数组为空先扩容resize初始化 if ((tab table) null || (n tab.length)
n (tab resize()).length; //
计算索引i (n -
hash如果该位置为空直接新建节点 if ((p tab[i (n -
hash]) null) tab[i] newNode(hash, key, value, null); else { NodeK,V e; K k; //
如果该位置的节点key和hash都匹配直接覆盖value if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; //
如果是红黑树节点调用树的插入方法 else if (p instanceof TreeNode) e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); //
如果是链表遍历链表 else { for (int binCount 0; ; binCount) { // 遍历到链表尾部新建节点插入 if ((e p.next) null) { p.next newNode(hash, key, value, null); // 链表长度≥8触发树化还要判断数组容量≥64 if (binCount TREEIFY_THRESHOLD -
treeifyBin(tab, hash); break; } // 找到匹配的key跳出循环后续覆盖value if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; p e; } } //
覆盖已有key的value if (e ! null) { V oldValue e.value; if (!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e); // LinkedHashMap会重写此方法 return oldValue; } } //
结构修改次数1 modCount; //
元素个数超过阈值触发扩容 if (size threshold) resize(); afterNodeInsertion(evict); // LinkedHashMap会重写此方法 return null; }
核心方法resize 方法扩容扩容是 HashMap 保证性能的关键核心逻辑新容量 原容量 × 2保证是 2 的幂重新计算每个节点的索引迁移到新数组红黑树会拆分成两个链表 / 红黑树减少迁移成本
LinkedHashMap 源码核心剖析LinkedHashMap 是 HashMap 的子类核心是在 HashMap 基础上增加了双向链表维护插入 / 访问顺序。
核心成员变量 内部类// 双向链表的头节点最早插入/访问的节点 transient LinkedHashMap.EntryK,V head; // 双向链表的尾节点最新插入/访问的节点 transient LinkedHashMap.EntryK,V tail; // 访问顺序true按访问顺序false按插入顺序默认false final boolean accessOrder; // 核心内部类继承HashMap.Node增加before/after指针双向链表 static class EntryK,V extends HashMap.NodeK,V { EntryK,V before, after; // 前驱、后继节点 Entry(int hash, K key, V value, NodeK,V next) { super(hash, key, value, next); } }
核心特性实现重写关键方法LinkedHashMap 几乎没有重写 put 方法而是通过重写 HashMap 的钩子方法实现有序//
新建节点时把节点加入双向链表尾部 NodeK,V newNode(int hash, K key, V value, NodeK,V e) { LinkedHashMap.EntryK,V p new LinkedHashMap.EntryK,V(hash, key, value, e); linkNodeLast(p); // 把节点链接到双向链表尾部 return p; } //
访问节点时get/put已存在的key把节点移到链表尾部accessOrdertrue时生效 void afterNodeAccess(NodeK,V e) { LinkedHashMap.EntryK,V last; if (accessOrder (last tail) ! e) { LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,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; } } //
插入新节点后判断是否需要删除最老的节点LRU缓存实现核心 void afterNodeInsertion(boolean evict) { LinkedHashMap.EntryK,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。
核心成员变量// 红黑树的根节点 private transient EntryK,V root; // 元素个数 private transient int size 0; // 结构修改次数 private transient int modCount 0; // 比较器null则用key的自然排序 private final Comparator? super K comparator;
核心内部类红黑树节点static final class EntryK,V implements Map.EntryK,V { K key; V value; EntryK,V left; // 左子节点小值 EntryK,V right; // 右子节点大值 EntryK,V parent; // 父节点 boolean color BLACK; // 节点颜色默认黑 Entry(K key, V value, EntryK,V parent) { this.key key; this.value value; this.parent parent; } }
核心方法put 方法TreeMap 的 put 本质是红黑树的插入 平衡调整public V put(K key, V value) { EntryK,V t root; //
根节点为空直接新建根节点 if (t null) { compare(key, key); // 检查key是否可比较抛NPE/ClassCastException root new Entry(key, value, null); size 1; modCount; return null; } int cmp; EntryK,V parent; Comparator? super K cpr comparator; //
使用比较器/自然排序找到插入位置 if (cpr ! null) { do { parent t; cmp cpr.compare(key, t.key); if (cmp
t t.left; // 小于当前节点走左子树 else if (cmp
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
t t.left; else if (cmp
t t.right; else return t.setValue(value); } while (t ! null); } //
新建节点插入红黑树 EntryK,V e new Entry(key, value, parent); if (cmp
parent.left e; else parent.right e; //
调整红黑树平衡核心变色、旋转 fixAfterInsertion(e); size; modCount; return null; }
红黑树平衡调整fixAfterInsertion红黑树的核心是插入 / 删除后通过变色、左旋、右旋维持平衡保证树的高度在log n级别这是 TreeMap 有序且高效的关键。
总结HashMap核心是数组 链表 / 红黑树通过哈希算法定位元素putVal处理插入逻辑resize处理扩容负载因子
75 平衡空间和时间效率。
LinkedHashMap继承 HashMap通过双向链表维护顺序重写newNode/afterNodeAccess等钩子方法实现插入 / 访问顺序是实现 LRU 缓存的天然选择。
TreeMap基于红黑树实现依赖Comparator或Comparable实现 key 排序put方法核心是红黑树的插入 平衡调整不允许 null key。
四、
总结HashMap、linkHashMap和TreeMap是Map集合中十分重要的双列集合通过对其基本使用的了解和对其底层源码的剖析有助于我们更好地理解其核心这对我们以后得java学习之旅打下了坚实的基础最后希望大家的java学习之旅畅通无阻文章如有错误欢迎私信我我会及时解决如果我的内容对你有帮助和启发请点赞、评论、收藏。
你们的支持就是我更新最大的动力那么我们下期再见