HashMap

HashMap 的 put过程

在 HashMap 中，put 方法的执行过程大致如下：

1. 初始化检查：
   • 调用 putVal() 方法时，首先检查哈希表是否已初始化。如果没有初始化（即哈希表为空），则调用 resize() 进行初始化，通常是调整表的容量和负载因子。如果已经初始化，接下来会根据给定的 key 计算哈希值。
2. 计算槽位：
   • 通过 hash(key) 计算 key 的哈希值，并通过 hash & (n - 1) 计算出该哈希值对应的槽位索引。这一步是为了确定该 key 存储在哪个位置。
3. 插入过程：
   • 如果该槽位为空（即没有冲突），则直接在该槽位插入新的键值对。
   • 如果该槽位已经有节点，则需要判断该节点的结构。若该槽位是链表，遍历链表并检查是否有匹配的 key。若找到了相同的 key，则替换其 value，否则将新节点插入到链表的末尾。
   • 如果该槽位是树节点（当链表长度超过阈值时），则会将该节点与树结构中的其他节点进行比较，调用树结构的 put 方法进行插入。
4. 负载因子和扩容：
   • 在插入新元素后，检查当前 HashMap 是否超出负载因子的限制。如果哈希表的大小超过了负载因子与当前容量的乘积时，哈希表会自动扩容，即将哈希表的容量翻倍并重新计算每个元素的位置。
5. 扩容过程：
   • resize() 会调整哈希表的容量，并重新计算每个元素的槽位。需要注意的是，扩容是一个代价较高的操作，因为它涉及到元素的重新哈希和再分配。

resize()过程

1. 判断当前哈希表已经初始化,如果已经初始化，判断哈希表是否达到最大容量，如果没有达到，那么扩容，否则不扩容。 如果哈希表还没有初始化，但是阈值已设置。(说明指定了初始容量)，用阈值作为新容量。如果哈希表没有初始化且阈值没有设置 使用默认值。
2. 设置好新阈值和新容量之后，检查原来哈希表是否为null,如果不为null,遍历每一个桶,如果这个桶里面只有一个节点， 那么根据路由公式 e.hash & (newCap-1) 找到新桶，如果是红黑树的节点，那么调用红黑树的spilt方法. 如果是链表节点：

• (e.hash & oldCap) == 0: 它利用 e.hash 和 oldCap 之间的按位与操作，来分辨元素是属于哈希表的低位桶还是高位桶。 如果等于0 是 低位桶，索引保持不变，如果为1 是高位桶。索引位置=当前位置+旧容量。
• 低位链表放到新表原位置，高位链表放到新表新位置

JDK 1.7 HashMap 头插法设计原因

核心目标：提升插入效率。JDK 1.7 的 HashMap 在哈希冲突时采用链表解决，新节点直接插入链表头部（头插法）。这种设计的优势在于插入操作仅需修改相邻节点的引用，时间复杂度为 O(1)，无需遍历整个链表。

实现简化与性能优化。头插法避免了维护尾指针的开销，代码实现更简洁，且单线程场景下性能表现优异。但这一设计在多线程扩容时可能导致链表成环（后文详述）。

JDK 1.8 改为尾插法的直接原因

解决多线程扩容死循环问题。头插法在扩容时（resize）会反转链表顺序。若多线程并发执行扩容操作，可能因线程切换导致链表节点相互引用，形成环形结构（如 A→B→A）。后续查询操作遍历链表时会陷入死循环。

尾插法保持链表顺序。JDK 1.8 改为尾插法后，链表节点的顺序在扩容前后保持一致。即使多线程并发操作，也不会因顺序反转导致成环，从根源上避免了死循环问题。