HashMap
HashMap 源码分析
HashMap 用「数组 + 链表 + 红黑树」实现平均 O(1) 的键值存取:hash 定位桶、冲突挂链、链太长转树兜底,最坏从 O(n) 封顶到 O(log n)。
允许一个 null 键、多个 null 值,非线程安全。
代码块收起展开
// 基于 JDK 25 (本地 D:/1ForCode/JAVA_Source), java.util.HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 默认初始容量 16。容量必须是 2 的幂，(n-1)&hash 才能等价取模（见 hash() 处的说明）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 容量上限 2^30：int 正数范围内最大的 2 的幂
static final int MAXIMUM_CAPACITY = 1 << 30;
// 0.75 是空间利用率与冲突率的折中，size 超过 capacity*0.75 触发扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 桶里已有 8 个节点还往里插，尝试转红黑树。0.75 负载下单桶到 8 的概率约亿分之六，
// 正常几乎不触发：树化是给劣质 hashCode / 哈希碰撞攻击兜底的
static final int TREEIFY_THRESHOLD = 8;
// resize 拆分树时节点数 <= 6 退回链表。8/6 之间空 2，防止 size 在阈值附近抖动时反复互转
static final int UNTREEIFY_THRESHOLD = 6;
// 表容量 < 64 时不转树、先扩容：小表冲突多半是表太小，扩容摊薄比建树便宜
static final int MIN_TREEIFY_CAPACITY = 64;
// 桶数组，懒初始化，长度总是 2 的幂。transient：序列化走自定义 writeObject，只写键值对
transient Node<K,V>[] table;
transient int size;
// 结构性修改计数，迭代器 fail-fast 依据（尽力而为，不能当并发保护用）
transient int modCount;
// 扩容阈值 = capacity * loadFactor。坑：带容量构造后、首次 resize 前，它临时存放初始容量
int threshold;
final float loadFactor;
// 链表节点。hash 缓存下来，resize / 比较时不再重算
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ... 构造器与 Map.Entry 实现略
}
// 扰动函数：把 hashCode 高 16 位异或进低 16 位。定位桶只用低位，
// 让高位也参与，否则只在高位有差异的一批 key 会整批撞进同一个桶
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 返回 >= cap 的最小 2 的幂。JDK8 是五连移位或运算，JDK9 起一条 numberOfLeadingZeros 搞定
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
public HashMap(int initialCapacity, float loadFactor) {
// ... 参数校验略（负容量、非法 loadFactor 抛异常，超 2^30 截断）
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); // 初始容量暂存在 threshold，首次 resize 才换算成真阈值
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 只记负载因子，数组不分配，首次 put 才建表
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 懒初始化：建表也走 resize
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 先比 hash 再 equals，hash 不等就省掉一次 equals
else if (p instanceof TreeNode)
e = ((TreeNode<K,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); // 尾插。JDK7 是头插，并发扩容会成环
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); // 桶里已有 8 个、这次插的是第 9 个，尝试转树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; // putIfAbsent 只在旧值为 null 时覆盖
afterNodeAccess(e); // 空方法，LinkedHashMap 用它维护访问顺序
return oldValue;
}
}
++modCount;
if (++size > threshold) // 先插入后判扩容，JDK7 反过来
resize();
afterNodeInsertion(evict); // 同为 LinkedHashMap 钩子，LRU 淘汰入口
return null;
}
// 初始化或容量翻倍，整个 HashMap 最重的操作
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE; // 到 2^30 上限就不再扩，放任冲突
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr; // 构造时暂存在 threshold 的初始容量在这里兑现
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 断开旧表引用，帮 GC
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 树也按 lo/hi 拆，拆后 <=6 退回链表
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 只看 hash 里新参与定位的那一位：0 留原下标
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 1 则整体挪到 j + oldCap
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null; // 尾接拆链保持相对顺序，全程不重算 hash
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(key)) == null ? null : e.value;
}
// JDK8 的签名是 getNode(int hash, Object key) 两参，后来把 hash 挪进了方法内
final Node<K,V> getNode(Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first; // 多数桶只挂一个节点，首节点命中是最快路径
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 树上查找 O(log n)
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null); // 链上顺序找 O(链长)
}
}
return null;
}
// 链表转树入口。表太小只扩容；真转树分两步：先换节点类型，再建树
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) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null); // Node 逐个替换成 TreeNode
if (tl == null)
hd = p;
else {
p.prev = tl; // TreeNode 同时维护 prev/next 双向链，退化回链表时直接串回
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab); // 到这里才真正建红黑树，染色和旋转都在 treeify 里
}
}
// ... 序列化、视图、TreeNode 内部类等其余成员略
}JDK 7 版对照
代码块收起展开
// JDK 7 的 HashMap：数组 + 链表，没有红黑树。与 JDK8+ 的三个关键区别：
// 1. 结构：JDK8 链长到阈值转红黑树，JDK7 冲突再多也是一条链，最坏 O(n)
// 2. 插入：JDK7 头插，JDK8 尾插
// 3. 扩容：JDK7 逐节点重算下标 + 头插，多线程会成环；JDK8 lo/hi 拆链保序不成环
// 节点类叫 Entry（JDK8 改名 Node），常量与字段和 JDK8 相同，此处略。
// 扰动做 4 次移位异或，比 JDK8 的一次 (h ^ h>>>16) 重。
// JDK8 敢简化，是因为有红黑树兜底，扰动不必做满
final int hash(Object k) {
int h = 0;
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
public V put(K key, V value) {
if (table == EMPTY_TABLE)
inflateTable(threshold); // 同样懒初始化
if (key == null)
return putForNullKey(value); // null 键单独一条路径，固定放 table[0]；JDK8 靠 hash()=0 统一了
int hash = hash(key);
int i = indexFor(hash, table.length); // indexFor = h & (length-1)，同 JDK8 的 (n-1)&hash
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // 先扩容再插入，JDK8 反过来
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
// 头插：新节点直接当链头，插入 O(1)，但链表顺序被反转，祸根在此
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
void resize(int newCapacity) {
Entry<K,V>[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
// 著名的坑：多线程并发 resize 形成环形链表，之后 get 命中该桶就死循环、CPU 100%。
// 根因是逐节点头插反转顺序，两个线程交错执行时可能出现 A.next=B 且 B.next=A
void transfer(Entry<K,V>[] newTable) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while (null != e) {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); // 每个节点重算下标
e.next = newTable[i]; // 头插进新桶
newTable[i] = e;
e = next;
}
}
}
// 一句话：JDK7 = 头插 / 并发扩容成环；JDK8+ = 红黑树 / 尾插 / lo-hi 拆链不成环。两版都非线程安全。原理串讲
一次 map.put(key, value) 的完整链路:入口先过 hash(key),把 hashCode 的高 16 位异或进低 16 位。
为什么要这一步?因为后面定位桶用的是 (n - 1) & hash,n 是 2 的幂时 n-1 的二进制全是低位 1,这个按位与等价于取模但快得多;代价是定位只看 hash 的低位,如果一批 key 的 hashCode 只在高位有差异(源码注释举的例子是连续整数值的 Float),它们会整批落进同一个桶。
花一次异或让高位也参与定位,等于用最便宜的方式把「速度换来的缺陷」补了回来。
进入 putVal,若 table 还是 null(new HashMap() 只记了 loadFactor,什么都没分配),第一次 put 由 resize() 顺手建表。
代码块收起展开
为什么懒初始化?很多 Map 建出来从没装过东西,晚建表就不用白占一片数组。定位到桶后分三路:桶空直接 `newNode`;首节点 hash 相等且 equals 相等就记下待覆盖;首节点是 TreeNode 走 `putTreeVal` 树插入;否则顺链尾插,当桶里已有 8 个节点、这次插入第 9 个时调 `treeifyBin`。
`treeifyBin` 先看表容量:小于 64 只做 `resize()`,小表冲突多半是表太小,扩容摊薄比建树便宜;容量够了才把整条链换成 TreeNode 双向链,再由 `hd.treeify(tab)` 染色旋转建成红黑树。插入完成后 ++modCount、++size,超过 threshold 触发 resize()。
resize() 的精髓在迁移。容量从 oldCap 翻倍后,每个节点的新下标只取决于 hash 里新参与运算的那一位:(e.hash & oldCap) == 0 的留在原下标 j,等于 1 的整体挪到 j + oldCap。
所以 JDK8 起迁移不重算任何 hash,只按这一位把链拆成 lo、hi 两条,尾接保序。
为什么坚持保序?JDK7 的 transfer 逐节点重算下标加头插,头插反转链表顺序,两个线程同时扩容时可能把 A.next 指向 B 的同时 B.next 又指向 A,之后 get 命中该桶就死循环。
JDK8 的拆链方式让并发扩容不再成环,但并发丢数据依旧,HashMap 从没承诺线程安全,只是不再拖垮 CPU。
get(key) 是同一套定位的只读版:getNode(key) 内部算 hash、(n - 1) & hash 定位桶,先查首节点。
多数桶只挂一个节点,这个快路径让平均查找就是一次 hash 加一次比较;首节点不中,TreeNode 走 getTreeNode 的 O(log n),链表顺序找 O(链长)。
最后一个为什么:转树阈值 8、退化阈值 6 怎么来的?源码注释给了泊松分布推算,0.75 负载下单桶节点数达到 8 的概率约亿分之六,正常的 hashCode 根本到不了。
树化的定位是兜底:对付写砸的 hashCode 和恶意构造的碰撞攻击。TreeNode 体积约是 Node 的两倍,常态用不起,所以阈值定在「几乎不触发」的位置;8 与 6 之间空出的 2 是缓冲,防止 size 在阈值附近抖动时链表和树来回互转。
设计取舍
- 容量恒为 2 的幂:换来
(n-1)&hash的定位速度,代价是必须靠hash()扰动补低位随机性。Hashtable 走相反路线,素数容量加取模。 - threshold 字段身兼两职:带容量构造之后、首次 resize 之前,它存的是
tableSizeFor算出的初始容量,读源码时别当成真阈值。 - 树化是兜底手段,常态几乎不触发;key 没实现 Comparable 时,树内同 hash 节点靠
tieBreakOrder用 identityHashCode 强行分出大小。 - modCount 的 fail-fast 只是尽力而为,迭代中的结构修改不保证及时抛 ConcurrentModificationException,并发正确性要靠 ConcurrentHashMap。
- 能预估元素数就用
HashMap.newHashMap(n)(JDK 19 起),它替你按 0.75 换算好容量;手写new HashMap<>(n)装 n 个元素,会在 0.75n 处扩一次容。