Java Map 源码解析：核心原理与应用

Java Map 源码解析：核心原理与应用

Java 的 Map 接口是集合框架中一个重要的组成部分，专门用于存储键值对。其强大的功能和灵活的实现使其在各种应用场景中得到了广泛的使用。本文面向对 Java 集合框架有一定了解的开发者，通过对 Map 接口及其常见实现类的源码解析，帮助深入理解其核心原理和应用。

---

一、背景与简介

Map 接口在 Java 集合框架中承担着键值对存储和快速检索的职责。它提供了一种通过键（Key）唯一标识值（Value）的存储方式。

1.1 Map 的特点

• 键值对存储：每个键对应一个唯一的值。
• 键的唯一性：相同键的插入会覆盖旧值。
• 线程安全问题：大多数实现类（如 HashMap）非线程安全，需根据场景选择适合的实现。

1.2 常见实现类及适用场景

• HashMap：基于哈希表实现，无序存储，适合快速查找的场景。
• TreeMap：基于红黑树实现，有序存储，适合需要排序的场景。
• LinkedHashMap：维护插入顺序或访问顺序。
• ConcurrentHashMap：线程安全，适合并发环境。

示例代码：

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 30);
map.put("Bob", 25);
System.out.println(map.get("Alice")); // 输出 30

---

二、Map 接口解析

Map 接口定义了许多核心方法，其设计直接影响了实际操作的性能和可用性。

2.1 核心方法

1. put(K key, V value)：添加或更新键值对。
2. get(Object key)：根据键获取值。
3. containsKey(Object key)：检查是否包含某键。
4. entrySet()、keySet() 和 values()：提供视图方法以便操作键值对。

示例代码：

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 30);
map.put("Bob", 25);
System.out.println(map.containsKey("Alice")); // 输出 true
System.out.println(map.entrySet()); // 输出所有的键值对

2.2 默认方法

Java 8 引入了默认方法，例如：

• forEach：遍历键值对。
• getOrDefault：获取值时指定默认值。

示例代码：

map.forEach((key, value) -> System.out.println(key + ": " + value));
System.out.println(map.getOrDefault("Charlie", 0));

---

三、常见实现类源码剖析

3.1 HashMap 源码剖析

```tex
HashMap 源码put 过程      涉及面试  如果解决hash冲突hash = hash(key);index   = hash & *(table.length -1)树化的阈值  8  考虑树化数组的长度未到达64 --> 扩容  为原来的2倍数组的长度到达64   --> 树化反树化 阈值 6  考虑反树化反树化的情况1> 父节点的左子节点或右子节点 为null2> 父节点的左子树的左节点为null扩容时机1> 链表长度>8 +  数组的长度未到达64 --> 扩容为原来的2倍2> size 达到了 扩容阈值 (table.length * 加载因子) --> 扩容为原来的2倍Map集合在使用时,键只推荐使用String  以及包装类
``````java
package com.atguigu.test;import java.util.HashMap;public class Demo10_HashMap_JDK8 {/*HashMap 源码put 过程      涉及面试  如果解决hash冲突hash = hash(key);index   = hash & *(table.length -1)树化的阈值  8  考虑树化数组的长度未到达64 --> 扩容  为原来的2倍数组的长度到达64   --> 树化反树化 阈值 6  考虑反树化反树化的情况1> 父节点的左子节点或右子节点 为null2> 父节点的左子树的左节点为null扩容时机1> 链表长度>8 +  数组的长度未到达64 --> 扩容为原来的2倍2> size 达到了 扩容阈值 (table.length * 加载因子) --> 扩容为原来的2倍Map集合在使用时,键只推荐使用String  以及包装类*/public static void main(String[] args) {HashMap<MyKey,Integer> map = new HashMap<>();for (int i = 0; i < 100; i++) {map.put(new MyKey(i),i);}System.out.println(map);}
}```

数据结构

HashMap 基于 数组 + 链表/红黑树 实现：

• 使用数组存储键值对。
• 处理哈希冲突时，链表长度超过阈值（默认 8）后转换为红黑树。

核心方法解析

1. put 方法
   • 计算键的哈希值。
   • 根据哈希值找到对应的桶。
   • 如果桶中存在相同键，更新值；否则插入新节点。

简化代码：

public V put(K key, V value) {int hash = hash(key);int index = (n - 1) & hash; // 计算桶索引if (table[index] == null) {table[index] = new Node<>(hash, key, value, null);} else {// 处理哈希冲突...}return oldValue;
}

1. get 方法
   • 根据键计算哈希值，找到对应的桶。
   • 遍历桶中的节点，查找匹配的键。

性能优化

• 哈希函数减少冲突。
• 链表转红黑树优化查询效率。

```java
// JDK1.7 
private class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始化容量 16static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认加载因子 0.75Fstatic final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;public HashMap() {//DEFAULT_INITIAL_CAPACITY：默认的初始化容量 16//DEFAULT_LOAD_FACTOR：默认加载因子 0.75Fthis(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);//调用本类的其他构造器}public V put(K key, V value) {//table是数组，存储键值对的数组，元素的类型Entry类型。//如果HashMap还没有添加过元素，table就是一个空数组if (table == EMPTY_TABLE) {inflateTable(threshold);//阈值 = 16; 阈值初始化为16//如果数组是空数组，长度变为16，threshold = capacity * loadFactor = 16 * 0.75 = 12}//HashMap允许key为null，Hashtable不允许if (key == null)//如果key为null，特殊处理return putForNullKey(value);// key为null的键值对，一定是存储在table[0]下面的。//计算key的hash值int hash = hash(key);//计算新的映射关系的存储下标table[i] ,依据为:key的hash值和数组的长度int i = indexFor(hash, table.length);//先取出table[i]的头结点//如果头结点不满足，就依次判断下面的结点  e = e.nextfor (Entry<K, V> e = table[i]; e != null; e = e.next) {Object k;//如果e.hash == hash 并且 要么是e.key 和新的映射关系的key地址相同或equls相同//说明e的key与新的映射关系的key相同if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//用新的value覆盖原来的valueV oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;//添加新的映射关系到table[i]的位置，作为table[i]的头结点，原来table[i]下面的链表连接到它next中addEntry(hash, key, value, i);return null;}private void inflateTable(int toSize) {// Find a power of 2 >= toSize//如果数组的长度不是2的n次方，纠正为2的n次方int capacity = roundUpToPowerOf2(toSize);//重新计算阈值 = capacity * loadFactor;threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//table重新建新数组 ，长度为 capacitytable = new Entry[capacity];//暂时不管它，hash种子有关initHashSeedAsNeeded(capacity);}private V putForNullKey(V value) {//整个for循环的作用：//(1)先取出数组table[0]的第一个元素e，如果e不为null//(2)判断e的key是否为null，如果e.key为null，就用新的value覆盖原来的value//(3)e=e.next，继续判断下一个结点//所有的操作都是在table[0]下面的//key为null的键值对，一定是存储在table[0]下面的。for (Entry<K, V> e = table[0]; e != null; e = e.next) {if (e.key == null) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;//把新的键值对(null,value)存储到table[0]的下面addEntry(0, null, value, 0);//hash=0,key=null,value=value,bucketIndex=0return null;}void addEntry(int hash, K key, V value, int bucketIndex) {//size：HashMap中所有键值对的个数//size >= threshold，达到阈值 并且 table[bucketIndex]非空//同时满足它俩的话，就会扩容if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);//把数组table扩大为原来的2倍hash = (null != key) ? hash(key) : 0; //重写计算key的hash值bucketIndex = indexFor(hash, table.length);//重新计算[bucketIndex]/*为什么数组扩容后，要重新计算下标？index = hash & table.length-1;  如果table.length变了，就需要重新计算 [index]*/}createEntry(hash, key, value, bucketIndex);}//本来我们想着直接使用key的hashCode()计算的结果的，但是很多时候用户自己实现的hashCode()不是很好//冲突现象比较严重，所以他在hashCode()的基础上做了一些干扰的操作，使得hash值更分散。//如果hash值更分散，那么存储到table中就会更均匀分布，而不是都在某个table[index]final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}void createEntry(int hash, K key, V value, int bucketIndex) {//取出[bucketIndex]位置的元素，即table[bucketIndex]的头结点Entry<K, V> e = table[bucketIndex];//table[bucketIndex]的头结点变为新结点(key,value)的Entry对象。//原来table[bucketIndex]下面的链表作为新结点的nexttable[bucketIndex] = new Entry<>(hash, key, value, e);//元素个数增加size++;}//HashMaP的元素类型，类似于我们在LinkedList中看到都Node，只是另一种形式的结点static class Entry<K, V> implements Map.Entry<K, V> {final K key;V value;Entry<K, V> next;int hash;/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K, V> n) {value = v;next = n;key = k;hash = h;}}// 用key的hash值 & 和数组的长度-1,计算下标static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";//用key的hash值， 和数组的长度-1做运算得到下标，范围[0,table.length-1]范围内return h & (length - 1);}
}
```1、put(key,value)（1）当第一次添加映射关系时，数组初始化为一个长度为**16**的**HashMap$Entry**的数组，这个HashMap$Entry类型是实现了java.util.**Map.Entry**接口（2）特殊考虑：如果key为null，index直接是[0],hash也是0（3）如果key不为null，在计算index之前，会对key的hashCode()值，做一个hash(key)再次哈希的运算，这样可以使得Entry对象更加散列的存储到table中（4）计算index = table.length-1 & hash;（5）如果table[index]下面，已经有映射关系的key与我要添加的新的映射关系的key相同了，会用新的value替换旧的value。（6）如果没有相同的，会把新的映射关系添加到链表的头，原来table[index]下面的Entry对象连接到新的映射关系的next中。（7）添加之前先判断if(size >= threshold  &&  table[index]!=null)如果该条件为true，会扩容```java
if(size >= threshold  &&  table[index]!=null){①会扩容②会重新计算key的hash③会重新计算index}
```

3.2 TreeMap 源码剖析

数据结构

TreeMap 基于 红黑树 实现，具有以下特点：

• 键值对按键的自然顺序或指定的比较器排序。
• 支持高效的范围查询。

核心方法解析

1. 插入
   • 将新节点插入到红黑树中。
   • 维护红黑树的平衡性。
2. 查询
   • 利用红黑树的特性，查询复杂度为 O(log n)。

示例代码：

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Alice", 30);
treeMap.put("Bob", 25);
System.out.println(treeMap);

---

四、性能与使用场景分析

4.1 性能对比

实现类	数据结构	时间复杂度	适用场景
HashMap	数组 + 链表/红黑树	O(1)（查找、插入）	快速查找，无需排序的场景。
TreeMap	红黑树	O(log n)（查找、插入）	需要有序存储的场景。
ConcurrentHashMap	分段锁	O(1)（查找、插入）	并发访问。
LinkedHashMap	哈希表 + 双向链表	O(1)（查找、插入）	保留插入顺序或访问顺序的场景。

4.2 使用建议

• 普通场景：HashMap 是首选。
• 有序存储：使用 TreeMap。
• 线程安全：使用 ConcurrentHashMap。
• 顺序敏感：使用 LinkedHashMap。

---

五、总结与延伸阅读

5.1 总结

Map 接口及其实现类在 Java 开发中扮演重要角色。从 HashMap 的高效性到 TreeMap 的有序性，以及 ConcurrentHashMap 的线程安全特性，不同的实现类满足了不同的场景需求。

5.2 延伸阅读

• JDK 官方文档
• 《Java 并发编程实战》
• 《深入理解 Java 虚拟机》

---

六、实践案例

案例：统计用户访问页面次数

在一个网站中，我们需要统计每个用户访问某些页面的次数，并能够动态地增加访问记录。使用 HashMap 可以非常高效地完成这一任务。

import java.util.HashMap;
import java.util.Map;public class UserPageVisitCounter {// 用于存储每个用户的页面访问记录private final Map<String, Map<String, Integer>> userVisitMap = new HashMap<>();/*** 记录用户对页面的访问* @param userId 用户 ID* @param page 页面名称*/public void recordVisit(String userId, String page) {// 获取当前用户的访问记录Map<String, Integer> pageVisitCount = userVisitMap.getOrDefault(userId, new HashMap<>());// 更新用户对当前页面的访问次数pageVisitCount.put(page, pageVisitCount.getOrDefault(page, 0) + 1);// 更新总表中的记录userVisitMap.put(userId, pageVisitCount);}/*** 获取用户对某页面的访问次数* @param userId 用户 ID* @param page 页面名称* @return 访问次数*/public int getPageVisitCount(String userId, String page) {return userVisitMap.getOrDefault(userId, new HashMap<>()).getOrDefault(page, 0);}/*** 打印所有用户的访问统计*/public void printAllVisits() {for (Map.Entry<String, Map<String, Integer>> userEntry : userVisitMap.entrySet()) {String userId = userEntry.getKey();Map<String, Integer> visits = userEntry.getValue();System.out.println("用户 " + userId + " 的访问记录：");for (Map.Entry<String, Integer> visitEntry : visits.entrySet()) {System.out.println("  页面：" + visitEntry.getKey() + "，访问次数：" + visitEntry.getValue());}}}public static void main(String[] args) {UserPageVisitCounter counter = new UserPageVisitCounter();// 模拟用户访问counter.recordVisit("user1", "home");counter.recordVisit("user1", "home");counter.recordVisit("user1", "about");counter.recordVisit("user2", "home");counter.recordVisit("user2", "contact");// 获取访问统计System.out.println("user1 访问 home 页面次数：" + counter.getPageVisitCount("user1", "home"));System.out.println("user2 访问 contact 页面次数：" + counter.getPageVisitCount("user2", "contact"));// 打印所有用户的访问记录counter.printAllVisits();}
}