jdk版本：JDK11

其内部使用哈希表（hash table）来组织数据，通过哈希函数将键映射到桶（bucket）中

• 数组部分：哈希表内部确实包含一个数组，这个数组的每个元素被称为桶（bucket）。当向哈希表中添加元素时，根据键的哈希码计算出一个索引，该索引决定了元素应该被放置在数组的哪个位置（即哪个桶中）。

• 处理冲突：由于不同的键可能产生相同的哈希码，或者即使哈希码不同也可能映射到同一个索引位置，这就产生了所谓的“哈希冲突”。为了解决这个问题，每个桶可以是一个更复杂的数据结构，例如：

  • 链表：最常见的方式是将所有映射到同一桶的元素链接成一个链表。这种方式称为链地址法（separate chaining）。
  • 红黑树：在 Java 的 HashMap 中，如果一个桶中的链表长度达到了一定阈值（默认8个节点），并且哈希表的容量大于等于64，链表会转换为红黑树，以提高查找效率。

几个核心方法：

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 {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        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;
                }
            }
            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;
    }

putVal 方法是 HashMap 内部用于插入键值对的核心方法。它负责处理哈希冲突、检查是否需要调整大小（resize）、以及在适当的时候将链表转换为红黑树等操作。以下是这个方法的详细解析：

方法参数

• int hash: 键对象的哈希码，已经计算好。
• K key: 要插入的键。
• V value: 与键关联的值。
• boolean onlyIfAbsent: 如果为 true，则仅当键不存在时才插入新值；如果为 false，则总是更新现有键的值。
• boolean evict: 通常用于某些特殊场景，如LinkedHashMap中实现LRU缓存时决定是否移除最旧条目。

方法逻辑

1. 初始化和容量检查：

   • 检查内部数组 table 是否为空或长度为0。如果是，则调用 resize() 初始化或扩容数组，并获取新的数组长度 n。

2. 确定桶位置：

   • 使用 (n - 1) & hash 来计算键应该放置在哪个桶的位置 i。这相当于取模运算但更高效，因为 n 总是2的幂次方。

3. 处理空桶情况：

   • 如果目标桶 tab[i] 是空的（即没有节点），则直接创建一个新的 Node 并放入该桶。

4. 处理非空桶情况：

   • 如果桶不为空，检查第一个节点是否就是我们要找的键（通过比较哈希码和键）。
   • 如果是，则记录下该节点 e 以备后续更新值。
   • 如果不是，并且该桶是一个 TreeNode（即红黑树），则调用 putTreeVal 方法来处理红黑树中的插入。
   • 否则，遍历链表直到找到匹配的键或者到达链表末尾。如果找到匹配的键，则设置 e 并跳出循环；如果没有找到，则在链表尾部添加新节点，并检查是否需要将链表转换为红黑树（当链表长度达到 TREEIFY_THRESHOLD 时）。

5. 更新现有键的值：

   • 如果找到了现有的键 e，则根据 onlyIfAbsent 参数决定是否更新其值，并返回旧值。

6. 增加修改次数和元素数量：

   • 更新 modCount 以反映结构上的改变，这对迭代器的快速失败特性很重要。
   • 增加 size 计数器，并检查是否需要扩容。

7. 扩容：

   • 如果当前元素数量超过了阈值 threshold，则调用 resize() 方法进行扩容。

8. 回调方法：

   • 调用 afterNodeAccess 和 afterNodeInsertion 回调方法，这些方法可以被子类重写以实现特定的行为，例如 LinkedHashMap 中维护访问顺序。

9. 返回结果：

   • 如果更新了已有的键，则返回旧值；否则返回 null。

关键点总结

• putVal 方法是 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;
                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 {
                            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;
    }

resize() 方法是 HashMap 中用于处理哈希表扩容的核心方法。当当前哈希表的大小（元素数量）超过了阈值时，就会触发扩容操作。扩容不仅仅是简单地增加数组的容量，还需要重新计算每个键值对的桶位置，并将它们重新分配到新的、更大的数组中。以下是该方法的工作原理和详细解析：

方法逻辑

1. 初始化变量：

   • oldTab: 当前的哈希表数组。
   • oldCap: 当前哈希表的容量（即数组长度）。
   • oldThr: 当前的阈值，即在不进行扩容的情况下哈希表能够容纳的最大元素数。

2. 检查现有容量：

   • 如果 oldCap 大于0，表示哈希表已经初始化过。
     • 如果当前容量已经达到或超过最大容量 (MAXIMUM_CAPACITY)，则不再扩容，直接返回当前表。
     • 否则，尝试将容量翻倍（newCap = oldCap << 1），并且如果旧容量至少为默认初始容量 (DEFAULT_INITIAL_CAPACITY)，也相应地将阈值翻倍。

3. 处理未初始化的情况：

   • 如果 oldCap 等于0，但 oldThr 大于0，这意味着在构造函数中指定了初始容量，此时将新容量设为 oldThr。
   • 如果两者都为0，则使用默认的初始容量和负载因子来计算新的容量和阈值。

4. 计算新的阈值：

   • 如果 newThr 仍然为0，根据新的容量和负载因子计算新的阈值。

5. 更新阈值：

   • 将新的阈值赋给 threshold，以便后续插入操作可以依据新的阈值判断是否需要再次扩容。

6. 创建新的数组：

   • 使用新的容量创建一个新的节点数组 newTab，并将其赋值给 table。

7. 迁移旧数据：

   • 遍历旧数组中的每一个非空桶，对于每个桶内的链表或红黑树执行以下操作：
     • 如果桶内只有一个节点，直接将其放置在新数组对应的位置。
     • 如果桶内是一个红黑树，则调用 TreeNode.split 方法来分割树并将子树放入新的数组。
     • 如果桶内是一个常规链表，则遍历链表，并根据哈希码的低位将链表分为两个部分：一部分保持原位置，另一部分移动到新数组中一个更远的位置（索引加上旧容量）。这确保了即使在扩容后，哈希冲突仍然尽可能少。

8. 返回新数组：

   • 最后，返回新创建的数组 newTab，完成扩容过程。

关键点总结

• resize() 方法不仅增加了哈希表的容量，还通过重新计算每个键值对的桶位置，有效地减少了哈希冲突的可能性。
• 它保证了在扩容过程中尽量减少性能开销，同时维持了哈希表的良好性能特性。
• 特别注意的是，在扩容时对于红黑树的处理，它会根据实际情况决定是否继续以树的形式存储，还是退化回链表形式。

这个方法设计得非常精巧，能够在保证性能的同时处理各种边界情况，如最大容量限制等。

关键参数：

1. DEFAULT_INITIAL_CAPACITY (默认初始容量):  1 << 4; // aka 16

   • 定义了 HashMap 在创建时如果没有指定容量的情况下，默认使用的数组大小。
   • 值为 1 << 4，即 16。这意味着在没有特别指定的情况下，HashMap 内部会初始化一个长度为16的数组。

2. MAXIMUM_CAPACITY (最大容量):  1 << 30;

   • 指定了 HashMap 数组的最大容量，防止其无限增长。
   • 值为 1 << 30，即 1,073,741,824（大约1GB）。这个值必须是2的幂，并且不超过 1 << 30，以确保索引计算不会溢出。

3. DEFAULT_LOAD_FACTOR (默认负载因子):  0.75f;

   • 控制了 HashMap 在什么情况下应该进行扩容。负载因子是一个介于0到1之间的浮点数，它决定了哈希表可以填充多少比例的桶之前需要扩容。
   • 默认值为 0.75f，表示当哈希表中元素的数量达到容量的75%时，将触发扩容操作。负载因子的选择是在时间和空间之间的一种权衡：较高的负载因子减少了内存使用但增加了碰撞几率；较低的负载因子则相反。

4. TREEIFY_THRESHOLD (树化阈值):  8;

   • 确定了在单个桶中的链表长度达到多少时应该转换成红黑树以提高查找效率。
   • 默认值为8，意味着如果某个桶中的节点数量达到了8个，并且哈希表的容量大于等于 MIN_TREEIFY_CAPACITY，那么该链表将会被转换为红黑树。

5. UNTREEIFY_THRESHOLD (退化阈值):  6;

   • 当桶中的节点数量减少至低于此值时，红黑树会被转换回链表形式。
   • 默认值为6，这有助于避免不必要的复杂数据结构维护成本。

6. MIN_TREEIFY_CAPACITY (最小树化容量): 64;

   • 指定了只有当哈希表的容量至少为此值时，才会考虑将链表转换为红黑树。
   • 默认值为64，保证了只有在哈希表足够大并且确实存在大量哈希冲突的情况下，才采用更复杂的数据结构来优化性能。

字段详解

1. transient Node<K,V>[] table;

   • 这是 HashMap 内部存储键值对的核心数组，每个元素是一个桶（bucket），可以是一个链表或红黑树的头节点。
   • 数组在第一次使用时初始化，并根据需要调整大小。数组长度始终是2的幂次方，以确保哈希码与索引之间的映射高效且均匀分布。

2. transient Set<Map.Entry<K,V>> entrySet;

   • 用于缓存 entrySet() 方法的结果，即所有键值对的集合视图。这个字段的存在可以避免每次调用 entrySet() 时都重新创建集合对象。
   • 注意到 AbstractMap 已经提供了 keySet() 和 values() 方法的基础实现，因此这里只额外维护 entrySet。

3. transient int size;

   • 记录当前 HashMap 中实际包含的键值对数量。
   • transient 关键字意味着该字段不会被序列化，因为它的值可以在反序列化后通过其他字段重新计算出来。

4. transient int modCount;

   • 记录 HashMap 自创建以来发生的结构性修改次数。结构性修改是指那些改变映射数量或内部结构的操作，如插入、删除和扩容。
   • 此字段用于使迭代器“快速失败”（fail-fast）。当迭代器检测到自创建以来发生了未预期的结构性修改时，会抛出 ConcurrentModificationException 异常，以防止潜在的数据不一致问题。

5. int threshold;

   • 下一次扩容的阈值，等于容量乘以负载因子 (capacity * load factor)。
   • 如果 table 数组尚未分配，则此字段保存初始数组容量，或者为0表示使用默认初始容量。
   • 在序列化过程中，此字段会被持久化，以确保反序列化后的实例能够正确地恢复其状态。

6. final float loadFactor;

   • 哈希表的负载因子，决定了哈希表在什么情况下应该进行扩容。它是一个介于0到1之间的浮点数，默认为0.75。
   • 负载因子的选择是在时间和空间之间的一种权衡：较高的负载因子减少了内存使用但增加了碰撞几率；较低的负载因子则相反。
   • 使用 final 关键字修饰，意味着一旦设置就不能更改，保证了实例的一致性。