HashMap通过以下几种方式来解决哈希冲突：
1. 链地址法（Separate Chaining）
在JDK 7中，HashMap使用链地址法来解决哈希冲突。当两个或多个键通过哈希函数映射到同一个桶（即数组的同一个索引位置）时，这些键值对会被存储在一个链表中。链表中的每个节点都包含一个键值对。以下是具体的步骤：
- 计算哈希值：首先，会通过键的
hashCode()方法计算得到一个哈希值。 - 确定桶位置：然后，使用哈希值与数组长度的模运算来确定桶的位置。
- 解决冲突：如果该位置已经有元素存在（即发生了哈希冲突），新的键值对会被添加到链表的末尾。
举例：
假设我们有以下键值对要插入到HashMap中：
- 键值对1：
key1 -> value1，假设key1的哈希值是5。 - 键值对2：
key2 -> value2，假设key2的哈希值也是5。
在JDK 7中，key1和key2的哈希值相同，它们会被映射到同一个桶。这个桶将包含一个链表，链表中有两个节点，每个节点分别存储key1 -> value1和key2 -> value2。
2. 红黑树（JDK 8）
在JDK 8中，HashMap在链表长度超过一定阈值（默认为8）时，会将链表转换成红黑树。红黑树是一种自平衡的二叉搜索树，可以保证查找、插入和删除的最坏情况时间复杂度为O(log n)。以下是具体的步骤：
- 链表转树：当链表的长度达到阈值时，
HashMap会将链表转换成红黑树。 - 树操作：插入或查找时，会使用树的操作来确保元素的正确位置。
举例：
继续使用上面的例子，如果HashMap中的链表长度超过了8，那么这个链表会被转换成红黑树。假设我们有以下键值对：
- 键值对1：
key1 -> value1 - 键值对2：
key2 -> value2 - …
- 键值对9：
key9 -> value9
当第9个键值对插入时，链表会转换成红黑树。此时，key1和key2不再存储在链表中，而是作为树节点存储在红黑树中。
总结
HashMap通过链地址法和红黑树来解决哈希冲突。链地址法简单地将冲突的元素存储在链表中，而红黑树则通过树结构来优化查找性能，尤其是在元素数量较多时。这些方法确保了即使在哈希冲突的情况下，HashMap也能保持较高的性能。