Java HashMap的get/put源码深度解析（JDK 1.8）
Java HashMap的get/put源码深度解析（JDK 1.8）
本文基于OpenJDK 1.8源码，深入剖析HashMap核心操作的实现机制。理解这些底层原理，能帮助开发者写出更高效的Java代码。
一、HashMap核心结构
JDK 1.8的HashMap采用数组+链表+红黑树的混合存储结构：
transient Node<K,V>[] table; // 哈希桶数组// 链表节点（基础存储单元）static class Node<K,V> implements Map.Entry<K,V> { final int hash; // 计算得到的哈希值 final K key; V value; Node<K,V> next; // 链表后继指针}// 红黑树节点（TreeNode继承自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;}关键阈值：
TREEIFY_THRESHOLD = 8：链表树化阈值UNTREEIFY_THRESHOLD = 6：红黑树退化阈值MIN_TREEIFY_CAPACITY = 64：最小树化容量
设计演进：
- JDK 1.7：纯数组+链表（头插法）
- JDK 1.8：引入红黑树（尾插法），解决哈希碰撞性能问题
二、put()方法源码全流程
入口方法
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. 计算桶下标：(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. 检查头节点是否匹配 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) { // 5.1 插入新节点（尾插法） p.next = newNode(hash, key, value, null); // 5.2 检查树化条件 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // 5.3 检查链表节点是否匹配 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 6. 更新已存在节点的值 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; return oldValue; } } // 7. 扩容检查 if (++size > threshold) resize(); return null;}关键流程解析：
-
哈希计算：通过扰动函数增强散列性
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);} -
树化逻辑：满足链表长度≥8且数组长度≥64时才树化
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 优先扩容而非树化 else if ((e = tab[index = (n - 1) & hash]) != null) { // 链表转红黑树的具体实现... }} -
扩容机制：2倍扩容+高低位拆分
final Node<K,V>[] resize() { // ... for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { // 拆分成低位链表和高位链表 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; do { // 关键判断：e.hash & oldCap if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = e.next) != null); // 低位链表保持原索引 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 高位链表迁移到[原索引+oldCap] if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } return newTab;}
三、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; // first:桶的第一个节点, e:遍历节点 int n; // 数组长度 K k; // 1. 数组非空且桶非空 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 2. 检查桶的第一个节点 if (first.hash == hash && ((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;}树节点查找：getTreeNode()
final TreeNode<K,V> getTreeNode(int h, Object k) { // 从根节点开始遍历 return ((parent != null) ? root() : this).find(h, k, null);}// 红黑树查找算法final TreeNode<K,V> find(int h, Object k, Class<?> kc) { TreeNode<K,V> p = this; do { int ph, dir; K pk; TreeNode<K,V> pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; // 左子树 else if (ph < h) p = pr; // 右子树 else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; // 找到节点 else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.find(h, k, kc)) != null) return q; // 递归右子树 else p = pl; // 继续左子树 } while (p != null); return null;}四、设计精髓与性能优化
1. 哈希扰动函数
(h = key.hashCode()) ^ (h >>> 16)将高16位与低16位异或，增加低位的随机性，减少哈希冲突
2. 高效定位桶
index = (table.length - 1) & hash利用位运算替代取模，效率提升5-8倍
3. 扩容优化
- 免rehash：通过
e.hash & oldCap判断位置 - 高低位拆分：保持链表顺序，避免死链
- 并行迁移：不同桶可同时迁移（线程不安全）
4. 树化策略
5. 时间复杂度对比
五、最佳实践与陷阱规避
正确使用HashMap
// 1. 预设容量避免多次扩容Map<String, Integer> map = new HashMap<>(128);// 2. 使用不可变对象作为Keypublic final class ImmutableKey { private final String id; // 必须正确实现hashCode和equals @Override public int hashCode() { return Objects.hash(id); }}// 3. 并发场景使用ConcurrentHashMapMap<String, Integer> safeMap = new ConcurrentHashMap<>();常见陷阱
// 陷阱1：可变对象作为KeyMap<List<String>, Integer> map = new HashMap<>();List<String> key = new ArrayList<>();map.put(key, 1);key.add(\"item\"); // 改变key的hashCode，导致无法检索// 陷阱2：未重写hashCode/equalsclass Person { String name; // 缺少hashCode/equals实现}Person p1 = new Person(\"Alice\");Person p2 = new Person(\"Alice\");map.put(p1, 1);map.get(p2); // 返回null六、高频面试题解析
Q1：HashMap何时会触发扩容？
当size > threshold（容量*负载因子）时触发，默认负载因子0.75：
- 初始容量16，首次扩容阈值12
- 扩容后容量翻倍，阈值重新计算
Q2：为什么树化阈值是8？
根据泊松分布公式：
P(X=k) = (λ^k * e^(-λ)) / k!当负载因子0.75时，链表长度≥8的概率小于千万分之一
Q3：头插法和尾插法的区别？
Q4：为什么用红黑树不用AVL树？
- 红黑树的平衡性要求较低（黑色节点平衡）
- 插入/删除的旋转操作更少
- 查询效率略低但仍在O(log n)级别
通过源码分析可见，HashMap的设计处处体现着工程智慧：用空间换时间，在冲突中寻求平衡。建议开发者在理解原理的基础上，结合实际场景合理选择参数，才能发挥HashMap的最大性能。
