HashMap的增加和扩容原理

写在前面

HashMap的知识，看八股肯定是不够的，所以来看看源码。

看很多源码之后才知道Java的一些类的实现有多么优雅，我只能用优雅来形容。

源码解读

我主要是从两个方面来看这部分的源码，一个是创建，一个是添加。其实重点还是添加，只不过我在添加的时候看到了懒初始化的操作，所以回去看了一眼创建。

添加操作关注的主要有两个部分，

1. 桶深过深转红黑树的操作
2. 达到负载因子标准之后的扩容操作

创建

下面这行代码，请问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);
}

但是也未必是用了就是好的，其实懒初始化也会有别的可能的问题：

1. 初次访问延迟：由于实际的资源分配被推迟到第一次使用时，这可能会导致初次访问时出现明显的延迟。
2. 并发问题：在多线程环境下，如果没有适当的同步机制，懒创建可能导致竞态条件。比如两个线程几乎同时检测到资源未初始化并尝试同时初始化它，这可能会引起错误或不必要的重复工作。
3. 复杂性增加：为了确保懒创建的安全性和效率，特别是在线程安全的场景下，可能需要引入额外的逻辑控制，如双重检查锁定模式(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);
        }
    }
}