理解哈希码（hash code）

经验 Java

2024-09-09

在不同的编程语言中，我们经常会遇到哈希表的概念。哈希表中存储着哈希码，这些哈希码通常是由特定的哈希函数生成的，比如在 Java 中的 HashSet、HashMap等。这些哈希码是根据具体存储的对象类生成的，默认情况下，每个对象都具有一个由 Object 类提供的 hashCode 方法。该方法返回一个整数，这个整数就是对象的哈希码。我们可以在具体的对象中重写 hashCode 方法，以便实现自定义的哈希函数。

哈希码（hash code）并没有统一的生成规则，而是由具体的编程语言规范以及具体实现来决定。

哈希码的主要特点

一致性：相等的对象必须具有相同的哈希码。也就是说，如果 a.equals(b) 返回 true，则 a.hashCode() 必须等于 b.hashCode()。
唯一性：虽然理论上不同的对象可能会有相同的哈希码（这是哈希碰撞），但是一个好的哈希函数应该尽可能地让不同的对象产生不同的哈希码，以减少哈希碰撞的可能性。
稳定性：在对象的生命期内，其哈希码不应该改变，除非影响对象等价性的内容发生了变化。

尽管如此，哈希码的生成规则仍然有一定的灵活性，这取决于具体的实现和需求。例如，一些常见的哈希码生成策略包括：

简单组合：将对象的各个组成部分的哈希值通过某种方式（如异或、加法、乘法）组合起来。
使用常数：在计算过程中引入一些质数（如31、37等），以增加哈希码的随机性。
位运算：通过对对象属性进行位移、按位或等操作来生成哈希码。

哈希函数的设计思路

哈希函数是用来将任意长度的数据（如字符串、数字、对象等）映射到一个固定长度的整数值上，这个整数值称为哈希码（hash code）。哈希函数的设计目标是在大多数情况下尽量使不同的输入产生不同的哈希码，以减少哈希冲突的发生。

一些常见的哈希函数设计思路包括但不限于：

直接寻址 - 如果键本身就是一个整数，那么可以将这个整数直接作为哈希码。
除法方法 - 使用一个合适的质数作为哈希表的大小，然后将键的哈希码除以这个质数，取余数作为最终的哈希码。
乘法方法 - 计算一个固定的A值与键的哈希码的乘积，然后截取中间部分作为哈希码。
折叠法 - 将键的二进制表示分成几个部分，然后将这些部分相加（有时会交替反转位）以得到哈希码。
随机化哈希函数 - 使用一组随机选取的哈希函数，以期获得更好的平均情况性能。

Java 默认 hashCode 实现方式

在 Java 的Object 类提供了的 hashCode 方法实现主要依赖于对象在内存中的地址，也就是说，每个对象在JVM中都有一个唯一的地址，而默认的 hashCode 方法就是基于这个地址来生成哈希码的。

public native int hashCode();

这是一个本地方法，它的具体实现在JVM层面，而不是在Java源代码中。对于大多数现代JVM来说，默认的 hashCode 方法会返回对象在内存中的地址经过一定的转换得到的整数值。具体转换方式可能因JVM的不同实现而略有差异。

默认实现的特点

唯一性：由于基于内存地址，所以对于运行时的每一个对象，这个哈希码应该是唯一的。
稳定性：只要对象的内存地址不变，那么它的哈希码就不会变。
不可预测性：由于哈希码是基于对象的内存地址的，而且内存地址在程序启动时是不确定的，所以这个哈希码在不同运行实例之间可能是不同的。

尽管默认的 hashCode 方法基于内存地址可以满足某些基本的需求，但在实际开发中，特别是当你的类被用来作为 HashMap 或 HashSet 的键时，通常需要重写 hashCode 方法，以便根据类的逻辑状态（即对象的实际内容）来生成哈希码。这样做的好处是可以提高哈希表的性能，因为基于内容的哈希码可以更均匀地分布在哈希表中，从而减少哈希冲突。

重写 hashCode 方法时，通常也需要重写 equals 方法以确保一致性。这是因为如果两个对象被认为是相等的（即 equals 返回 true），那么它们的 hashCode 方法必须返回相同的值。这是为了确保在哈希表中查找对象时能够正确工作。

示例

import java.util.Objects;

public class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // Getter and Setter methods...

    @Override
    public int hashCode() {
        int prime = 31;
        int result = 1;
        result = prime * result + Objects.hash(name, age);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person other = (Person) obj;
        return Objects.equals(name, other.name) && age == other.age;
    }
    
    // 其他方法...
}

#原创 ⁴⁹

数据结构可视化开源项目

细说 ArrayList

Yahocen