HashMap的增加和扩容原理
21 min
写在前面
HashMap的知识，看八股肯定是不够的，所以来看看源码。
看很多源码之后才知道Java的一些类的实现有多么优雅，我只能用优雅来形容。
源码解读
我主要是从两个方面来看这部分的源码，一个是创建，一个是添加。其实重点还是添加，只不过我在添加的时候看到了懒初始化的操作，所以回去看了一眼创建。
添加操作关注的主要有两个部分，
- 桶深过深转红黑树的操作
- 达到负载因子标准之后的扩容操作
创建
下面这行代码，请问HashMap的数组是在哪一行代码处创建的呢？
import java.util.HashMap;
public class HashMapLearn {
public static void main(String[] args) {
//1
HashMap<Integer,Integer> hashMap = new HashMap<>(16, 0.75F);
//2
hashMap.put(1,2);
}
}其实是在2处才创建。
还是看源码，可以看到，通过构造函数初始化的时候，只是赋值了一些容量类的参数。
也就是说，HashMap内部数组的创建，是懒式创建的。这点在我们后面看put源码的时候会看到。
懒初始化可以延迟资源的分配直到真正需要的时候，从而提高资源利用率和程序启动速度。
/* ---------------- Public operations -------------- */
/**
* Constructs an empty {@code HashMap} with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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;
this.threshold = tableSizeFor(initialCapacity);
}但是也未必是用了就是好的，其实懒初始化也会有别的可能的问题：
- 初次访问延迟：由于实际的资源分配被推迟到第一次使用时，这可能会导致初次访问时出现明显的延迟。
- 并发问题：在多线程环境下，如果没有适当的同步机制，懒创建可能导致竞态条件。比如两个线程几乎同时检测到资源未初始化并尝试同时初始化它，这可能会引起错误或不必要的重复工作。
- 复杂性增加：为了确保懒创建的安全性和效率，特别是在线程安全的场景下，可能需要引入额外的逻辑控制，如双重检查锁定模式(Double-Checked Locking)，增加了代码的复杂性和维护难度。
加入
put的源码其实也不是特别多，或者说其实HashMap的源码部分就不是特别多，我把我的思路及分析都写在了注释中了。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
//如果桶的位置为空，直接就加入了
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;
//如果不是链表的存储方式而是红黑树，那就得用树的插入方式
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//否则就寻找链表的最后一个节点或者对应的等key节点
for (int binCount = 0; ; ++binCount) {
//如果找遍了全部的桶都没找到，就创建一个新节点加在最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果桶深度等于8，同时还需要转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//找到了对应的key
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//没找到对应的key，在上面加了Node，同时要修改modCount
++modCount;
//size超过阈值，就要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}下面我们先看看扩容吧，其实转红黑树的代码我未必能看懂，所以我还是决定先看看扩容。
扩容
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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;
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;
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;
if (e.next == null)
//如果是单个节点，直接迁移，因为是高位扩容，所以直接放不会冲突
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//关于红黑树的拆分放桶的方法，这里就不多扩展了，后面补充在附录里吧
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//然后就是按照链表的顺序开始
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//然后这个时候就是进行while循环的处理
next = e.next;
//看这个节点是不是留在原桶,因为需要维护两个桶的尾
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 = next) != null);
//原桶的放到原桶位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位桶的放到高位
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}扩容这部分其实就些内容，其实难点还是在红黑树的那一块，但是我比较懒散没有详细去看。
桶过深转红黑树
主要是通过这一个方法来实现的
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
// 如果数组容量小于 MIN_TREEIFY_CAPACITY，则优先扩容，这个值是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;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
//如果是第一个节点，那么就是头节点，把p给hd
if (tl == null)
hd = p;
//如果不是，就是构建前后关系
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//然后就是调用这个转红黑树的方法
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}这是最核心的部分了，也就是红黑树的构建。
/**
* Forms tree of the nodes linked from this node.
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//遍历节点
next = (TreeNode<K,V>)x.next;
//首先是清空左右，为了防止遗留问题
x.left = x.right = null;
//如果是第一个节点，就把它设置为根节点，无父亲节点，非红节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
//否则就按照key的hash进行红黑树构建了
else {
K k = x.key;
int h = x.hash;
//用于存储键的比较类（如果键实现了 Comparable 接口）。
Class<?> kc = null;
//从根节点开始遍历
for (TreeNode<K,V> p = root;;) {
//dir表示当前节点应该插入到左子树（-1）还是右子树（1）。
int dir, ph;
K pk = p.key;
//哈希值比较：
//如果当前节点的哈希值小于 p 的哈希值，则插入到左子树。
//如果当前节点的哈希值大于 p 的哈希值，则插入到右子树。
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//如果哈希值相等，则进一步比较键值：
//如果键实现了 Comparable 接口，则使用 Comparable 进行比较。
//如果键未实现 Comparable 或比较结果相等，则调用 tieBreakOrder 方法进行仲裁。
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
//找到对应的插入位置
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//平衡红黑树
root = balanceInsertion(root, x);
break;
}
}
}
}
//绑定头节点到数组上
moveRootToFront(tab, root);
}平衡红黑树部分的代码感觉有点不太想看说实话，过段时间再看吧。
ConcurrentHashMap
其实我们可以关注到，HashMap几乎没有实现对多线程的关注，所以他是线程不安全的，那么ConcurrentHashMap又是如何实现线程的安全呢？其实这个比较容易被问到的问题，几乎所有的八股都会说什么分段锁啊，CAS操作啊，但是具体的源码实现是什么样子呢？很少有人关注，所以我这里来看一眼吧。
构造方法
首先还是看看构造方法
/**
* Creates a new, empty map with an initial table size based on
* the given number of elements ({@code initialCapacity}), initial
* table density ({@code loadFactor}), and number of concurrently
* updating threads ({@code concurrencyLevel}).
*
* @param initialCapacity the initial capacity. The implementation
* performs internal sizing to accommodate this many elements,
* given the specified load factor.
* @param loadFactor the load factor (table density) for
* establishing the initial table size
* @param concurrencyLevel the estimated number of concurrently
* updating threads. The implementation may use this value as
* a sizing hint.
* @throws IllegalArgumentException if the initial capacity is
* negative or the load factor or concurrencyLevel are
* nonpositive
*/
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
//初始容量不能小于并发级别
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}其实没有太多的修改，主要是增加了并发级别，要求了初始容量不能小于并发级别，其余的与HashMap一致
接下来就看看插入操作到底是怎么实现保证一致性的
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* <p>The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//spread 方法：
//对键的哈希值进行重新计算，以减少哈希冲突。
//公式为：(h ^ (h >>> 16)) & HASH_BITS，其中 HASH_BITS 是一个掩码。
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
//如果tab为空，初始化tab，为了阅读的连贯性，我们后面再看这个方法
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//如果为空桶，使用casTabAt
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
//这个MOVED其实是个特殊标记，表示当前正在进行扩容操作
//static final int MOVED = -1; // hash for forwarding nodes
else if ((fh = f.hash) == MOVED)
//这个方法还是挺核心的，主要作用是检测当前是否正在进行扩容操作，并参与协助完成扩容任务。
//如果发现某个桶（bucket）已经被标记为正在迁移（通过 ForwardingNode 标记），则该方法会尝试参与到迁移过程中。
//它的主要目标是加速扩容过程，通过允许多个线程并行地完成数据迁移。
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
//如果对应问题都没有出现，那就对f枷锁，然后把节点放入到对应的位置中去，这里的思路其实与HashMap一致
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}然后我们最后再看一眼InitTable
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//for循环，组钥匙cas操作
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
//如果sizeCtl<0，表示有其他值在init，就把时间片让出去
Thread.yield(); // lost initialization race; just spin
//否则就开始CAS操作，设置sizeCtl为-1，表示自己要初始化了
//初始化完成之后就break即可
else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
try {
//但是在CAS成功之后，会判断table是不是为空，如果为空才执行初始化，否则就直接进入finally段，单后break了。
//也就是CAS自旋成功之后才会break这个循环
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}完结
基本完结啦，后面如果我有时间的话会认真看看红黑树部分的代码的，但是现在可能对我来说留给我的时间确实不多了
附录，红黑树的split，注释和代码均来自通义千问
以下是 TreeNode.split 方法的核心逻辑（简化版）：
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// loHead 和 loTail 表示保留在原桶的节点链
TreeNode<K,V> loHead = null, loTail = null;
// hiHead 和 hiTail 表示需要移动到新桶的节点链
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 遍历红黑树的所有节点
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
// 判断节点属于哪个桶
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
} else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 将低桶（原桶）的节点放入新数组
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // 如果高桶也有节点，则需要保持红黑树结构
loHead.treeify(tab);
}
}
// 将高桶（新桶）的节点放入新数组
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null) // 如果低桶也有节点，则需要保持红黑树结构
hiHead.treeify(tab);
}
}
}