目录
一、HashMap基础结构
二、put操作流程分析
put操作关键步骤总结
三、get操作流程分析
get操作关键步骤总结
四、延伸
1.hash()方法
2. 扩容
resize()方法的主要逻辑：
Java 8中对扩容的优化：
3. 转向红黑树的条件
HashMap作为Java集合框架中最重要且最常用的数据结构之一，其内部实现机制值得深入探究。本文将从源码角度分析HashMap的get和put操作流程，基于Java 8的实现进行讲解。
一、HashMap基础结构
在讲解get和put之前，我们先了解HashMap的核心结构：
// HashMap的主要成员变量
transient Node<K,V>[] table; // 存储元素的数组
transient int size; // 实际存储的键值对数量
int threshold; // 扩容阈值 (capacity * loadFactor)
final float loadFactor; // 负载因子(默认0.75)HashMap采用"数组+链表+红黑树"的混合存储结构：
数组(table)是主体
当哈希冲突时，使用链表法解决
当链表长度超过8且数组长度≥64时，链表转为红黑树
二、put操作流程分析
put操作是HashMap的核心功能之一，其中主要方法为：
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}核心逻辑putVal方法：
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：table为空则初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 步骤2：计算索引位置，如果该位置为空则直接插入if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 步骤3：节点key已存在，直接覆盖valueif (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转为红黑树if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}// key已存在则跳出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 步骤6：写入valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 步骤7：超过阈值则扩容++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}put操作关键步骤总结
-
计算哈希值：通过hash()方法计算key的哈希值
-
初始化检查：如果table为空，则调用resize()初始化
-
定位桶位置：通过
(n-1) & hash计算数组下标（等价于hash % n，但效率更高--位运算比取模快） -
处理冲突：
-
如果该位置为空，直接插入新节点
-
如果key已存在，则覆盖value
-
如果是树节点，调用红黑树的插入方法
-
如果是链表，遍历链表并在尾部插入
-
-
树化检查：链表长度≥8时可能转为红黑树
-
扩容检查：size超过threshold则扩容
三、get操作流程分析
首先来看get的实现方法：
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}其核心实现getNode方法解析：
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 步骤1：table不为空且长度>0且对应位置有节点if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 步骤2：检查第一个节点if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 步骤3：遍历后续节点if ((e = first.next) != null) {// 步骤4：如果是树节点if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 步骤5：遍历链表do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}get操作关键步骤总结
-
计算哈希值：与put相同的hash()方法
-
定位桶位置：同样的
(n-1) & hash计算方式 -
检查首节点：先比较hash，再比较key
-
处理冲突：
-
如果是树节点，调用红黑树的查找方法
-
如果是链表，遍历查找
-
-
返回结果：找到返回value，未找到返回null
四、延伸
1.hash()方法
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}可以看见代码中将高16位与低16位异或，这么做可以实现：
减少哈希冲突
充分利用高位的哈希信息
使哈希分布更加均匀
2. 扩容
resize()方法的主要逻辑：
计算新容量和新阈值
创建新数组
将旧数组元素重新分配到新数组（rehash）
Java 8中对扩容的优化：
无需重新计算hash，通过
(e.hash & oldCap) == 0判断位置元素要么在原位置，要么在原位置+oldCap的位置
3. 转向红黑树的条件
链表转为红黑树的两个条件：
-
链表长度 ≥ TREEIFY_THRESHOLD(8)
-
数组长度 ≥ MIN_TREEIFY_CAPACITY(64)
【注】上面表示默认情况下是链表长度-8，且数组长度-64
否则会优先进行扩容而不是转向红黑树。
)
)
