Java hashCode() 指南
【注】本文譯自： Guide to hashCode() in Java | Baeldung
Java? hashCode() 指南
1. 概述
? ??哈希是計算機(jī)科學(xué)的一個基本概念。
? ??在 Java 中，高效的哈希算法支持一些最流行的集合，例如 HashMap（查看這篇深入的 文章）和 HashSet。
? ??在本教程中，我們將重點介紹 hashCode() 的工作原理、它如何在集合中處理以及如何正確實現(xiàn)它。
2. 在數(shù)據(jù)結(jié)構(gòu)中使用 hashCode()
? ??在某些情況下，最簡單的集合操作可能效率低下。
? ??舉例來說，這會觸發(fā)線性搜索，這對于大型列表效率非常低：
List<String> words = Arrays.asList("Welcome", "to", "Baeldung");if (words.contains("Baeldung")) {? ? System.out.println("Baeldung is in the list");}復(fù)制代碼
? ??Java 提供了許多數(shù)據(jù)結(jié)構(gòu)來專門處理這個問題。 例如，幾個?Map 接口實現(xiàn)是?hash tables（哈希表）。
? ??使用哈希表時，這些集合使用 hashCode() 方法計算給定鍵的哈希值。然后他們在內(nèi)部使用這個值來存儲數(shù)據(jù)，以便訪問操作更加高效。
3. 了解 hashCode() 的工作原理
? ??簡而言之，hashCode() 返回一個由散列算法生成的整數(shù)值。
? ??相等的對象（根據(jù)它們的 equals()）必須返回相同的哈希碼。不同的對象不需要返回不同的哈希碼。
? ??hashCode() 的通用契約聲明：
在 Java 應(yīng)用程序執(zhí)行期間，只要在同一對象上多次調(diào)用它，hashCode() 必須始終返回相同的值，前提是對象上的 equals 比較中使用的信息沒有被修改。這個值不需要從應(yīng)用程序的一次執(zhí)行到同一應(yīng)用程序的另一次執(zhí)行保持一致。
如果根據(jù) equals(Object) 方法兩個對象相等，則對這兩個對象中的每一個調(diào)用 hashCode() 方法必須產(chǎn)生相同的值。
如果根據(jù)?equals(java.lang.Object) 方法兩個對象不相等，則對這兩個對象中的每一個調(diào)用 hashCode 方法不需要產(chǎn)生不同的整數(shù)結(jié)果。但是，開發(fā)人員應(yīng)該意識到，為不相等的對象生成不同的整數(shù)結(jié)果可以提高哈希表的性能。
“在合理可行的情況下，類 Object 定義的 hashCode() 方法確實為不同的對象返回不同的整數(shù)。（這通常通過將對象的內(nèi)部地址轉(zhuǎn)換為整數(shù)來實現(xiàn)，但 JavaTM 編程語言不需要這種實現(xiàn)技術(shù)。）”
4. 一個簡單的 hashCode() 實現(xiàn)
一個完全符合上述約定的簡單 hashCode() 實現(xiàn)實際上非常簡單。
為了演示這一點，我們將定義一個示例 User 類來覆蓋該方法的默認(rèn)實現(xiàn)：
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}復(fù)制代碼
User 類為完全遵守各自合同的 equals() 和 hashCode() 提供自定義實現(xiàn)。更重要的是，讓 hashCode() 返回任何固定值并沒有什么不合法的。
但是，這種實現(xiàn)將哈希表的功能降級到基本上為零，因為每個對象都將存儲在同一個單個存儲桶中。
在這種情況下，哈希表查找是線性執(zhí)行的，并沒有給我們帶來任何真正的優(yōu)勢。我們將在第 7 節(jié)詳細(xì)討論。
5. 改進(jìn) hashCode() 實現(xiàn)
讓我們通過包含 User 類的所有字段來改進(jìn)當(dāng)前的 hashCode() 實現(xiàn)，以便它可以為不相等的對象產(chǎn)生不同的結(jié)果：
@Overridepublic int hashCode() {? ? return (int) id * name.hashCode() * email.hashCode();}復(fù)制代碼
這個基本的散列算法絕對比前一個好得多。這是因為它僅通過將 name 和 email 字段的哈希碼與 id 相乘來計算對象的哈希碼。
一般來說，我們可以說這是一個合理的 hashCode() 實現(xiàn)，只要我們保持 equals() 實現(xiàn)與其一致。
6. 標(biāo)準(zhǔn) hashCode() 實現(xiàn)
我們用來計算哈希碼的哈希算法越好，哈希表的性能就越好。
讓我們看看一個“標(biāo)準(zhǔn)”實現(xiàn)，它使用兩個素數(shù)為計算出的哈希碼添加更多的唯一性：
@Overridepublic 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;}復(fù)制代碼
雖然我們需要了解 hashCode() 和 equals() 方法所扮演的角色，但我們不必每次都從頭開始實現(xiàn)它們。這是因為大多數(shù) IDE 可以生成自定義 hashCode() 和 equals() 實現(xiàn)。從 Java 7 開始，我們有一個 Objects.hash() 實用方法來進(jìn)行舒適的散列：
Objects.hash(name, email)
IntelliJ IDEA 生成以下實現(xiàn)：
@Overridepublic int hashCode() {? ? int result = (int) (id ^ (id >>> 32));? ? result = 31 * result + name.hashCode();? ? result = 31 * result + email.hashCode();? ? return result;}復(fù)制代碼
Eclipse 產(chǎn)生了這個：
@Overridepublic 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;}復(fù)制代碼
除了上述基于 IDE 的 hashCode() 實現(xiàn)之外，還可以自動生成高效的實現(xiàn)，例如使用 Lombok.。
在這種情況下，我們需要在?pom.xml 中添加?lombok-maven 依賴：
<dependency>? <groupId>org.projectlombok</groupId>? <artifactId>lombok-maven</artifactId>? <version>1.16.18.0</version>? <type>pom</type></dependency>復(fù)制代碼
現(xiàn)在用 @EqualsAndHashCode 注解?User 類就足夠了：
@EqualsAndHashCodepublic class User {? ? // fields and methods here}復(fù)制代碼
同樣，如果我們希望 Apache Commons Lang 的?HashCodeBuilder 類為我們生成 hashCode() 實現(xiàn)，我們在 pom 文件中包含?commons-lang Maven 依賴項：
<dependency>? <groupId>commons-lang</groupId>? <artifactId>commons-lang</artifactId>? <version>2.6</version></dependency>復(fù)制代碼
hashCode() 可以這樣實現(xiàn)：
public class User {? ? public int hashCode() {? ? ? ? return new HashCodeBuilder(17, 37).? ? ? ? append(id).? ? ? ? append(name).? ? ? ? append(email).? ? ? ? toHashCode();? ? }}復(fù)制代碼
一般來說，在實現(xiàn) hashCode() 時沒有通用的方法。我們強(qiáng)烈推薦閱讀 Joshua Bloch 的 Effective Java.。它提供了實現(xiàn)高效散列算法的詳盡指南列表。
請注意，所有這些實現(xiàn)都以某種形式使用了數(shù)字 31。這是因為 31 有一個很好的屬性。它的乘法可以用按位移位代替，這比標(biāo)準(zhǔn)乘法要快：
31 * i == (i << 5) - i復(fù)制代碼
7. 處理哈希沖突
哈希表的內(nèi)在行為帶來了這些數(shù)據(jù)結(jié)構(gòu)的一個相關(guān)方面：即使使用有效的哈希算法，兩個或多個對象可能具有相同的哈希碼，即使它們不相等。因此，即使它們具有不同的散列表鍵，它們的散列碼也會指向同一個桶。
這種情況通常被稱為哈希沖突，有多種處理方法，每種方法都有其優(yōu)點和缺點。Java 的 HashMap 使用單獨的鏈接方法來處理沖突：
“當(dāng)兩個或多個對象指向同一個存儲桶時，它們只是存儲在一個鏈表中。在這種情況下，哈希表是一個鏈表數(shù)組，每個具有相同哈希值的對象都附加到鏈表中的桶索引處。
在最壞的情況下，幾個桶會綁定一個鏈表，而對鏈表中對象的檢索將是線性執(zhí)行的。”
哈希沖突方法簡單說明了高效實現(xiàn) hashCode() 的重要性。
Java 8 為?HashMap 實現(xiàn)帶來了有趣的增強(qiáng)。如果桶大小超過特定閾值，則樹圖替換鏈表。這允許實現(xiàn) O(logn) 查找而不是悲觀 O(n)。
8. 創(chuàng)建一個簡單的應(yīng)用程序
現(xiàn)在我們將測試標(biāo)準(zhǔn) hashCode() 實現(xiàn)的功能。
讓我們創(chuàng)建一個簡單的 Java 應(yīng)用程序，將一些 User 對象添加到 HashMap 并使用?SLF4J 在每次調(diào)用該方法時將消息記錄到控制臺。
這是示例應(yīng)用程序的入口點：
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");? ? ? ? }? ? }}復(fù)制代碼
這是 hashCode() 實現(xiàn)：
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;? ? }}復(fù)制代碼
這里需要注意的是，每次在哈希映射中存儲對象并使用 containsKey() 方法檢查時，都會調(diào)用 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: 1255477819User found in the collection復(fù)制代碼
9. 結(jié)論
很明顯，生成高效的 hashCode() 實現(xiàn)通常需要混合一些數(shù)學(xué)概念（即素數(shù)和任意數(shù)）、邏輯和基本數(shù)學(xué)運算。
無論如何，我們可以有效地實現(xiàn) hashCode() ，而無需使用這些技術(shù)。我們只需要確保散列算法為不相等的對象生成不同的哈希碼，并且它與 equals() 的實現(xiàn)一致。
與往常一樣，本文中顯示的所有代碼示例都可以在?GitHub?上找到。
