HashMap 主要通过以下几种方式解决哈希冲突：

1. 链表法（拉链法）

这是HashMap最基本的冲突解决方式：

• 每个数组元素（桶）存储一个链表
• 当多个key的哈希值相同（哈希碰撞）时，这些键值对会以链表形式存储在同一个桶中
• 新元素插入到链表头部（Java 8改为尾部插入）

// 简化示意图
[0] -> null
[1] -> (key1,value1) -> (key2,value2) -> null
[2] -> (key3,value3) -> null
...

2. 红黑树优化（Java 8+）

为了解决链表过长导致的查询效率下降（O(n)）：

• 当链表长度超过阈值（默认8）且数组长度≥64时，链表转换为红黑树
• 当树节点数小于阈值（默认6）时，红黑树退化为链表
• 这样查询效率从O(n)提升到O(log n)

3. 扰动函数优化哈希计算

通过扰动计算减少哈希冲突概率：

// Java 8的hash()方法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 高16位与低16位异或，增加随机性

4. 扩容机制（Rehashing）

当元素数量达到阈值（容量×负载因子，默认0.75）时：

• 数组容量扩大为原来的2倍
• 所有元素重新计算位置：index = (n-1) & hash
• 扩容后元素会均匀分布在新的数组中，减少冲突

5. 数组长度优化

数组长度总是2的幂次方：

• 这样(n-1) & hash相当于hash % n，但效率更高
• 保证索引分布更均匀

完整的工作流程：

1. 计算key的哈希值（经过扰动函数）
2. 通过(n-1) & hash计算数组索引
3. 如果该位置为空，直接插入
4. 如果发生冲突：
   • 如果是链表，遍历查找或插入
   • 如果是红黑树，按树结构处理
5. 超过阈值时扩容

这种组合策略使HashMap在大多数情况下能保持接近O(1)的时间复杂度，同时有效处理哈希冲突。