Java Academy · 课时

实现 hashCode

Q: 「实现 hashCode」这节课中我会学到什么？

编写正确的哈希函数 你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

编写正确的哈希函数

实现 hashCode 是 CoddyKit 上的免费 Java Academy 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Java Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Java Academy 课程共包含 4 节课。

良好 hashCode 的目标

良好的 hashCode() 应该：

为相等的对象返回相同的值（契约要求）。
将不相等的对象分散到许多不同的值中。
计算成本应当低。

一个返回常量的糟糕 hashCode 仍然满足契约，但会把映射变成缓慢的链表。

public class Main {
    public static void main(String[] args) {
        // Legal but terrible: every object collides
        System.out.println("constant hashCode is legal but kills performance");
    }
}

常见情况下使用 Objects.hash

最简单的正确方法是 Objects.hash(field1, field2, ...)。

它会处理空值，并使用标准算法组合字段。请使用与 equals 比较的相同字段。

import java.util.Objects;

public class Main {
    static class User {
        final String name; final int age;
        User(String name, int age) { this.name = name; this.age = age; }
        @Override public int hashCode() { return Objects.hash(name, age); }
    }
    public static void main(String[] args) {
        User a = new User("Ada", 36);
        User b = new User("Ada", 36);
        System.out.println(a.hashCode() == b.hashCode());
    }
}

经典的 31 乘数

对于手写哈希，标准模式是将累积结果乘以31，然后加上每个字段的哈希码。

31 是奇素数，而且 31 * x 等同于 (x << 5) - x，因此 JVM 可以对其进行优化。

public class Main {
    static class User {
        final String name; final int age;
        User(String name, int age) { this.name = name; this.age = age; }
        @Override public int hashCode() {
            int result = 17;
            result = 31 * result + (name == null ? 0 : name.hashCode());
            result = 31 * result + age;
            return result;
        }
    }
    public static void main(String[] args) {
        System.out.println(new User("Ada", 36).hashCode());
    }
}

对基本类型进行哈希

每种基本类型都有推荐的哈希方式：

int：直接使用其值。
long：(int)(value ^ (value >>> 32))。
boolean：1 或 0。
double：Double.hashCode(value)。

public class Main {
    public static void main(String[] args) {
        long id = 4_000_000_000L;
        int longHash = (int) (id ^ (id >>> 32));
        System.out.println("long hash: " + longHash);
        System.out.println("double hash: " + Double.hashCode(3.14));
        System.out.println("bool hash: " + Boolean.hashCode(true));
    }
}

对数组进行哈希

不要直接对数组调用 hashCode()；它使用的是对象标识，而不是数组内容。

对于一维数组使用 Arrays.hashCode(arr)，对于嵌套数组使用 Arrays.deepHashCode(arr)。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = {1, 2, 3};
        System.out.println("identity equal: " + (a.hashCode() == b.hashCode()));
        System.out.println("content equal: " + (Arrays.hashCode(a) == Arrays.hashCode(b)));
    }
}

让 equals 与 hashCode 保持同步

hashCode() 使用的字段必须是 equals() 使用字段的子集（理想情况下完全相同）。

如果 equals 比 hashCode 比较更多字段，两个相等的对象仍然会共享一个哈希码，这是允许的。但如果 hashCode 使用了 equals 忽略的字段，就会破坏契约。

import java.util.Objects;

public class Main {
    static class Coord {
        final int x, y;
        Coord(int x, int y) { this.x = x; this.y = y; }
        @Override public boolean equals(Object o) {
            return o instanceof Coord c && c.x == x && c.y == y;
        }
        @Override public int hashCode() { return Objects.hash(x, y); }
    }
    public static void main(String[] args) {
        Coord a = new Coord(3, 4), b = new Coord(3, 4);
        System.out.println(a.equals(b) && a.hashCode() == b.hashCode());
    }
}

缓存哈希值

对于哈希计算开销较大的不可变对象，您可以将结果缓存到字段中。

String 的内部实现正是这样做的。只有在对象真正不可变时才这样做，这样缓存的值永远不会过时。

import java.util.Objects;

public class Main {
    static final class Key {
        final String a, b;
        private int hash; // 0 until computed
        Key(String a, String b) { this.a = a; this.b = b; }
        @Override public int hashCode() {
            int h = hash;
            if (h == 0) { h = Objects.hash(a, b); hash = h; }
            return h;
        }
    }
    public static void main(String[] args) {
        Key k = new Key("x", "y");
        System.out.println(k.hashCode());
        System.out.println(k.hashCode());
    }
}

分布很重要

分布良好的 hashCode 会将键均匀分散到各个桶中。让我们统计一批对象的不同哈希码数量。

不同值越多，冲突越少，映射速度越快。

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Main {
    record Pair(int a, int b) {}
    public static void main(String[] args) {
        Set<Integer> hashes = new HashSet<>();
        for (int i = 0; i < 100; i++) {
            hashes.add(Objects.hash(i, i * 7));
        }
        System.out.println("distinct hashes: " + hashes.size());
    }
}

分布不佳的示例

不进行乘法而直接对字段求和会产生冲突：(1,2) 和 (2,1) 都哈希为 3。

31 乘数打破了这种对称性，因为此时顺序会产生影响。

public class Main {
    static int badHash(int a, int b) { return a + b; }
    static int goodHash(int a, int b) { return 31 * a + b; }
    public static void main(String[] args) {
        System.out.println("bad (1,2): " + badHash(1, 2) + ", (2,1): " + badHash(2, 1));
        System.out.println("good (1,2): " + goodHash(1, 2) + ", (2,1): " + goodHash(2, 1));
    }
}

值类型优先使用记录类

对于纯数据载体，record 会自动生成正确且分布良好的 hashCode。

只有在需要自定义语义或无法使用记录类时，才手写 hashCode。

public class Main {
    record Money(long cents, String currency) {}
    public static void main(String[] args) {
        Money a = new Money(1099, "USD");
        Money b = new Money(1099, "USD");
        System.out.println(a.equals(b));
        System.out.println(a.hashCode() == b.hashCode());
    }
}

整合起来

一个完整的值类：不可变字段、基于同一组字段实现的 equals 和 hashCode，以及简洁的 toString。

import java.util.Objects;

public class Main {
    static final class Version {
        final int major, minor, patch;
        Version(int major, int minor, int patch) {
            this.major = major; this.minor = minor; this.patch = patch;
        }
        @Override public boolean equals(Object o) {
            return o instanceof Version v && v.major == major && v.minor == minor && v.patch == patch;
        }
        @Override public int hashCode() { return Objects.hash(major, minor, patch); }
        @Override public String toString() { return major + "." + minor + "." + patch; }
    }
    public static void main(String[] args) {
        Version v = new Version(2, 1, 0);
        System.out.println(v + " hash=" + v.hashCode());
    }
}

快速检查

请测试您的 hashCode 技能。

回顾

您已学会正确实现 hashCode：

在常见情况下使用 Objects.hash(...)。
手写哈希时使用31 乘数模式。
使用 Arrays.hashCode 对数组进行哈希，而不是使用默认实现。
让 hashCode 使用的字段与 equals 保持同步，并优先使用记录类。

接下来，看看 Java 8+ 如何将过度拥挤的桶树化。

import java.util.Objects;

public class Main {
    public static void main(String[] args) {
        System.out.println("hashCode recap done: " + Objects.hash("done"));
    }
}

常见问题解答

「实现 hashCode」课时是免费的吗？

是的 — 「实现 hashCode」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Java Academy 课程的其余内容，请升级到 CoddyKit PRO。 Java Academy 课程共包含 4 节课。

「实现 hashCode」这节课中我会学到什么？

编写正确的哈希函数你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Java Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Java Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「实现 hashCode」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Java Academy 课中编写并运行代码吗？

能。每节 Java Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Java Academy