HashMap 源码深度解析合集 - Java高频面试精选(7)1.LinkedList 插入真的是 O(1) 吗？深度解析 Java 双向链表的性能陷阱与源码真相04-192.HashM
为什么 HashMap 是 Java 中最常用、最重要的数据结构？
核心原因就一个：性能。常见的基础数据结构中，数组查询快但插入删除慢，链表插入快但查询慢。HashMap 综合了数组和链表的优点，将查询与插入的效率都控制在近似 O(1) 的复杂度内。
但 HashMap 的设计远不止于此。容量为什么是 2 的幂？哈希扰动函数 spread() 如何防止哈希冲突？链表转红黑树的阈值为什么选 8？本文将从源码级别逐一揭示这些设计背后的原理。
学完本文，你将掌握：
- HashMap 的底层实现原理（数组 + 链表 + 红黑树）
- put 方法的完整执行流程与哈希扰动算法
- 扩容机制与 2 倍扩容的根本原因
- HashMap 为什么线程不安全？并发下会产生什么事故？
- HashMap 的容量为什么必须是 2 的幂？
- HashMap 在 Java 8 版本中做了哪些变更？
简介
HashMap 的底层数据结构由数组、链表和红黑树组成，核心是基于数组实现的。为了解决哈希冲突，采用拉链法，于是引入了链表结构。为了解决链表过长导致的查询性能下降，Java 8 引入了红黑树结构。
HashMap 类中有两个关键的阈值常量：
TREEIFY_THRESHOLD = 8：当链表长度达到 8 时，链表会转换为红黑树UNTREEIFY_THRESHOLD = 6：当红黑树节点数减少到 6 时，红黑树会退化为链表MIN_TREEIFY_CAPACITY = 64：只有数组容量达到 64 时才会触发树化，否则优先扩容数组而不是树化
这三个常量配合使用，目的是避免频繁的树化和退化操作。如果链表只是短暂变长，不会触发树化；如果红黑树只是短暂变小，不会立即退化。
💡 核心提示：为什么树化阈值是 8、退化阈值是 6？这背后有统计学依据。HashMap 中节点的分布服从泊松分布（Poisson Distribution）。在理想的 hash 散列下，链表长度达到 8 的概率约为 0.00000006（千万分之六），几乎不可能自然发生。如果达到了 8，说明 hash 冲突严重，此时用红黑树代替链表可以将 O(n) 退化为 O(log n)。退化为 6 是为了留出缓冲区间（8→6），避免在临界值附近频繁树化/退化，这就是所谓的"迟滞效应"（Hysteresis）。
HashMap 类架构图
contains
implements
implements
«abstract»
AbstractMap
+containsKey(Object) : boolean
+containsValue(Object) : boolean
+isEmpty() : boolean
+size() : int
+clear() : void
«interface»
Map
+put(K, V) : V
+get(Object) : V
+remove(Object) : V
+containsKey(Object) : boolean
+containsValue(Object) : boolean
+entrySet() : Set<Entry>
+keySet() : Set<K>
+values() : Collection<V>
HashMap
-transient Node[] table
-transient int size
-transient int threshold
-transient int modCount
-final float loadFactor
+put(K, V) : V
+get(Object) : V
+remove(Object) : V
+resize() : Node[]
-hash(Object) : int
-putVal(int, K, V, boolean, boolean) : V
-getNode(int, Object) : Node
-treeifyBin(Node[], int) : void
-tableSizeFor(int) : int
LinkedHashMap
-transient Entry head
-transient Entry tail
-final boolean accessOrder
Node
+final int hash
+final K key
+V value
+Node next
+getKey() : K
+getValue() : V
+setValue(V) : V
TreeNode
+TreeNode parent
+TreeNode left
+TreeNode right
+TreeNode prev
+boolean red
+putTreeVal(HashMap, Node[], int, K, V) : TreeNode
+getTreeNode(int, Object) : TreeNode
+removeTreeNode(HashMap, Node[], boolean) : void
+split(HashMap, Node[], int, int) : void
«interface»
Cloneable
«interface»
Serializable
HashMap 的核心工作原理可以用下面的流程图概括：
是
否
是
否
是
否
红黑树
链表
是
是
否
否
是
否
是
否
初始化: table=null, size=0, threshold=0
put(key, value)
hash(key): h = key.hashCode()\n返回 h ^ (h >>> 16)
table 为空?
resize(): 初始化数组\n容量=16 或 tableSizeFor(指定容量)
计算下标: i = (n - 1) & hash
tab[i] 是否为空?
直接插入新节点
key 是否已存在?
覆盖旧值, 返回旧值
节点类型?
putTreeVal: 红黑树插入
遍历链表, 尾插法追加
链表长度 >= 8?
数组容量 >= 64?
treeifyBin: 链表转红黑树
resize(): 扩容数组
size > threshold?
resize(): 容量翻倍\n链表拆分为低位/高位两条链表
modCount++, size++, 返回null
get(key)
hash(key) 计算哈希值
计算下标: (n-1) & hash
找到 key?
返回 value
返回 null
类属性
再看一下 HashMap 类中有哪些关键属性：
public class HashMap<K, V> extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable {
/**
* 默认容量大小，1 << 4 = 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* 负载系数，容量超过 threshold = capacity * loadFactor 时触发扩容
* 默认 16 * 0.75 = 12 个元素时扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 容量最大值，2 的 30 次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 链表转红黑树的阈值：链表长度 > 8 时树化
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 红黑树退化为链表的阈值：节点数 < 6 时退化
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 树化的最小数组容量：只有 table 容量 >= 64 才会树化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 存储元素的数组，容量始终为 2 的幂
*/
transient Node<K, V>[] table;
/**
* 实际存储的键值对数量
*/
transient int size;
/**
* 扩容阈值，当 size > threshold 时触发扩容
*/
transient int threshold;
/**
* 结构修改次数，用于 fail-fast 机制
*/
transient int modCount;
}
其中 Node 是链表的节点：
static class Node<K, V> implements Map.Entry<K, V> {
final int 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;
}
}
以及红黑树的节点 TreeNode（继承自 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; // 前驱节点（继承自 LinkedHashMap.Entry）
boolean red; // 节点颜色
TreeNode(int hash, K key, V val, Node<K, V> next) {
super(hash, key, val, next);
}
}
初始化
HashMap 常见的初始化方法有两个：
- 无参初始化
- 有参初始化，指定容量大小
/**
* 无参初始化
*/
Map<Integer, Integer> map = new HashMap<>();
/**
* 有参初始化，指定容量大小
*/
Map<Integer, Integer> map = new HashMap<>(10);
再看一下构造方法的底层实现：
/**
* 无参初始化
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
/**
* 有参初始化，指定容量大小
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 有参初始化，指定容量大小和负载系数
*/
public HashMap(int initialCapacity, float loadFactor) {
// 校验参数
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
}
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
}
this.loadFactor = loadFactor;
// 计算出合适的容量大小（2的幂）
this.threshold = tableSizeFor(initialCapacity);
}
可以看出，无参构造方法只初始化了负载系数。指定容量大小的有参构造方法也只是初始化了负载系数和 threshold（扩容阈值），两个方法都没有初始化数组大小。
tableSizeFor 方法会将传入的容量值转换为大于等于它的最小的 2 的幂。例如 tableSizeFor(10) 返回 16，tableSizeFor(20) 返回 32。这个方法实现非常精妙：
/**
* 返回大于等于 cap 的最小的 2 的幂
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
💡 核心提示：
tableSizeFor方法为什么先cap - 1？如果不减 1，当 cap 本身就是 2 的幂时（比如 16），结果会变成 32，导致浪费一半空间。减 1 保证了 "恰好等于 2 的幂" 时不会翻倍。而右移 + 或运算的组合，能将最高位 1 右侧的所有位都填充为 1，最后 +1 就是下一个 2 的幂。
如果再有面试官问你，HashMap 初始化的时候数组大小是多少？答案是 0（或者说未初始化），因为 HashMap 采用了懒加载策略，数组在第一次 put 时才会通过 resize() 方法初始化。
深入 hash 算法
在深入 put 方法之前，先看一下 HashMap 的 hash() 方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这个方法做了两件事：
- 如果 key 为 null，返回 0（HashMap 允许 null 作为 key）
- 否则，取 key 的
hashCode()，然后将其无符号右移 16 位，再与原值做异或运算
为什么要这样做？HashMap 计算数组下标用的是 (n - 1) & hash，其中 n 是数组容量（2 的幂）。当 n 较小时（比如 16），n - 1 只有低 4 位是 1，高位都是 0，这意味着 & 运算只会用到 hash 的低位。如果不同 key 的 hashCode 只有高位不同、低位相同，就会产生哈希冲突。通过右移 16 位再异或，把高位的信息混入低位，让高位也参与下标计算，从而减少哈希冲突。
💡 核心提示：为什么选择右移 16 位？因为 int 是 32 位，右移 16 位恰好将高 16 位与低 16 位对齐，异或后高低位的信息混合在一起。这是一个在性能和散列质量之间的权衡：更多次的混合（比如多次右移+异或）可以提高散列质量，但会降低性能；16 位一次的混合在实践中已足够好。
put 源码
put 方法的流程如下：
- 计算 key 的 hash 值
- 如果数组为空，调用
resize()初始化 - 根据
(n - 1) & hash计算数组下标 - 如果下标位置为空，直接插入
- 如果下标位置不为空，判断 key 是否已存在，存在则覆盖
- 如果是红黑树节点，执行红黑树插入
- 如果是链表节点，遍历链表尾插，长度达到 8 时树化
- 如果
size > threshold，调用resize()扩容
put 方法详细流程图
是
否
是
否
是
否
是
否
是
是
否
否
是
否
put(key, value)
hash(key) 计算扰动后的哈希值
table 是否为空?
resize() 初始化数组
i = (n-1) & hash 计算下标
tab[i] == null?
tab[i] = newNode() 直接插入
p.hash == hash && key匹配?
e = p 记录待覆盖节点
p instanceof TreeNode?
putTreeVal() 红黑树插入
遍历链表尾插
binCount >= 7?
table.length >= 64?
treeifyBin() 链表转红黑树
resize() 扩容数组
++size > threshold?
覆盖旧值, 返回旧值
resize() 扩容
modCount++, size++, 返回null
返回旧值
put 源码详解
再看一下 put 方法的具体源码实现：
/**
* put 方法入口
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 计算 hash 值（高位和低位都参与计算）
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 实际的put方法逻辑
* @param hash key对应的hash值
* @param key 键
* @param value 值
* @param onlyIfAbsent 如果为true，则只有当key不存在时才会put，否则会覆盖
* @param evict 如果为false，表处于创建模式
* @return 返回旧值
*/
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. 如果 key 对应下标位置元素不存在，直接插入即可
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
} else {
Node<K, V> e;
K k;
// 3. 如果头节点 key 匹配，直接结束，后续判断是否需要覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
e = p;
} else if (p instanceof TreeNode) {
// 4. 判断下标位置的元素类型，如果是红黑树，则执行红黑树的插入逻辑
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
} else {
// 5. 否则执行链表的插入逻辑
for (int binCount = 0; ; ++binCount) {
// 6. 遍历链表，直到找到空位置为止
if ((e = p.next) == null) {
// 7. 创建一个新的链表节点，并追加到末尾（尾插法）
p.next = newNode(hash, key, value, null);
// 8. 如果链表长度达到 8，则转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) {
treeifyBin(tab, hash);
}
break;
}
// 9. 如果在链表中找到相同的 key，则结束
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
// 10. 判断是否需要覆盖旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 11. 判断是否需要扩容
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}
其中 treeifyBin 方法负责将链表转换为红黑树，但只有在数组容量达到 MIN_TREEIFY_CAPACITY（64）时才会真正树化，否则只是扩容数组：
final void treeifyBin(Node<K, V>[] tab, int hash) {
int n, index;
Node<K, V> e;
// 如果数组容量 < 64，优先扩容而不是树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
resize();
} else if ((e = tab[index = (n - 1) & hash]) != null) {
// 否则，将链表转换为红黑树
TreeNode<K, V> hd = null, tl = null;
// 遍历链表，将所有 Node 替换为 TreeNode
do {
TreeNode<K, V> p = new TreeNode<>(e.hash, e.key, e.value, null);
if (tl == null) {
hd = p;
} else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 将 TreeNode 双向链表构造成红黑树
if ((tab[index] = hd) != null) {
hd.treeify(tab);
}
}
}更多推荐
5
0- 0
已为社区贡献3条内容
所有评论(0)