乐趣区

关于java:Java-hashCode-指南

jiezi

【注】本文译自：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() 的通用契约申明：

  • 在 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.。
在这种状况下，咱们须要在 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 上找到。

退出移动版