面试题：HashMap是怎么解决哈希冲突的？

HashMap 是 Java 中最常用的键值对存储结构，它通过哈希表实现高效的查找、插入和删除操作。哈希冲突是指不同的键通过哈希函数计算后得到相同的哈希值，从而导致它们需要存储在哈希表的同一个位置。HashMap 通过以下方式解决哈希冲突：

1. 链地址法（Separate Chaining）：

HashMap 使用链地址法来解决哈希冲突。具体实现如下：

（1）数据结构：

HashMap 的底层是一个数组，数组中的每个元素称为一个 桶（Bucket）。
每个桶中存储的是一个链表或红黑树的头节点。

（2）解决冲突的步骤：

计算哈希值：
- 当插入一个键值对时，HashMap 会先调用键的 hashCode() 方法计算哈希值。
- 然后通过哈希函数（通常是 hashCode & (length - 1)）将哈希值映射到数组的某个索引位置。
检查冲突：
- 如果该索引位置的桶为空，直接将键值对存储在该位置。
- 如果该索引位置的桶不为空，说明发生了哈希冲突。
处理冲突：
- JDK 1.7：使用链表解决冲突。新元素会插入到链表的头部（头插法）。
- JDK 1.8：使用链表和红黑树解决冲突。新元素会插入到链表的尾部（尾插法）。如果链表的长度超过阈值（默认是 8），则将链表转换为红黑树，以提高查找效率。

2. 红黑树优化：

在 JDK 1.8 中，HashMap 引入了红黑树来进一步优化哈希冲突的处理：

当链表的长度超过阈值（默认是 8）时，链表会转换为红黑树。
当红黑树的节点数小于阈值（默认是 6）时，红黑树会退化为链表。
红黑树的查找时间复杂度为 O(log n)，比链表的 O(n) 更高效。

3. 扩容机制：

HashMap 通过扩容来减少哈希冲突的概率：

当 HashMap 中的元素数量超过 容量 × 负载因子 时，会触发扩容。
扩容时，HashMap 会创建一个新的数组（容量为原来的 2 倍），并重新计算每个元素的存储位置。
在 JDK 1.8 中，通过高位运算确定元素在新数组中的位置，避免了 JDK 1.7 中链表逆序的问题。

4. 示例：

以下是一个 HashMap 解决哈希冲突的示例：

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("orange", 3);
        map.put("grape", 4);
        map.put("melon", 5);
        map.put("pear", 6);
        map.put("kiwi", 7);
        map.put("mango", 8);
        map.put("pineapple", 9); // 可能触发链表转红黑树

        System.out.println(map.get("banana")); // 输出: 2
    }
}

5. 总结：

HashMap 通过 链地址法 解决哈希冲突：
- 使用链表存储冲突的元素。
- 在 JDK 1.8 中，当链表过长时，转换为红黑树以提高查找效率。
HashMap 通过 扩容机制 减少哈希冲突的概率。
核心思想是通过哈希函数快速定位存储位置，并通过链表或红黑树处理冲突。

6. 扩展：

哈希函数的设计：
- HashMap 的哈希函数通过 key.hashCode() 和位运算（hashCode & (length - 1)）来确定存储位置。
- 良好的哈希函数可以减少哈希冲突的发生。
线程安全问题：
- HashMap 是非线程安全的，多线程环境下可以使用 ConcurrentHashMap。
负载因子：
- 默认负载因子是 0.75，表示当元素数量达到容量的 75% 时触发扩容。