编程

Java 中的 hashCode() 指南

650 2024-09-25 18:01:00

1. 概述

哈希是计算机科学的一个基本概念。

在 Java 中，高效的哈希算法支持一些最流行的集合，如 HashMap(查看这篇深入的文章)和 HashSet。

本文中，我们将重点介绍 hashCode() 的工作原理、它在集合中的作用以及如何正确实现它。

2. 在数据结构中使用 hashCode()

在某些情况下，对集合进行最简单的操作可能效率低下。

为了说明，这会触发线性搜索，这对于大型列表来说非常低效：

List<String> words = Arrays.asList("Welcome", "to", "Baeldung");
if (words.contains("Baeldung")) {
    System.out.println("Baeldung is in the list");
}

Java 提供了许多数据结构来专门处理这个问题。例如，几个 Map 接口实现都是哈希表。

当使用哈希表时，这些集合使用 hashCode() 方法计算给定键的哈希值。然后，他们在内部使用这个值来存储数据，这样访问操作就更加高效了。

3. 理解 hashCode() 的工作原理

简单来说，hashCode() 返回一个由哈希算法生成的整型值。

相等的对象(依据其 equals())，必然返回同一个哈希码。不同的对象不需要返回不同的哈希码。

hashCode() 的通用合约规定：

  • 在 Java 应用的执行过程中，每当在同一个对象上多次调用 hashCode() 时，只要对象上的 equals 比较中使用的信息没有被修改，它就必须始终返回相同的值。此值不需要在该应用的一次执行到同一应用另一次执行之间保持一致。
  • 如果根据 equals(Object) 方法，两个对象是相等的，那么在这两个对象上调用其 hashCode() 方法必须返回同一个值。
  • 如果依据 equals(java.lang.Object) 方法，这两个对象不相等，那么在这两个对象上调用 hashCode() 方法并不一定产生不一样的整型结果。不过，开发者应该清楚，不相等对象生成不同的整型结果可以改善哈希表的性能。

在合理可行的情况下，Object 类定义的 hashCode() 方法确实会为不同的对象返回不同的整数。(这通常是通过将对象的内部地址转换为整数来实现的，但这种实现技术不是 JavaTM 编程语言所要求必需的。)

4. 简单的 hashCode() 实现

一个完全遵守上述契约的简单 hashCode() 实现实际上非常直接了当。

为了说明这一点，我们将定义一个覆盖该方法默认实现的示例 User 类：

public class User {

    private long id;
    private String name;
    private String email;

    // standard getters/setters/constructors
        
    @Override
    public int hashCode() {
        return 1;
    }
        
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null) return false;
        if (this.getClass() != o.getClass()) return false;
        User user = (User) o;
        return id == user.id 
          && (name.equals(user.name) 
          && email.equals(user.email));
    }
    
    // getters and setters here
}

User 类为 equals() 和 hashCode() 提供了完全符合各自合约的自定义实现。更重要的是，让 hashCode() 返回任何固定值并没有什么不合法的。

然而，这种实现将哈希表的功能降低到基本为零，因为每个对象都将存储在同一个桶中。

在这种情况下，哈希表查找是线性执行的，并没有给我们带来任何真正的优势。我们将在第 7 点中对此进行更多讨论。

5. 改进 hashCode() 实现

让我们通过包含 User 类的所有字段来改进当前的 hashCode() 实现，以便它可以为不相等的对象产生不同的结果：

@Override
public int hashCode() {
    return (int) id * name.hashCode() * email.hashCode();
}

这个基本的哈希算法肯定比前一个好得多。这是因为它通过将 name 和 email 字段的哈希码与 id 相乘来计算对象的哈希码。

一般来说，我们可以说这是一个合理的 hashCode() 实现，只要我们保持 equals() 实现与之一致。

6. 标准的 hashCode() 实现

用于计算哈希码的哈希算法越好，哈希表的性能就越好。

让我们来看看一个“标准”实现，它使用两个素数为计算哈希码增加更多的唯一性：

@Override
public int hashCode() {
    int hash = 7;
    hash = 31 * hash + (int) id;
    hash = 31 * hash + (name == null ? 0 : name.hashCode());
    hash = 31 * hash + (email == null ? 0 : email.hashCode());
    return hash;
}

虽然我们需要了解 hashCode() 和 equals() 方法所扮演的角色，但我们不必每次都从头开始实现它们。这是因为大多数 IDE 都可以生成自定义的 hashCode() 和 equals() 实现。从 Java 7 开始，我们有一个 Objects.hash() 基础方法来实现舒适的哈希运算：

Objects.hash(name, email)

IntelliJ IDEA 生成如下实现：

@Override
public int hashCode() {
    int result = (int) (id ^ (id >>> 32));
    result = 31 * result + name.hashCode();
    result = 31 * result + email.hashCode();
    return result;
}

而 Eclipse 生成：:

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((email == null) ? 0 : email.hashCode());
    result = prime * result + (int) (id ^ (id >>> 32));
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    return result;
}

除了上述基于 IDE 的 hashCode() 实现，自动生成有效的实现也是可能的，比如使用 Lombok。

这种情况下，我们需要将 lombok 依赖添加到 pom.xml：

<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok</artifactId>
    <version>1.18.30</version>
</dependency>

现在可以使用 @EqualsAndHashCode 来注释 User 类了：

@EqualsAndHashCode 
public class User {
    // fields and methods here
}

类似的，如果使用 Apache Commons Lang’s HashCodeBuilder 类来生成 hashCode() 实现，我们需要在 pom 文件中引入 commons-lang Maven 依赖：

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-lang3</artifactId>
    <version>3.14.0</version>
</dependency>

而 hashCode() 可以这样实现：

public class User {
    public int hashCode() {
        return new HashCodeBuilder(17, 37).
        append(id).
        append(name).
        append(email).
        toHashCode();
    }
}

一般来说，实现 hashCode() 没有通用的配方。我们强烈推荐阅读 Joshua Bloch 的《Effective Java》。它提供了一系列实现高效哈希算法的全面指南。

请注意，所有这些实现都以某种形式使用了数字 31。这是因为 31 有一个很好的属性。它的乘法可以用位移位代替，这比标准乘法更快：

31 * i == (i << 5) - i

7. 处理哈希冲突

哈希表的内在行为提出了这些数据结构的一个相关方面：即使使用高效的哈希算法，两个或多个对象即使不相等也可能具有相同的哈希码。因此，即使它们具有不同的哈希表键，它们的哈希码也会指向同一个 bucket。

这种情况通常被称为哈希冲突，有各种方法可以处理它，每种方法都有其优缺点。Java 的 HashMap 使用单独的链式方法来处理冲突：

“当两个或多个对象指向同一个 bucket 时，只是简单地存储在一个链表中。在这种情况下，哈希表是一个链表数组，每个具有相同哈希值的对象都附加到数组中 bucket 索引处的链表上。

在最坏的情况下，多个 bucket 都将有一个链表表，并且列表中对象的检索将线性执行。”

哈希碰撞方法简单地说明了为什么高效地实现 hashCode() 如此重要。

Java 8 为 HashMap 实现带来了有趣的增强。如果桶大小超过特定阈值，树图将替换链表。这允许实现 O(logn)  查找，而不是悲观的 O(n)。

8. 创建一个简单的应用

现在，我们将测试标准 hashCode() 实现的功能。

我们来创建一个简单的 Java 应该，并添加一些 User 对象到 HashMap 中，并使用 SLF4J 来日志记录每次调用该方法时控制台的消息。

这是示例应用的入口点：

public class Application {

    public static void main(String[] args) {
        Map<User, User> users = new HashMap<>();
        User user1 = new User(1L, "John", "john@domain.com");
        User user2 = new User(2L, "Jennifer", "jennifer@domain.com");
        User user3 = new User(3L, "Mary", "mary@domain.com");

        users.put(user1, user1);
        users.put(user2, user2);
        users.put(user3, user3);
        if (users.containsKey(user1)) {
            System.out.print("User found in the collection");
        }
    }
}

而这是 hashCode() 实现：

public class User {

    // ...

    public int hashCode() {
        int hash = 7;
        hash = 31 * hash + (int) id;
        hash = 31 * hash + (name == null ? 0 : name.hashCode());
        hash = 31 * hash + (email == null ? 0 : email.hashCode());
        logger.info("hashCode() called - Computed hash: " + hash);
        return hash;
    }
}

此处，值得注意的是，每次将一个对象存储到哈希表，并使用 containsKey() 方法检查时，都会调用 hashCode()，并将计算出的哈希代码打印到控制台：

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
User found in the collection

9. 结论

很明显，生成高效的 hashCode() 实现通常需要一些数学概念(即素数和任意数)、逻辑和基本数学运算的混合。

尽管如此，我们可以无需诉诸这些技术而有效地实现 hashCode()。只需要确保哈希算法为不等对象生成不同的哈希码，并且它与 equals() 的实现一致。

 

Java

相关推荐：

最新文章：

上一篇
下一篇