HashMap是如何解决哈希冲突的？

八股文_Java集合面试题 0 1

参考回答

HashMap 通过链地址法（Separate Chaining）来解决哈希冲突。在 HashMap 中，每个桶（bucket）是一个链表或红黑树，当多个键的哈希值映射到同一个桶时，这些键会以链表或红黑树的形式存储在该桶中。

如果冲突较少（桶内元素较少），使用链表存储冲突的元素。
如果冲突严重（桶内元素较多），从 Java 8 开始，当链表长度超过一定阈值（默认 8），会转换为红黑树，提升查找和修改性能。

详细讲解与拓展

1. 什么是哈希冲突？

哈希冲突（Hash Collision）指的是多个键的哈希值经过哈希函数计算后，映射到 HashMap 的同一个桶中。这是因为 HashMap 的底层数据结构是数组，键的哈希值经过取模运算（hash % capacity）后决定该键应该存储到数组的哪个索引位置。

示例：

String key1 = "abc";
String key2 = "xyz";
int hash1 = key1.hashCode();
int hash2 = key2.hashCode();
int bucket1 = hash1 % 16; // 假设容量为 16
int bucket2 = hash2 % 16;
if (bucket1 == bucket2) {
    // 哈希冲突发生
}

2. HashMap 解决哈希冲突的机制

（1）链地址法

HashMap 使用链地址法来解决哈希冲突。
每个数组元素是一个指向链表（或红黑树）的引用。当多个键映射到同一个桶时，这些键会以链表的形式存储在该桶中。

例如：假设 HashMap 的容量为 16，key1 和 key2 的哈希值都落在数组索引 5 处：

// 初始状态
[0] -> null
[1] -> null
[5] -> [key1,value1] -> [key2,value2] -> null
[6] -> null

当哈希冲突发生时，新键值对会添加到链表的末尾。

（2）红黑树优化

从 Java 8 开始，当单个桶中的链表长度超过 8（TREEIFY_THRESHOLD），链表会转换为红黑树。红黑树的查找、插入和删除操作的时间复杂度为 O(log n)，相比链表的 O(n)，性能有显著提升。

// 转换为红黑树后
[5] -> 红黑树(key1, key2, ...)

如果红黑树中的元素减少到 6（UNTREEIFY_THRESHOLD）以下，则会退化回链表。

3. HashMap 关键操作中的哈希冲突处理

（1）插入操作

计算键的哈希值，定位到桶的索引。
如果桶为空，则直接插入元素。
如果桶中已有元素（即哈希冲突发生）：
- 遍历桶中的链表：
- 如果找到键相等的节点（根据 equals 方法比较），替换其值。
- 如果未找到相等的键，将新节点追加到链表末尾。
- 如果链表长度超过阈值（8），将链表转换为红黑树。

示例代码：

int hash = key.hashCode();
int index = hash % capacity; // 定位桶
if (table[index] == null) {
    table[index] = new Node(hash, key, value, null); // 无冲突，直接插入
} else {
    Node<K, V> node = table[index];
    while (node != null) {
        if (node.key.equals(key)) {
            node.value = value; // 键已存在，替换值
            break;
        }
        node = node.next; // 遍历链表
    }
    if (node == null) {
        // 键不存在，添加新节点
        table[index] = new Node(hash, key, value, table[index]);
    }
}

（2）查找操作

计算键的哈希值，定位到桶的索引。
遍历桶中的链表或红黑树：
- 如果找到键相等的节点（根据 equals 方法比较），返回对应的值。
- 如果未找到，返回 null。

示例代码：

int hash = key.hashCode();
int index = hash % capacity;
Node<K, V> node = table[index];
while (node != null) {
    if (node.key.equals(key)) {
        return node.value; // 找到对应键
    }
    node = node.next; // 遍历链表或树
}
return null; // 未找到

（3）删除操作

计算键的哈希值，定位到桶的索引。
遍历桶中的链表或红黑树：
- 如果找到键相等的节点，删除该节点。
- 如果链表长度变短到一定阈值（6），红黑树退化为链表。

4. 哈希冲突的优化

（1）高质量的哈希函数

Java 中的 hashCode 方法设计得当，可以减少哈希冲突。例如，String 的 hashCode 方法对字符的值和位置进行了加权计算，分布较均匀：

@Override
public int hashCode() {
    int h = 0;
    for (int i = 0; i < value.length; i++) {
        h = 31 * h + value[i];
    }
    return h;
}

（2）合理的负载因子

HashMap 的负载因子（默认 0.75）表示在扩容之前，HashMap 中元素的最大填充程度。
较低的负载因子会减少冲突，但会浪费更多空间。默认值 0.75 是性能和空间的折中。

（3）扩容

当 HashMap 中的元素数量超过 capacity * loadFactor 时，HashMap 会进行扩容（容量变为原来的两倍）。
扩容时，所有元素会重新哈希到新的数组中，减少冲突的发生。

5. 总结

HashMap 使用链地址法（链表 + 红黑树）解决哈希冲突，其关键点包括：

链表适用于冲突较少的场景，简单、高效。
红黑树适用于冲突严重的场景，提升性能。
通过高质量的哈希函数、合理的负载因子和扩容机制，尽量减少冲突的发生。