🦋 HashMap - 源码分析 [ 🍧 Peach ]

🦋 HashMap - 源码分析

2023-03-09#Java #HashMap

- 目录
HashMap	HashMap 原理
HashMap	HashMap 源码

注：本文源码版本均为：JDK 8

一、属性

// 🔹 常量
// 默认的初始容量值（16）- 必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 最大容量上限（2的30次方）
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的负载因数（0.75）
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 树化阈值：当一个桶中的元素个数大于等于8时进行树化
static final int TREEIFY_THRESHOLD = 8;

// 树降级为链表的仓位计数阈值，当一个桶中的元素个数小于等于6时把树转化为链表。
static final int UNTREEIFY_THRESHOLD = 6;

// 将table树化的最小容量值（64）：当桶的个数达到64的时候才进行树化（至少应为4*TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。）
static final int MIN_TREEIFY_CAPACITY = 64;

// 🔹 变量
// Node数组，又叫作桶（bucket）
transient Node<K,V>[] table;

// 作为entrySet()的缓存
transient Set<Map.Entry<K,V>> entrySet;

// 元素的数量
transient int size;

// 记录hashMap的修改次数（每次扩容和更改 map 结构的计数器）
transient int modCount;

// 扩容阈值 = table.length * loadFactor（当size大于阈值时扩容）
int threshold;

// 负载因数：表示整体上table被占用的程度
final float loadFactor;

二、构造方法

graph LR

T(("HashMap
构造方法")):::p
T --> A(["HashMap map1 = new HashMap();"]):::lp
T --> B(["HashMap map2 = new HashMap(30);"]):::lp
T --> C(["HashMap map3 = new HashMap(30, 0.5f);"]):::lp
T --> D(["HashMap map4 = new HashMap(map);"]):::lp

A --- |"无参构造方法"|a("不指定容量，默认:16")
B --- |"initialCapacoty"| b("指定初始化容量：30")
C --- |"initialCapacoty
loadFactor"| c("指定初始化容量、负载因数")
D --- |"Map map"| d("以指定map构造新map")

D -.- ci("* 注意：
与上述仅创建空HashMap不同，
此方法内部调用了put()存值
table才真正进行了初始化。"):::info

classDef p fill:#ddaebd
classDef lp fill: #f4e4e9
classDef info fill:#f6f6f7,color:#737379,stroke-dasharray: 3 3, stroke-width: 2px

（1）HashMap()

无参数的构造方法

/**
 * Constructs an empty HashMap with the default initial capacity(16) and the default load factor (0.75).
 * 以默认初始容量(16)和默认负载因数(0.75)，构造一个空的HashMap。
 */
public HashMap() {
    // 🔻 将负载因数赋为默认值。
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

（2）HashMap(20)

带初始容量的构造方法：

/**
 * Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).
 * 以特定的初始容量和默认的负载因数(0.75)，构造一个空的HashMap
 *
 * @param  initialCapacity 初始容量
 * @throws IllegalArgumentException 初始容量为负值时抛出非法数据异常。
 */
 public HashMap(int initialCapacity) {
    // 🔻 调用了带初始容量、负载因数的构造方法（详见下文(3)）
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }

（3）HashMap(20, 0.5f)

带初始容量、负载因数的构造方法

/**
 * Constructs an empty HashMap with the specified initial capacity and load factor.
 * 以特定的初始容量和负载因数构造一个空的HashMap。
 *
 * @param  initialCapacity 初始化容量
 * @param  loadFactor      负载因数
 * @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;
    //  🔹 负载因数大于0且为数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                         loadFactor);

    // 🔴 二、为配置参数赋值
    //  🔹 为负载因数赋值
    this.loadFactor = loadFactor;
    //  🔹 为扩容阈值赋值：使用tableSizeFor()将给定数值调整为2的次幂数。
    this.threshold = tableSizeFor(initialCapacity);
}

（4）HashMap(map)

- HashMap()

带map的构造方法

/**
 * Constructs a new HashMap with the same mappings as the specified Map.
 * The HashMap is created with default load factor (0.75) and an initial capacity sufficient to hold the mappings in the specified Map.
 * 使用与指定Map相同的映射构造新的HashMap。
 * 此HashMap由：默认负载因数(0.75)、足够的初始容量（足以存下指定Map）创建。
 *
 * @param   m the map whose mappings are to be placed in this map
 * @参数：   m，原map
 * @throws  NullPointerException if the specified map is null
 * @异常：   当原map为空时抛出空指针异常。
 */
public HashMap(Map<? extends K, ? extends V> m) {
    // 🔻 将负载因数赋为默认值。
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 🔻 调用putMapEntries()，将原有map存入新map。
    putMapEntries(m, false);
}

- putMapEntries()

赋值并初始化函数

/**
 * Implements Map.putAll and Map constructor.
 * 赋值并构造函数。
 *
 * @param m the map
 * @参数： m，传入的map
 * @param evict false when initially constructing this map, else true (relayed to method afterNodeInsertion).
 * @参数： evict，首次创建此map时返回false，非首次创建返回true。
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size(); // m的元素个数
    // 🔴 一、若m中有元素，需要根据新Map的初始化情况为其扩容阈值赋值。 （若m无元素则无需赋值，直接使用给定的负载因数和扩容阈值(lf*cap)完成构造。）
    if (s > 0) {
        // 🔹 若数组未初始化：根据m中元素数量和负载因数计算新Map的扩容阈值。
        if (table == null) { // pre-size
            // m的扩容阈值 = 元素数量 / 负载因数（🔸+1.0F：对小数做向上取整以尽可能保证更大容量）
            float ft = ((float)s / loadFactor) + 1.0F;
            // 将m扩容阈值的数据类型转为整型，并限定在默认容量上限内
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 若计算出m的扩容阈值 > 新Map扩容阈值，调用tableSizeFor方法，将新Map扩容阈值设置为：该值最接近容量的2次幂数。
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 🔹 若数组已初始化、且Map中的元素数量超过了其扩容阈值：扩容。
        else if (s > threshold)
            resize();
        // 🔴 二、赋值：遍历m的entry，逐个赋值到新Map上。
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // 🔹 调用putVal()为每个节点赋值（此时新Map才真正初始化完成）
            putVal(hash(key), key, value, false, evict);
        }
    }
}

((float)s / loadFactor) + 1.0F + 1.0F：为了让浮点数进行除法计算后向上取整，以尽可能保证足够容量。

三、静态实用程序

- hash()

计算key.hashCode()

/* ---------------- Static utilities -------------- */
/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. 
 * 计算key.hashCode()并将哈希的高位扩展（异或运算）到低位。
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(h=key.hashCode()) ^ (h >>>16)

hash(Object) 方法通过以上表达式得到指定对象的Hash值。
这里是取得当前对象的Hash值，首先进行带符号位的右移16位操作（这时候对象Hash值的高位段就变成了低位段），然后与对象原来的Hash值进行异或运算。
异或的原因：

因为数组容量总是2的n次幂数，计算索引位置时，散列真正生效的只是低nbit的有效位，很容易发生碰撞。因此，把高16bit和低16bit异或一下，既减少了系统的开销，也不会造成因为高位没有参与下标的计算(table长度比较小)时，引起碰撞。

- tableSizeFor()

返回最接近给定目标容量的二次幂数值

/**
 * Returns a power of two size for the given target capacity.
 * 返回给定目标容量的二次幂数。
 */
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;
}


/* 以下为备注：
    -------------------------------------------------
      * 该位运算用于求出高位1之后每位都为1的结果。
        因为将每位变为1，则加上1后刚好是一个二次幂数。
        如(0000 1000)，使其第一位1后面都为1，即(0000 1111)
    ------------------------------------------------- */

        // 如，initialCapacity = 9
        // 🔴 将 n - 1
	int n = cap -1; // n = 8	

        // 🔴 作位运算：1. 无符号位移 2. 与n作或的位运算。
	n |= n >>> 1; 
	n = 0000 1000
	n = 0000 0100
	n = 0000 1100  

	n |= n >>> 2;
	n = 0000 1100
	n = 0000 0011
	n = 0000 1111  // =15

	n |= n >>> 4;
	n = 0000 1111
	n = 0000 0000  
	n = 0000 1111  

	n |= n >>> 8;
	n = 0000 1111
	n = 0000 0000
	n = 0000 1111  

	n |= n >>> 16;	
        // 🔸 因为int是32位的，所以执行到16即可.


        // 🔴 返回位移结果n + 1
	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUN_CAPACITY : n + 1;
	 n < 0, 则返回 n = 1 
	 n >= 0, 且 n >= 最大容量, 则返回最大容量 
	 n >= 0, 且 n < 最大容量, 则返回 n + 1 （=16）

为什么先进行n-1操作：为了处理n刚好是二次幂数的情况。

🦋 若n已经是2的n次幂了，按照逻辑变1之后再加1，结果就会变成n的2倍了，与应有的结果不一致。如，n=16（0001 0000），位运算后 n=31（0001 1111）。

- Comparable

/**
 * Returns x's Class if it is of the form "class C implements
 * Comparable<C>", else null.
 */
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

/**
 * Returns k.compareTo(x) if x matches kc (k's screened comparable
 * class), else 0.
 */
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

四、实现方法

（1）Get() - 获取

%%{
    init: {
    'themeVariables': {
        'fontSize': '13px'
    }
}   
}%%
graph TD
T(["如何从HashMap
获取元素？"]):::p
T --> B("先根据key找到桶位")
B --> A(["判断当前位置的元素
是否就要找的值"]):::lp
A --> |"是"| C2["核对k-v值后返回"]:::b
A --> |"否
（有hash冲突）"| C(["判断为链表或红黑树"]):::lp
C -.-> |"链表"|a["遍历链表、
核对k-v值后返回"]:::b
C -.-> |"红黑树"|b["从树的根节点查找、
核对k-v值后返回"]:::b

classDef p fill:#ddaebd
classDef b fill:#d9dfeb
classDef lp fill: #f4e4e9

- get()

通过key获取value

/**
 * Returns the value to which the specified key is mapped,
 * or null if this map contains no mapping for the key.
 * 返回指定key所映射的value值。若找不到对应value时返回null。
 *
 * 但返回null不一定代表不存在该key映射的值，有可能是该key保存的value值正是"null"。
 * 可以使用containsKey()来识别。
 */
public V get(Object key) {
    // Node
    Node<K,V> e;
    // 🔻 使用key和其hash值调用getNode()方法，返回Node的value值。
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

null ? null : e.value：若该值为null，返回null；若该值不为null，返回e.value

- getNode()

获取Node

/**
 * Implements Map.get and related methods.
 * 实现了Map.get()和相关方法
 *
 * @param hash key的hash值
 * @param key key
 * @return 返回该key对应的Node，若无返回null
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; // Node数组
    Node<K,V> first, e; // Node
    int n; // 数组长度
    K k; // key
    // 🔻 判断该数组非空
    //   并根据传入key的hash值计算出该hash值对应的Node的下标，将该数组下标对应的值赋值给first-Node（意为hash冲突时第一个节点）
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 🔹 先判断若first刚好是我们要找的Node时：直接返回first
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 🔹 当first尾部还有元素（即有hash冲突）时，根据Node的结构取值。
        if ((e = first.next) != null) {
            // 🔸 红黑树：将Node转为TreeNode类型，并调用getTreeNode()取值。
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 🔸 链表：遍历取值。
            do {
                if (e.hash == hash && // 判断hash值和key值都相同
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 🔻 数组为空，返回null
    return null;
}

（2）Remove() - 删除

%%{
    init: {
    'themeVariables': {
        'fontSize': '13px'
    }
}   
}%%
graph TD
T(["如何从HashMap
删除元素？"]):::p
T --> B("先根据key找到桶位")
B --> A(["判断当前位置的元素
是否就要删除的值"]):::lp
A --> |"是"| C2["直接删除该元素"]:::b
A --> |"否
（有hash冲突）"| C(["判断为链表或红黑树"]):::lp
C --> |"链表"|a["将上个位置的指针
（跳过该值）指向下个位置"]:::b
C --> |"红黑树"|b["去掉当前节点后自平衡"]:::b
b -.- bt["（树长度小于6时转为链表）"]:::info

classDef info fill:#f6f6f7,color:#737379stroke-width: 3px, stroke-dasharray: 3 3
classDef p fill:#ddaebd
classDef b fill:#d9dfeb
classDef lp fill: #f4e4e9

- remove()

删除元素

/**
 * Removes the mapping for the specified key from this map if present.
 * 根据指定key删除映射。
 *
 * @param  key 要从map中删除映射的键
 * @return 返回与键关联的前值，若前值为空返回null
 */
public V remove(Object key) {
    Node<K,V> e;
    // 🔻 调用removeNode()删除该键映射，若前值为空返回null，若前值非空返回前值。
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

- removeNode()

删除Node

/**
 * Implements Map.remove and related methods.
 * 实现删除和相关方法。
 *
 * @param hash       key的hash值
 * @param key        key
 * @param value      若有值时匹配该值
 * @param matchValue 若为真：仅值相等时删除
 * @param movable    为false:删除时不移动其他值
 * @return 返回Node，若无该Node返回null
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; // Node数组（引用当前hashMap的散列表）
    Node<K,V> p;     // 当前Node元素：p
    int n, index;    // n：数组长度，index：数组下标
    // 数组非空、当前索引位置的Node元素p非空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; // 要删除的Node元素：node；当前节点的下个节点：e(=p.next)
        K k; V v; // 当前元素p的key和value值
        // 🔹 第一个位置刚好是要删除的元素：赋值给node，执行下方修改指针的代码
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 🔹 存在哈希冲突时：根据链表或红黑树结构获取要删除的元素node
        else if ((e = p.next) != null) {
            // 🔸 红黑树：使用getTreeNode()获取元素，赋值给node。
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 🔸 链表：用hash值和键值对遍历：赋值给node。
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 🔴 根据元素(node)的结构删除
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 🔹 若要删除树结构节点：使用removeTreeNode()移除树节点
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 🔹 若要删除Node节点上的元素（刚好是第一个元素）：将该节点赋值为下个元素
            else if (node == p)
                tab[index] = node.next;
            // 🔹 若要删除链表节点：指向其下个元素的next，将链表链接起来。
            else
                p.next = node.next;
            ++modCount; // 记录修改次数（可以判断是否修改成功）
            --size; // 数组长度自减
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

（3）Put() - 添加

%%{
    init: {
    'themeVariables': {
        'fontSize': '13px'
    }
}   
}%%
graph TD
T(["如何向HashMap
添加元素？"]):::p
T --> B("先根据key找到桶位")
B --> A(["判断当前索引是否
就是要添加元素的位置"]):::lp
A --> |"无元素"| C2["直接将元素添加到该位置"]:::b
A --> |"有元素
（有hash冲突）"| C(["判断为链表或红黑树"]):::lp
C --> |"链表"|a["将元素添加到链表尾部"]:::b
C --> |"红黑树"|b["将元素添加到树尾部"]:::b
a -.- at["链表长度超过8、且桶数量大于64时转为树
（*桶数小于64时不会树化，只会扩容）"]:::info

classDef info fill:#f6f6f7,color:#737379stroke-width: 3px, stroke-dasharray: 3 3

classDef p fill:#ddaebd
classDef b fill:#d9dfeb
classDef lp fill: #f4e4e9

+ put()

添加元素

/**
 * Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
 * 存值：将指定值与此映射中的指定键相关联。如果映射先前包含键的映射，则将替换旧值。
 *
 * @param key 
 * @param value 
 * @return 返回被替换的原值
 */
public V put(K key, V value) {
    // 调用putVal()方法存值
    return putVal(hash(key), key, value, false, true);
}

- putVal()

赋值方法（若key已有值时默认替换）

/**
    * Implements Map.put and related methods.
    * 实现了Map赋值以及相关方法。
    *
    * @param hash         key的hash值
    * @param key          key值
    * @param value        需要赋的值
    * @param onlyIfAbsent 是否保留原值（默认为false：会替换原值）
    * @param evict        false:表处于创建状态
    * @return 返回前值，如果没有则为空
    */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; // Node数组
    Node<K,V> p; // Node
    int n, i; // n：数组长度， i：数组索引
    // 🔴 一、若空数组：初始化
    //       当数组为空、长度为0时：扩容，并获得Node数组长度n（容量）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 🔴 二、若空索引：直接存
    //       若传入的key计算出的索引位置无元素，则使用键值对在该位置上创建Node，putVal()完成。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 🔴 三、若索引非空：根据情况存值
    //       可能有hash冲突，判断该Node是否为链表或红黑树进行存值。
    else {
        Node<K,V> e; // node
        K k; // key
        // 🔹 若p刚好在当前索引位置的第一个节点上（未涉及到链表或红黑树），将该Node赋值给e以备存值（当前Node的key值和传入的key值相等）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 🔹 TreeNode类型：通过putTreeVal()方法在红黑树上插入键值对，赋值给e以备存值。
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 🔹 链表类型：循环直到将元素插入链表尾部，赋值给e以备存值。
        else {
            for (int binCount = 0; ; ++binCount) { // binCount：链表节点个数
                // 🔸 若已遍历到链表尾部：使用newNode()在尾部再添加一个新节点并存值。
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // * 若添加节点后链表的长度超过树化阈值：
                    //   通过treeifyBin()将链表转化为红黑树，跳出循环，putVal()完成。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 🔸 若还未遍历到尾部、且该节点的key值与传入key值相等：
                //    则跳出循环，执行下方替换原值的判断。
                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;
        }
    }
    ++modCount; // 记录修改次数（方便在迭代中检测结构性变化）
    // 🔻 若存值后元素数量大于扩容阈值，则扩容。
    if (++size > threshold) 
        resize();
    afterNodeInsertion(evict); // 插入后回调（❓
    return null;
}

比较时先比较hash值，hash相同的时候，再使用equals方法进行比较：
if(e.hash == hash && ((k = e.key) == key || key.equals(k)))
因为hash是整数，比较的性能一般要比equals()高很多，使用短路与：hash不同，就没有必要调用equals方法了，这样整体上可以提高比较性能。

+ putIfAbsent()

赋值，且已有值时不进行覆盖

@Override
public V putIfAbsent(K key, V value) {
    // 🔻 与默认的put()区别在于第四个参数：onlyIfAbsent（为true时不覆盖原值）
    return putVal(hash(key), key, value, true, true);
}

（4）*Resize() - 扩容

① 何时扩容

%%{
    init: {
        'themeVariables': {
            'fontSize': '14px'
        }
    }
}%%
graph TD
T(["HashMap何时需要扩容？"]):::p
T --> |"1. 初始化"| A("1. table为null 或长度为0时"):::lp
T --> |"2. 存值"| B("2. 添加元素且元素数量即将超过
扩容阈值（threshold）时"):::lp
B -.- |"hreshold 可以由 tableSizeFor() 计算得到"| b["tableSizeFor()：可以计算出大于当前方法入参值，
并且和当前方法入参值最接近的2的幂数。"]:::info
classDef p fill: #ddaebd
classDef lp fill: #f4e4e9
classDef lb fill: #d9dfeb
classDef info fill:#f6f6f7,color:#737379, stroke-width: 2px, stroke-dasharray: 3 3

② 如何扩容

%%{
  init: {
      'themeVariables': {
          'fontSize': '14px'
      }
  }
}%%
graph TD
T(["HashMap如何扩容？"]):::p
T --> A("2倍扩容，创建新数组")
A --> B("移动元素到新数组
（重新计算hash）")
B --> b(["判断元素类型调整位置"]):::lp
b -.-|"单个值"| b1["①原位置
② 原位置 + 原容量"]:::lb
b -.-|"红黑树"| b2["split()分割树
①一棵：原位置
②另一棵：原位置 + 原容量"]:::lb
b -.-|"链表"| b3["①低位链表：原位置
②高位链表：原位置 + 原容量"]:::lb
b2 -.- b2t["若树节点数量≤6：转链表"]:::info
classDef p fill: #ddaebd
classDef lp fill: #f4e4e9
classDef lb fill: #d9dfeb
classDef info fill:#f6f6f7,color:#737379, stroke-width: 2px, stroke-dasharray: 3 3

调整位置的原因：

因为HashMap计算索引位置是根据hash值 & (当前容量 -1)，因此当容量改变时，一些原本的索引位置也会发生改变。扩容的同时重新调整元素位置，取值时才能正确匹配到相应的键值对。

③ 如何调整位置

元素位置如何改变？

%%{
  init: {
      'themeVariables': {
          'fontSize': '14px'
      }
  }
}%%
graph TD 
T(["元素位置如何改变？"]):::p
T --> A("hash值 & 原长度"):::lb
A --> a["结果为0，位置不变"]:::lp
A --> b["结果为1，在新位置"]:::lp
a -.- at["如，原hash值=3（原位置=3），
数组长度16， hash & 16：
 0000 0011 // 3 
 0001 0000 // 16 
 0000 0000 // =0
则，新位置 = 原位置 = 3"]:::info
b -.- bt["如，原hash值=19（原位置=3），
数组长度16，hash & 16：
 0001 0011 // 19 
 0001 0000 // 16 
 0001 0000 // =1
则，新位置 = 原位置 + 原容量 = 19"]:::info
classDef p fill: #ddaebd
classDef lp fill: #f4e4e9
classDef lb fill: #d9dfeb
classDef info fill:#f6f6f7,color:#737379, stroke-width: 2px, stroke-dasharray: 3 3

满足“(e.hash & oldCap)==0”条件的节点可以继续在原索引位上存储，不满足该条件的节点则需要进行移动操作。

HashMap中，table数组都是以2的幂数进行扩容操作的，就是将原容量值左移1位。
因此进行扩容操作后，各个K-V键值对节点是否仍能在原索引位上，取决于新增的一位（oldCap的值）在进行与运算时是否为0。

链表元素移动：
1. 满足“(e.hash & oldCap)==0”条件的节点会构成新的单向链表，这个链表中的节点会按照原索引位顺序存储于新的HashMap集合的table数组中；
2. 满足“(e.hash &oldCap) !=0”条件的节点会构成另一个新的单向链表，并且将原索引值+原数组长度的计算结果作为新的索引值存储于新的HashMap集合的table数组中。
红黑树元素移动：
- 将这棵红黑树拆分成两棵新的红黑树：（若红黑树中节点数≤6，会将树结构转为链表结构）
  ① 一棵红黑树（或链表）留在原索引位上，
  ② 另一棵红黑树（或链表）放到原索引值+原数组容量值计算结果对应的新索引位上。

- resize()

扩容

/**
 * 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.
 * 初始化或二倍扩容。若为空，根据阈值和初始容量分配。
 * 由于使用2次幂扩容，因此每个元素保持相同索引，或在新表中以二次幂偏移量移动。
 *
 * @return table
*/
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // 原table
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的table长度，若无元素返回0
    int oldThr = threshold; // 原阈值
    int newCap, newThr = 0; // 新长度、新阈值
    // 🔴 一、设置扩容阈值
    //  🔹 ① 若已初始化(原数组有元素)：检查数组长度并设置2倍扩容阈值。
    if (oldCap > 0) {
        //  🔸 若原数组长度超过最大容量值：—> 已到达容量上值，无法再扩容，返回原表。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //  🔸 若原数组长度2倍扩容后仍未超过容量上限，且原数组长度超过了默认初始容量：—> 原扩容阈值设置为2倍。
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //  🔹 ② 若未初始化(原数组无元素)，但已设置过扩容阈值(>0) ：将新数组长度设置为该扩容阈值。
    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);
    }

    // 🔴 二、检查扩容阈值
    // 若新扩容阈值仍为0：使用新数组长度计算新的扩容阈值（并将数组长度限制在最大容量上限内）
    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) {
                // 清空原值，便于GC回收。
                oldTab[j] = null;
                // ① 单个值
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e; // 原位 或 +旧容量oldCap
                // ② 红黑树：分割
                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 {
                        next = e.next;
                        // true：位置不变（低位链表）
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // false：位置 + 容量（高位链表）
                        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;
}

五、内部类

（1）Node

HashMap.Node类：

/**
 * Basic hash bin node, used for most entries.  (See below for TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 * 基本hash的bin节点，用于大部分节点。（TreeNode子类见下文，Entry子类见LinkedHashMap。）
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key; // final：由于key是计算元素排列位置的依据，因此一旦初始化就不允许改变。
    V value;
    Node<K,V> next; // 下一个节点（因为需要用Node节点构建单向链表）

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    // 🔻 重写hashCode()：将key的Hash值、value的Hash值进行异或运算。
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    // 🔻 重写equals()
    public final boolean equals(Object o) {
        // 🔹 ① 判断两个节点的内存起始地址相同
        if (o == this)
            return true;
        // 🔹 ② 判断两个Map类型节点的key和value值都相等
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

重写HashCode()

Java官方对重写对象的 hashCode() 方法有严格的要求 —— 若重写 hashCode() 方法，则需要重写相应的 equals() 方法。

补充：Objects工具类

graph LR
T(["Objects
工具类"]):::p
T --> A("提供了进行对象比较、
检验的基本操作"):::lb
A --> 1(["compare(T, S, Comparator)"]):::lp
A --> 2(["hashCode(Object)"]):::lp
A --> 3(["hashCode(Object[])"]):::lp
A --> 4("isNull(Object)、
nonNull(Object)、
requireNonNull(Object)等"):::lp
A --> 5(["toString(Object)"]):::lp
1 -.- 1t["两个对象的比较操作"]
2 -.- 2t["计算对象Hash值"]
3 -.- 3t["计算多个对象的Hash值组合"]
4 -.- 4t["校验或确认当前对象是否为空"]
5 -.- 5t["返回对象的字符串信息"]
classDef p fill: #ddaebd
classDef lp fill: #f4e4e9
classDef lb fill: #d9dfeb

根据哈希值存取对象、比较对象是计算机程序中一种重要的思维方式。

它使得存取对象主要依赖于自身Hash值，而不是与其他对象进行比较，存取效率也与集合大小无关，高达O(1)，即使进行比较，也利用Hash值提高比较性能。

（2）TreeNode

TreeNode 继承自 LinkedHashMap.Entry 类。

HashMap集合使用 HashMap.TreeNode 类的对象表示红黑树中的节点，来构成红黑树。

① 当某个索引位上的链表长度达到指定的阈值（默认为单向链表长度超过8）时，单向链表会转化为红黑树；
② 当红黑树中的节点足够少（默认为红黑树中的节点数量少于6个）时，红黑树会转换为单向链表。

- 属性

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    // 父节点
    TreeNode<K,V> parent;  // red-black tree links
    // 左节点
    TreeNode<K,V> left;  
    // 右节点
    TreeNode<K,V> right;  
    // 前节点：删除时需要取消链接"next"
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    // 节点颜色：true红色；false黑色 
    boolean red;

    // 构造方法，参数：hash值、key、value、下一个Node节点
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    // ...
    // 还有构建红黑树、解构红黑树、添加节点、移除节点等方法
}

- getTreeNode()

获取红黑树节点

 /**
 * Calls find for root node. 
 * 调用查找根节点
 */
final TreeNode<K,V> getTreeNode(int h, Object k) {
    // 🔻 调用find()查找节点
    return ((parent != null) ? root() : this).find(h, k, null);
    // 若根节点不为空，调用root节点查找；若根节点为空，使用this查找。
}

- find()

查找树节点

/**
 * Finds the node starting at root p with the given hash and key. The kc argument caches comparableClassFor(key) upon first use comparing keys.
 * 使用给定的key和hash值查找从根p开始的节点。
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this; // 当前树形Node：p
    // 遍历整树：
    do {
        int ph, dir; 
        K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q; // 当前Node左节点、右节点、
        // 若当前节点hash值较大：p取其左节点
        if ((ph = p.hash) > h)
            p = pl;
        // 若当前节点hash值较小：p取其右节点
        else if (ph < h)
            p = pr;
        // 若当前节点key值等于给定key值，返回当前节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 若左节点为空，p取其右节点
        else if (pl == null)
            p = pr;
        // 若右节点为空，p取其左节点
        else if (pr == null)
            p = pl;
        // 根据compareTo比较
        else if ((kc != null ||
                    (kc = comparableClassFor(k)) != null) &&
                    (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        // 根据compareTo的结果，若右节点能找到：返回右节点
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        // 若compareTo的结果在左节点上：继续查找
        else
            p = pl;
    } while (p != null);
    return null;
}

- split()

分割树结构（HashMap扩容时使用到的方法）

/**
    * Splits nodes in a tree bin into lower and upper tree bins, or untreeifies if now too small. Called only from resize; see above discussion about split bits and indices.
    * 分割该树为两棵树，若树太小则链化。
    *
    * @param map 
    * @param tab table
    * @param index 被分割树的索引位置
    * @param bit 扩容前的原数组容量
    */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this; // 当前树节点
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0; // 遍历时计算链表的长度
    // 🔴 一、重新计算索引位置（遍历双向链表结构）
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        // 🔻 拆分：割断当前节点的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; // 记录长度
        }
    }

    // 🔴 二、移动元素（将两个新链表树化或取消树化）
    //  🔹 0：原位置
    if (loHead != null) {
        // 🔸 若节点≤树化阈值：取消树化，转为链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        // 🔸 若节点≥树化阈值：树化
        else {
            // 将链表存入table索引位置
            tab[index] = loHead;
            // 确认链表存在元素后树化
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    // 🔹 1：新位置（原位置 + 原容量）：同上
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

🦋 红黑树中隐含的双向链表结构：
① 在将红黑树结构转换为链表结构的过程中，需要使用这个隐含的双向链表进行遍历；
② 在红黑树结构的拆分过程中，也需要使用这个隐含的双向链表进行遍历。

（3）Iterators

- nextNode()

HashMap实现了Iterator(迭代器)接口。

abstract class HashIterator {
        Node<K,V> next;        // 将返回的下个entry
        Node<K,V> current;     // 当前 entry
        int expectedModCount;  // 用于快速失败的属性
        int index;             // 当前索引
    
    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }
    
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        // 若modCount不等于expectedModCount：抛出异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // 若指定Node为空：抛出异常
        if (e == null)
            throw new NoSuchElementException();
        // 若next指向的Node（即当前Node的next的值）不为空，且数组不为空：
        if ((next = (current = e).next) == null && (t = table) != null) {
            // 限定索引不超出长度、且下个位置仍有元素。
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
    // ... 
    // EntryIterator，继承自HashIterator
    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
}

遍历元素时使用modCount属性判断HashMap是否发生结构性变化

🔹 属性：
- modCount：HashMap类中的一个成员变量，表示对HashMap的修改次数。（与ArrayList和LinkedList相同）
- expectedModCount：表示对hashMap修改次数的期望值，它的初始值为modCount。
- ConcurrentModificationException()异常：此异常为了防止在使用Iterator遍历容器的同时又对容器作增加或删除操作，或者使用多线程操作。

🔹 说明：
HashMap的Iterator是fail-fast迭代器。每次发生结构性变化时modCount都会增加，而每次迭代器操作时都会检查expectedModCount是否与modCount相同，这样就能检测出结构性变化。当有其他线程改变了HashMap的结构（增加、删除、修改元素），将会抛出ConcurrentModificationExceptidon。

🔹 解决方法：
在遍历的过程中把需要删除的对象保存到一个集合中，等遍历结束后再调用removeAll方法来删除，或者通过Iterator的remove()方法移除元素。

- end -

参考：

HashMap扩容部分：《Java高并发与集合框架：JCF和JUC源码分析与实现》
内存结构示意图部分：《Java编程的逻辑》

🍧 Peach