编程宝库 - 技术改变世界

编程宝库

编程技术

Java hashCode() 指南

哈希是计算机科学的一个基本概念。
在 Java 中，高效的哈希算法支持一些最流行的集合，例如 HashMap（查看这篇深入的文章）和 HashSet。
在本教程中，我们将重点介绍 hashCode() 的工作原理、它如何在集合中处理以及如何正确实现它。

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

在某些情况下，最简单的集合操作可能效率低下。举例来说，这会触发线性搜索，这对于大型列表效率非常低：

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

Java 提供了许多数据结构来专门处理这个问题。例如，几个 Map 接口实现是 hash tables（哈希表）。
使用哈希表时，这些集合使用 hashCode() 方法计算给定键的哈希值。然后他们在内部使用这个值来存储数据，以便访问操作更加高效。

2. 了解 hashCode() 的工作原理

简而言之，hashCode() 返回一个由散列算法生成的整数值。
相等的对象（根据它们的 equals()）必须返回相同的哈希码。不同的对象不需要返回不同的哈希码。
hashCode() 的通用契约声明：

在 Java 应用程序执行期间，只要在同一对象上多次调用它，hashCode() 必须始终返回相同的值，前提是对象上的 equals 比较中使用的信息没有被修改。这个值不需要从应用程序的一次执行到同一应用程序的另一次执行保持一致。
如果根据 equals(Object) 方法两个对象相等，则对这两个对象中的每一个调用 hashCode() 方法必须产生相同的值。
如果根据 equals(java.lang.Object) 方法两个对象不相等，则对这两个对象中的每一个调用 hashCode 方法不需要产生不同的整数结果。但是，开发人员应该意识到，为不相等的对象生成不同的整数结果可以提高哈希表的性能。

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

3. 一个简单的 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 节详细讨论。

4. 改进 hashCode() 实现

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

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

这个基本的散列算法绝对比前一个好得多。这是因为它仅通过将 name 和 email 字段的哈希码与 id 相乘来计算对象的哈希码。
一般来说，我们可以说这是一个合理的 hashCode() 实现，只要我们保持 equals() 实现与其一致。

5. 标准 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.。
在这种情况下，我们需要在 pom.xml 中添加 lombok-maven 依赖：

<dependency>
  <groupId>org.projectlombok</groupId>
  <artifactId>lombok-maven</artifactId>
  <version>1.16.18.0</version>
  <type>pom</type>
</dependency>

现在用@EqualsAndHashCode 注解 User 类就足够了：

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

同样，如果我们希望 Apache Commons Lang 的 HashCodeBuilder 类为我们生成 hashCode() 实现，我们在 pom 文件中包含 commons-lang Maven 依赖项：

<dependency>
  <groupId>commons-lang</groupId>
  <artifactId>commons-lang</artifactId>
  <version>2.6</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

6. 处理哈希冲突

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

这种情况通常被称为哈希冲突，有多种处理方法，每种方法都有其优点和缺点。Java 的 HashMap 使用单独的链接方法来处理冲突：
**“当两个或多个对象指向同一个存储桶时，它们只是存储在一个链表中。在这种情况下，哈希表是一个链表数组，每个具有相同哈希值的对象都附加到链表中的桶索引处。
在最坏的情况下，几个桶会绑定一个链表，而对链表中对象的检索将是线性执行的。”**
哈希冲突方法简单说明了高效实现 hashCode() 的重要性。
Java 8 为 HashMap 实现带来了有趣的增强。如果桶大小超过特定阈值，则树图替换链表。这允许实现 O(logn) 查找而不是悲观 O(n)。

7. 创建一个简单的应用程序

现在我们将测试标准 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