一、 哈希表结构

• 基本构造：HashMap 底层采用哈希表实现，内部由一个数组（称为桶数组）构成，每个数组位置（桶）存储若干数据。
• 数据组织：每个桶中的数据通常以链表存储，在发生大量冲突时，当链表长度超过一定阈值，会转换为红黑树以提升查找效率。

二、 哈希函数的作用

• 映射机制：插入数据时，HashMap 通过哈希函数计算键的哈希值，进而确定该键值对存储在桶数组中的索引位置。
• 冲突可能性：不同的键可能会产生相同的哈希值（哈希冲突），这时会采用相应策略处理冲突。通过 (key.hashCode() ^ (key.hashCode() >>> 16)) 计算哈希值，减少低位相似键的冲突概率。

三、 处理哈希冲突

• 链式法（Separate Chaining）：大多数情况下，冲突的键值对会被存放在同一个桶内的链表中。
• 红黑树优化：当单个桶内元素数量过多时（链表长度超过预设阈值），链表会转换为红黑树，从而将查找复杂度降低至 O(log n)。当单个桶内链表长度超过8 且桶数组容量达到64 时，链表会转换为红黑树；若数组容量不足64，则优先触发扩容。当红黑树节点数减少至6以下时，会退化为链表以节省空间。

四、 动态扩容与负载因子

• 负载因子：负载因子定义了哈希表允许填充的程度，默认值为 0.75。即当已存储的元素数量达到数组容量的 75% 时，会触发扩容。
• 扩容机制：扩容过程中，HashMap 会创建一个更大的桶数组（通常为原容量的2倍），并重新计算所有元素的桶索引，保证操作性能不受影响。

五、 基本操作及其性能

• 查找：计算键的哈希值确定桶位置，再在桶内（链表或红黑树）查找对应的键值对。平均时间复杂度为 O(1)。
• 插入：同样通过哈希函数定位桶位置，若发生冲突，则将新元素追加到链表或插入到红黑树中。
• 删除：根据键的哈希值定位桶后，从链表或红黑树中删除相应的节点。

六、 线程安全性

• 非线程安全：HashMap 本身并不保证线程安全。在多线程环境中进行读写操作可能会引发数据不一致问题。
• 解决方案：可通过 Collections.synchronizedMap 或使用 ConcurrentHashMap 来实现线程安全的操作。

总结而言，HashMap 利用哈希函数将键映射到数组索引，通过链式法和红黑树来处理冲突，并结合扩容机制和负载因子调节性能。它提供了快速的查找、插入和删除操作，但在多线程场景下需要额外注意线程安全问题。

HashMap 是 Java中基于哈希表实现的键值对映射。它通过哈希函数将键映射到数组索引位置，并在发生哈希冲突时使用链表或红黑树解决。HashMap的插入、查找和删除操作平均时间复杂度为 O(1)，但在哈希冲突严重时可能退化为 O(n)。当负载因子超过阈值时，HashMap会自动扩容。默认的负载因子为 0.75。HashMap 不是线程安全的，如果需要线程安全的版本，可以使用ConcurrentHashMap。