HashMap 是 Java 集合框架中非常重要的一个类，它基于哈希表实现，用于存储键值对（Key-Value Pair）。

1. 核心数据结构

HashMap 在底层主要依赖于两种数据结构：

• 数组（Array）：作为哈希表的主体，用于存储元素（更准确地说，是存储链表的头节点或树的根节点）。
• 链表（LinkedList） 或 红黑树（Red-Black Tree）：用于解决哈希冲突（Hash Collision）。当多个键（Key）经过哈希计算后映射到数组的同一个索引位置（称为“桶” Bucket）时，这些键值对会以链表的形式存储在该索引对应的位置上。在 JDK 1.8 及之后，当链表长度超过一定阈值（默认为8）时，链表会自动转换为红黑树，以提高查找效率；当红黑树中的节点数量减少到一定阈值（默认为6）时，树又会退化成链表。

2. 工作流程（以 put(K key, V value) 为例）

1. 计算键的哈希值： 首先，使用 hash(Object key) 方法计算键 key 的哈希值。这个方法不仅调用 key.hashCode()。

2. 计算桶索引： 利用计算得到的哈希值 hash，通过取模运算确定该键值对应在 table 数组中的索引位置 i，通常使用高效的位运算 (table.length - 1) & hash 。

3. 处理哈希冲突：

   • 如果 table[i] 为空，说明该位置没有冲突，直接创建一个新的 Node 节点并放入 table[i]。
   • 如果 table[i] 不为空（发生冲突）：
     • 首先检查 table[i] 节点的 key 是否与要插入的 key 相同（通过 equals 比较）。如果相同，则更新其对应的 value。
     • 如果不同：
       • 如果 table[i] 是链表节点：遍历该链表，检查是否有节点的 key 等于要插入的 key。如果找到，更新 value；如果没找到，则将新节点插入链表尾部（JDK1.7是头插法，JDK1.8改为尾插法）。
       • 如果 table[i] 是树节点（TreeNode）：调用红黑树的插入方法。
     • 在插入链表后，如果链表长度达到树化阈值（默认为8），且当前 table 数组长度达到最小树化容量（默认为64），则将该链表转换为红黑树。

4. 检查扩容： 插入新节点后，size 加1。然后检查 size 是否超过了 threshold。如果超过了，则调用 resize() 方法进行扩容。

3. 扩容机制 (resize())

扩容是 HashMap 性能的关键点之一。当需要扩容时：

1. 创建一个新的、容量更大的 Node 数组（通常是原数组长度的2倍）。
2. 遍历旧数组中的每个桶（Bucket）：
   • 如果桶中只有一个节点（没有冲突），直接根据其哈希值和新数组长度重新计算索引位置（(newCap - 1) & hash），放入新数组。
   • 如果桶中是链表：需要遍历链表，将链表节点重新分配到新数组的两个桶中（根据 (e.hash & oldCap) == 0 判断）。具体来说，如果 (e.hash & oldCap) == 0，则该节点应留在新数组的相同索引位置 i；如果不等于0，则应移动到新索引位置 i + oldCap。这个过程称为 rehash 或 重新散列。
   • 如果桶中是红黑树：也会按照类似逻辑进行拆分（可能拆分成两个链表或两个树），如果拆分后链表长度小于退化阈值（默认为6），则将树退化成链表。
3. 更新 table 引用指向新数组，并更新 threshold 为 (newCapacity * loadFactor)。

4. 查找 (get(Object key))

1. 计算键 key 的哈希值。
2. 计算桶索引 i = (table.length - 1) & hash。
3. 检查 table[i]：
   • 如果为空，返回 null。
   • 如果不为空：
     • 如果该节点的 key 等于要查找的 key（equals），则返回其 value。
     • 否则，如果该节点是树节点，调用树查找方法。
     • 如果是链表节点，则遍历链表查找。
4. 找到则返回 value，否则返回 null。

5. 总结

• 数据结构： 数组 + 链表 / 红黑树。
• 哈希冲突： 通过链地址法（Separate Chaining）解决。
• 扩容： 当元素数量超过 容量 * 负载因子 时，进行2倍扩容并重新散列。
• 性能： 在理想情况下（无冲突），put 和 get 操作的时间复杂度是 O(1)。在冲突严重时（链表很长），时间复杂度可能退化到 O(n)。引入红黑树后，最坏情况可优化到 O(log n)。
• 线程不安全： HashMap 不是线程安全的。多线程环境下，多个线程如果同时对一个桶进行插入，可能会形成循环链表，所以推荐使用 ConcurrentHashMap。
• 要记忆的关键属性：①负载因子0.75；②初始容量16；③存储元素超过16*0.75=12个时，会触发扩容操作，容量×2；④链表长度大于等于8且容量大于等于64时会触发链表转红黑树操作；⑤链表长度小于等于6时，又会退化成链表