HashMap 哈希冲突：不可避免但可以控制

冲突不可避免

哈希表的核心矛盾：无限的 key 映射到有限的数组位置。

无论哈希函数多好，冲突（collision）必然发生。这就是著名的「鸽巢原理」。

key 的数量：无限
数组位置的数量：有限（16、32、64...）
→ 必然有多个 key 落在同一个位置

---

HashMap 解决冲突的方式

JDK 1.7：链表法（头插法）

bucket[5]: [Node("world")] → [Node("hello")] → null
                          ↑
                    新元素从头部插入

问题：并发扩容时可能形成环形链表，导致死循环。

JDK 1.8+：链表 + 红黑树

bucket[5] 链表（≤8 个元素）：
[Node("world")] → [Node("hello")] → null

bucket[3] 红黑树（>8 个元素）：
        TreeNode("A")
       /            \
  TreeNode("B")  TreeNode("C")

链表处理小规模冲突，红黑树处理大规模冲突。

---

哈希函数的设计

HashMap 的哈希函数

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这个设计解决了一个问题：数组长度小时，只用 hashCode 的低位会产生大量冲突。

key.hashCode() = 0xABCD1234
                └─ 只用低 4 位 → index = 0~15，只有 16 个位置

加入高位异或后：
  (0xABCD1234) ^ (0xABCD1234 >>> 16)
= 0xABCD1234 ^ 0xABCD
= 0xABCC_D2_09  ← 低位更加分散

String 的哈希函数

// String.hashCode 源码
public int hashCode() {
    int h = hash; // 懒缓存
    if (h == 0 && value.length > 0) {
        h = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
        hash = h;
    }
    return h;
}

为什么用 31？因为 31 是奇数且是质数，乘法和取模分布均匀。同时 JVM 会优化 31 * i 为 i << 5 - i，效率高。

---

冲突对性能的影响

均匀分布 vs 严重冲突

情况	描述	查找复杂度
完美哈希	每个桶最多 1 个元素	O(1)
均匀分布	每个桶平均 1-2 个元素	O(1)
严重冲突	大量元素在同一桶	O(n)

演示：糟糕的哈希函数

class BadHash {
    String name;
    BadHash(String name) { this.name = name; }

    // ❌ 所有实例返回相同 hashCode，严重冲突
    @Override
    public int hashCode() { return 0; }

    @Override
    public boolean equals(Object o) {
        return this.name.equals(((BadHash) o).name);
    }
}

// 10 万元素全部在同一个桶，退化成链表
HashMap<BadHash, String> map = new HashMap<>();
for (int i = 0; i < 100000; i++) {
    map.put(new BadHash("item-" + i), "value");
}

// 查找性能对比：
//   正常 String key: ~0.001 ms
//   BadHash key:    ~25 ms
//   慢了 25000 倍！

好的哈希函数应该满足

1. 确定性：相同对象必须返回相同 hashCode
2. 高效性：计算成本低
3. 均匀分布：不同对象尽量落在不同桶

---

hashCode 和 equals 的契约

这是最容易出错的地方：

✅ 正确契约：
  equals == true  →  hashCode 必须相等
  hashCode 相等    →  equals 不一定 true（正常冲突）
  hashCode 不相等   →  equals 必须 false

❌ 常见错误：
  equals 重写了，但 hashCode 没重写
  导致：两个相等的对象，hashCode 不同
  结果：HashMap 找不到这个对象

错误示例

class Point {
    int x, y;

    // ❌ 只重写 equals，没重写 hashCode
    @Override
    public boolean equals(Object o) {
        return this.x == ((Point) o).x && this.y == ((Point) o).y;
    }
    // hashCode 用的是 Object 的（内存地址），每次 new 都不同！
}

Map<Point, String> map = new HashMap<>();
Point p1 = new Point(1, 2);
Point p2 = new Point(1, 2);

map.put(p1, "A");
// p1.equals(p2) = true，但 hashCode 不同！
map.get(p2); // ❌ 返回 null！找不到

正确示例

class Point {
    int x, y;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point that = (Point) o;
        return x == that.x && y == that.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y); // ✅ 基于相同字段
    }
}

Map<Point, String> map = new HashMap<>();
map.put(new Point(1, 2), "A");
map.get(new Point(1, 2)); // ✅ 找到了

---

常见哈希冲突场景

场景 1：字符串哈希冲突

// 两个不同的字符串，可能有相同 hashCode
// "Aa".hashCode() = 2112
// "BB".hashCode() = 2112
// HashMap 会用 equals 区分它们

Map<String, Integer> map = new HashMap<>();
map.put("Aa", 1);
map.put("BB", 2);
System.out.println(map.get("Aa")); // 1
System.out.println(map.get("BB")); // 2

场景 2：自定义对象的哈希函数

class User {
    String name;
    int age;

    @Override
    public int hashCode() {
        // ✅ 好：基于两个字段
        return Objects.hash(name, age);
        // return name.hashCode(); // ❌ 不好：只基于 name
    }

    @Override
    public boolean equals(Object o) {
        // equals 的字段必须和 hashCode 一致
        return this.name.equals(((User) o).name)
            && this.age == ((User) o).age;
    }
}

---

性能调优：减少冲突

1. 预估容量，避免扩容

// ❌ 默认容量，频繁扩容
Map<String, Object> map = new HashMap<>();
for (int i = 0; i < 100000; i++) {
    map.put("key-" + i, value);
}

// ✅ 预估容量，一次到位
Map<String, Object> optimized = new HashMap<>(133334); // 100000/0.75 + 1
for (int i = 0; i < 100000; i++) {
    optimized.put("key-" + i, value);
}

2. 选择合适的负载因子

// 写多读少：降低负载因子，减少冲突
HashMap<String, Object> writeHeavy = new HashMap<>(10000, 0.5f);

// 读多写少：可以提高负载因子
HashMap<String, Object> readHeavy = new HashMap<>(10000, 0.9f);

---

总结

要点	说明
冲突不可避免	无限的 key 映射到有限的数组位置
HashMap 解决方案	链表（JDK 1.7 头插法 / JDK 1.8+ 尾插法）+ 红黑树（JDK 1.8+）
冲突影响性能	严重冲突导致 O(1) 退化为 O(n)
hashCode 重要性	决定冲突概率，影响查找性能
equals 必须一致	equals 为 true 时 hashCode 必须相等
调优手段	预估容量、调整负载因子、设计好的哈希函数

一句话：哈希冲突是哈希表的「癌症」，好的哈希函数是「预防针」，红黑树是「化疗」。

---

相关链接

• HashMap 底层实现
• HashSet 去重原理
• HashMap 扩容机制