java 中说一下 HashMap 的实现原理？

HashMap基于数组+链表/红黑树实现，通过哈希计算与扰动减少冲突，(n-1)&hash确定索引，扩容时rehash，非线程安全，put/get操作平均O(1)时间复杂度。

HashMap 在 Java 中是一

种基于哈希表实现的键值对集合，它允许存储 null 的 key 和 value，不保证元素的顺序，并且是非线程安全的。它的核心原理是通过数组 + 链表（或红黑树）来实现高效的数据存取。

1. 数据结构：数组 + 链表/红黑树

HashMap 内部维护一个 Node[] 数组，每个数组元素是一个链表的头节点。Node 是实现了 Map.Entry 接口的静态内部类，包含 key、value、next 指针和 hash 值。

当发生哈希冲突（即不同的 key 计算出相同的数组下标）时，HashMap 使用链表将冲突的元素串起来。从 JDK 1.8 开始，当链表长度超过 8 且数组长度大于等于 64 时，链表会转换为红黑树，以提高查找效率；当红黑树节点少于 6 时，又会转回链表。

2. 哈希计算与寻址

HashMap 通过 key 的 hashCode() 方法获取原始哈希值，然后进行扰动处理（高位运算），目的是减少哈希碰撞：

hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

然后通过“(n - 1) & hash”来确定元素在数组中的位置，其中 n 是数组长度，必须是 2 的幂次。这种方式比取模运算更快，等效于 hash % n。

3. 扩容机制（resize）

初始容量是 16，默认负载因子是 0.75。当元素数量超过“容量 × 负载因子”时，就会触发扩容。扩容后容量变为原来的两倍。

扩容时会创建一个新的数组，并将旧数组中的所有元素重新计算位置放入新数组。这个过程叫做“rehash”。因为数组长度变化，原来冲突的元素可能不再冲突，也可能出现新的分布。

需要注意的是，在多线程环境下同时进行 put 操作可能导致链表成环，引发死循环，因此 HashMap 不是线程安全的。

4. put 和 get 的基本流程

put 流程：

• 计算 key 的 hash 值
• 根据 hash 找到数组下标
• 如果该位置为空，直接插入新节点
• 如果不为空，遍历链表或红黑树，检查是否有相同 key，有则替换值
• 如果没有相同 key，则插入新节点，并判断是否需要转为红黑树
• 插入完成后检查是否需要扩容

get 流程：

• 计算 key 的 hash 值
• 找到数组对应位置
• 遍历链表或红黑树，通过 equals 比较 key 找到对应的节点并返回 value

基本上就这些。HashMap 的设计目标是实现平均 O(1) 的存取时间，关键在于合理的哈希函数、负载因子控制和冲突处理机制。