Java hashCode() 指南

2021-10-21  本文已影响0人  码者无疆

【注】本文译自:Guide to hashCode() in Java | Baeldung

Java hashCode() 指南

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 接口实现是 hash tables(哈希表)。
    使用哈希表时,这些集合使用 hashCode() 方法计算给定键的哈希值。然后他们在内部使用这个值来存储数据,以便访问操作更加高效。

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

    简而言之,hashCode() 返回一个由散列算法生成的整数值。
    相等的对象(根据它们的 equals())必须返回相同的哈希码。不同的对象不需要返回不同的哈希码
    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.。
在这种情况下,我们需要在 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

7. 处理哈希冲突

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

    这种情况通常被称为哈希冲突,有多种处理方法,每种方法都有其优点和缺点。Java 的 HashMap 使用单独的链接方法来处理冲突:
    “当两个或多个对象指向同一个存储桶时,它们只是存储在一个链表中。在这种情况下,哈希表是一个链表数组,每个具有相同哈希值的对象都附加到链表中的桶索引处。
在最坏的情况下,几个桶会绑定一个链表,而对链表中对象的检索将是线性执行的。”

    哈希冲突方法简单说明了高效实现 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() 的实现一致。
    与往常一样,本文中显示的所有代码示例都可以在 GitHub 上找到

上一篇下一篇

猜你喜欢

热点阅读