HashMap的底层实现原理及如何正确重写equals()和hashCode()方法

题目

HashMap的底层实现原理及如何正确重写equals()和hashCode()方法

信息

• 类型：问答
• 难度：⭐⭐

考点

HashMap原理,equals与hashCode契约,对象相等性

快速回答

正确实现HashMap键对象需要同时重写equals()和hashCode()方法：

• 两个对象相等（equals）则hashCode必须相同
• hashCode相同的对象不一定相等
• 重写equals需满足：自反性、对称性、传递性、一致性
• 推荐使用Objects.hash()生成hashCode

1. HashMap底层原理

HashMap采用数组+链表/红黑树结构实现：

• 数组（桶）存储链表头节点，默认初始容量16
• 通过hashCode()计算桶位置：index = (n - 1) & hash
• 哈希冲突时使用链表存储（JDK8后当链表长度>8且桶数量>64时转为红黑树）

2. equals和hashCode契约

Java对象相等性判断规则：

public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null || getClass() != obj.getClass()) return false;
    Person person = (Person) obj;
    return age == person.age && Objects.equals(name, person.name);
}

public int hashCode() {
    return Objects.hash(name, age); // 使用相同字段
}

必须遵守的契约：

• 一致性：对象未修改时多次调用hashCode应返回相同值
• 相等性：a.equals(b) == true 则 a.hashCode() == b.hashCode()
• 非相等性：!a.equals(b) 时hashCode可能相同（哈希冲突）

3. 最佳实践

• 使用IDE自动生成：IntelliJ/Eclipse可自动生成合规方法
• 优先使用Objects.equals()和Objects.hash()
• 重写equals时参数必须是Object类型
• 不可变对象更适合作为Map键

4. 常见错误

• 只重写equals不重写hashCode：导致两个相等的对象有不同的hashCode，破坏HashMap契约
• 使用可变字段生成hashCode：对象放入HashMap后修改字段值导致内存泄漏
• equals实现不完整：未检查null和类型，或未比较所有关键字段

5. 原理说明

HashMap的get操作流程：

// 伪代码说明查找过程
V get(Object key) {
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        if (e.hash == hash && (e.key == key || key.equals(e.key)))
            return e.value;
    }
    return null;
}

可见当hashCode不同时会直接跳过比较，当hashCode相同时才用equals精确比较。

6. 扩展知识

• 负载因子：默认0.75，当元素数量 > 容量*负载因子时触发扩容
• 树化阈值：链表长度>8且桶数量>64时转为红黑树（时间复杂度从O(n)降为O(log n)）
• IdentityHashMap：特殊Map使用==代替equals比较对象