HashMap底层原理概述

• HashMap底层原理

  HashMap是一种基于哈希表的数据结构，用于存储键值对。其底层实现主要依赖于数组、链表和红黑树。

  一、数据结构

  • 数组：HashMap内部维护一个数组，数组的每个元素称为一个桶（bucket）。
  • 链表与红黑树：当多个键值对映射到同一个桶时，会形成链表。若链表长度超过一定阈值（默认为8），且数组长度达到64，则链表会转换为红黑树，以提高查询效率。

  二、Put操作过程

  1. 1.计算Hash值：通过Key的hashCode方法计算hash值，并进行特定的位运算（高位右移16位后与原哈希码异或），以减少哈希冲突。

  2. 2.确定数组下标：使用hash & (n-1)计算键值对在数组中的下标，其中n为数组长度。

  3. 插入或更新键值对

     ：

     • 若对应下标无元素，直接插入新Node。
     • 若已有元素，通过equals方法比较Key：
       • 若相同，则更新Value。
       • 若不同，则发生哈希冲突，将新Node插入链表头部。

  4. 4.链表转红黑树：当链表长度超过8且数组长度达到64时，链表转换为红黑树。

  三、扩容机制

  1. 1.触发条件：当HashMap中的元素数量超过容量与负载因子的乘积（默认阈值为12，即16 * 0.75）时，触发扩容。

  2. 扩容过程

     ：

     • 确定新容量：新容量为原容量的两倍。

     • 创建新数组：根据新容量创建新的Node数组。

     • 重新哈希与迁移

       ：

       • 遍历旧数组的每个桶。
       • 对于桶中的每个元素（链表或红黑树），重新计算其在新数组中的位置，并插入。
       • 若涉及红黑树，可能需要进行拆分和重组。

     • 更新内部状态：将HashMap的内部数组引用指向新数组，并更新阈值。

  四、其他注意事项

  • HashMap的初始容量为16，默认负载因子为0.75。这些参数可在创建HashMap时进行自定义设置。
  • HashMap不是线程安全的。在多线程环境下，可以考虑使用ConcurrentHashMap等线程安全的替代方案