有效和正确定義hashCode()和equals()

Brian Goetz

首席顧問, Quiotix Corp

2003 年 8 月 11 日

每個Java對象都有 hashCode() 和 equals() 方法。許多類忽略（Override)這些方法的預設實施,以在對象執行個體之間提供更深層次的語義可比性。在 Java理念和實踐這一部分，Java開發人員Brian Goetz向您介紹在建立Java類以有效和準确定義 hashCode() 和 equals() 時應遵循的規則和指南。您可以在 讨論論壇與作者和其它讀者一同探讨您對本文的看法。(您還可以點選本文頂部或底部的 讨論進入論壇。) 

雖然Java語言不直接支援關聯數組 -- 可以使用任何對象作為一個索引的數組 -- 但在根 Object 類中使用 hashCode() 方法明确表示期望廣泛使用 HashMap (及其前輩 Hashtable )。理想情況下基于散列的容器提供有效插入和有效檢索；直接在對象模式中支援散列可以促進基于散列的容器的開發和使用。 

定義對象的相等性

Object 類有兩種方法來推斷對象的辨別： equals() 和 hashCode() 。一般來說，如果您忽略了其中一種，您必須同時忽略這兩種，因為兩者之間有必須維持的至關重要的關系。特殊情況是根據 equals() 方法，如果兩個對象是相等的，它們必須有相同的 hashCode() 值(盡管這通常不是真的)。 

特定類的 equals() 的語義在Implementer的左側定義；定義對特定類來說 equals() 意味着什麼是其設計工作的一部分。 Object 提供的預設實施簡單引用下面等式： 

  public boolean equals(Object obj) { return (this == obj); }

在這種預設實施情況下，隻有它們引用真正同一個對象時這兩個引用才是相等的。同樣， Object 提供的 hashCode() 的預設實施通過将對象的記憶體位址對映于一個整數值來生成。由于在某些架構上，位址空間大于 int 值的範圍，兩個不同的對象有相同的 hashCode() 是可能的。如果您忽略了 hashCode() ，您仍舊可以使用 System.identityHashCode() 方法來接入這類預設值。 

忽略equals() -- 簡單執行個體

預設情況下， equals() 和 hashCode() 基于辨別的實施是合理的，但對于某些類來說，它們希望放寬等式的定義。例如， Integer 類定義 equals() 與下面類似： 

  public boolean equals(Object obj) {

    return (obj instanceof Integer 

            && intValue() == ((Integer) obj).intValue());

  }

在這個定義中，隻有在包含相同的整數值的情況下這兩個 Integer 對象是相等的。結合将不可修改的 Integer ，這使得使用 Integer 作為 HashMap 中的關鍵字是切實可行的。這種基于值的Equal方法可以由Java類庫中的所有原始封裝類使用，如 Integer 、 Float 、 Character 和 Boolean 以及 String (如果兩個 String 對象包含相同順序的字元，那它們是相等的)。由于這些類都是不可修改的并且可以實施 hashCode() 和 equals() ，它們都可以做為很好的散列關鍵字。 

為什麼忽略equals()和hashCode()?

如果 Integer 不忽略 equals() 和 hashCode() 情況又将如何?如果我們從未在 HashMap 或其它基于散列的集合中使用 Integer 作為關鍵字的話，什麼也不會發生。但是，如果我們在 HashMap中 使用這類 Integer 對象作為關鍵字，我們将不能夠可靠地檢索相關的值，除非我們在 get() 調用中使用與 put() 調用中極其類似的 Integer 執行個體。這要求確定在我們的整個程式中，隻能使用對應于特定整數值的 Integer 對象的一個執行個體。不用說，這種方法極不友善而且錯誤頻頻。 

Object 的interface contract要求如果根據 equals() 兩個對象是相等的，那麼它們必須有相同的 hashCode() 值。當其識别能力整個包含在 equals() 中時，為什麼我們的根對象類需要 hashCode() ？ hashCode() 方法純粹用于提高效率。Java平台設計人員預計到了典型Java應用程式中基于散列的集合類（Collection Class)的重要性--如 Hashtable 、 HashMap 和 HashSet ，并且使用 equals() 與許多對象進行比較在計算方面非常昂貴。使所有Java對象都能夠支援 hashCode() 并結合使用基于散列的集合，可以實作有效的存儲和檢索。 

實施equals()和hashCode()的需求

實施 equals() 和 hashCode() 有一些限制， Object 檔案中列舉出了這些限制。特别是 equals() 方法必須顯示以下屬性： 

Symmetry：兩個引用， a 和 b , a.equals(b) if and only if b.equals(a) 

Reflexivity：所有非空引用， a.equals(a) 

Transitivity：If a.equals(b) and b.equals(c) , then a.equals(c) 

Consistency with hashCode() ：兩個相等的對象必須有相同的 hashCode() 值 

Object 的規範中并沒有明确要求 equals() 和 hashCode() 必須 一緻-- 它們的結果在随後的調用中将是相同的，假設“不改變對象相等性比較中使用的任何資訊。”這聽起來象“計算的結果将不改變，除非實際情況如此。”這一模糊聲明通常解釋為相等性和散列值計算應是對象的可确定性功能，而不是其它。 

對象相等性意味着什麼？

人們很容易滿足Object類規範對 equals() 和 hashCode() 的要求。決定是否和如何忽略 equals() 除了判斷以外，還要求其它。在簡單的不可修值類中，如 Integer (事實上是幾乎所有不可修改的類)，選擇相當明顯 -- 相等性應基于基本對象狀态的相等性。在 Integer 情況下，對象的唯一狀态是基本的整數值。 

對于可修改對象來說，答案并不總是如此清楚。 equals() 和 hashCode() 是否應基于對象的辨別(象預設實施)或對象的狀态(象Integer和String)？沒有簡單的答案 -- 它取決于類的計劃使用。對于象 List 和 Map 這樣的容器來說，人們對此争論不已。Java類庫中的大多數類，包括容器類，錯誤出現在根據對象狀态來提供 equals() 和 hashCode() 實施。 

如果對象的 hashCode() 值可以基于其狀态進行更改，那麼當使用這類對象作為基于散列的集合中的關鍵字時我們必須注意，確定當它們用于作為散列關鍵字時，我們并不允許更改它們的狀态。所有基于散列的集合假設，當對象的散列值用于作為集合中的關鍵字時它不會改變。如果當關鍵字在集合中時它的散列代碼被更改，那麼将産生一些不可預測和容易混淆的結果。實踐過程中這通常不是問題 -- 我們并不經常使用象 List 這樣的可修改對象做為 HashMap 中的關鍵字。 

一個簡單的可修改類的例子是Point，它根據狀态來定義 equals() 和 hashCode() 。如果兩個 Point 對象引用相同的 (x, y) 座标， Point 的散列值來源于 x 和 y 座标值的IEEE 754-bit表示，那麼它們是相等的。 

對于比較複雜的類來說， equals() 和 hashCode() 的行為可能甚至受到superclass或interface的影響。例如， List 接口要求如果并且隻有另一個對象是 List， 而且它們有相同順序的相同的Elements(由Element上的 Object.equals() 定義)， List 對象等于另一個對象。 hashCode() 的需求更特殊--list的 hashCode() 值必須符合以下計算： 

  hashCode = 1;

  Iterator i = list.iterator();

  while (i.hasNext()) {

      Object obj = i.next();

      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());

不僅僅散列值取決于list的内容，而且還規定了結合各個Element的散列值的特殊算法。( String 類規定類似的算法用于計算 String 的散列值。) 

編寫自己的equals()和hashCode()方法

忽略預設的 equals() 方法比較簡單，但如果不違反對稱（Symmetry）或傳遞性（Transitivity）需求，忽略已經忽略的 equals() 方法極其棘手。當忽略 equals() 時，您應該總是在 equals() 中包括一些Javadoc注釋，以幫助那些希望能夠正确擴充您的類的使用者。 

作為一個簡單的例子，考慮以下類： 

  class A {

    final B someNonNullField;

    C someOtherField;

    int someNonStateField;

我們應如何編寫該類的 equals() 的方法？這種方法适用于許多情況： 

  public boolean equals(Object other) {

    // Not strictly necessary, but often a good optimization

    if (this == other)

      return true;

    if (!(other instanceof A))

      return false;

    A otherA = (A) other;

    return 

      (someNonNullField.equals(otherA.someNonNullField))

        && ((someOtherField == null) 

            ? otherA.someOtherField == null 

            : someOtherField.equals(otherA.someOtherField)));

現在我們定義了 equals() ，我們必須以統一的方法來定義 hashCode() 。一種統一但并不總是有效的定義 hashCode() 的方法如下： 

  public int hashCode() { return 0; }

這種方法将生成大量的條目并顯著降低 HashMap s的性能，但它符合規範。一個更合理的 hashCode() 實施應該是這樣： 

  public int hashCode() { 

    int hash = 1;

    hash = hash * 31 + someNonNullField.hashCode();

    hash = hash * 31 

                + (someOtherField == null ? 0 : someOtherField.hashCode());

    return hash;

注意：這兩種實施都降低了類狀态字段的 equals() 或 hashCode() 方法一定比例的計算能力。根據您使用的類，您可能希望降低superclass的 equals() 或 hashCode() 功能一部分計算能力。對于原始字段來說，在相關的封裝類中有helper功能，可以幫助建立散列值，如 Float.floatToIntBits 。 

編寫一個完美的 equals() 方法是不現實的。通常，當擴充一個自身忽略了 equals() 的instantiable類時，忽略 equals() 是不切實際的，而且編寫将被忽略的 equals() 方法(如在抽象類中)不同于為具體類編寫 equals() 方法。關于執行個體以及說明的更詳細資訊請參閱 Effective Java Programming Language Guide, Item 7 ( 參考資料) 。 

有待改進?

将散列法建構到Java類庫的根對象類中是一種非常明智的設計折衷方法 -- 它使使用基于散列的容器變得如此簡單和高效。但是，人們對Java類庫中的雜湊演算法和對象相等性的方法和實施提出了許多批評。 java.util 中基于散列的容器非常友善和簡便易用，但可能不适用于需要非常高性能的應用程式。雖然其中大部分将不會改變，但當您設計嚴重依賴于基于散列的容器效率的應用程式時必須考慮這些因素，它們包括： 

太小的散列範圍。使用 int 而不是 long 作為 hashCode() 的傳回類型增加了散列沖突的幾率。 

糟糕的散列值配置設定。短strings和小型integers的散列值是它們自己的小整數，接近于其它“鄰近”對象的散列值。一個循規導矩（Well-behaved）的散列函數将在該散列範圍内更均勻地配置設定散列值。 

無定義的散列操作。雖然某些類，如 String 和 List ，定義了将其Element的散列值結合到一個散列值中使用的雜湊演算法，但語言規範不定義将多個對象的散列值結合到新散列值中的任何準許的方法。我們在前面 編寫自己的equals()和hashCode()方法中讨論的 List 、 String 或執行個體類 A 使用的訣竅都很簡單，但算術上還遠遠不夠完美。類庫不提供任何雜湊演算法的友善實施，它可以簡化更先進的 hashCode() 實施的建立。 

當擴充已經忽略了 equals() 的 instantiable類時很難編寫 equals() 。當擴充已經忽略了 equals() 的 instantiable類時，定義 equals() 的“顯而易見的”方式都不能滿足 equals() 方法的對稱或傳遞性需求。這意味着當忽略 equals() 時，您必須了解您正在擴充的類的結構和實施詳細資訊，甚至需要暴露基本類中的機密字段，它違反了面向對象的設計的原則。 

結束語

通過統一定義 equals() 和 hashCode()， 您可以提升類作為基于散列的集合中的關鍵字的使用性。有兩種方法來定義對象的相等性和散列值：基于辨別，它是 Object 提供的預設方法；基于狀态，它要求忽略 equals() 和 hashCode() 。當對象的狀态更改時如果對象的散列值發生變化，确信當狀态作為散列關鍵字使用時您不允許更更改其狀态。 

參考資料 

您可以參閱本文在 developerWorks 全球站點上的 英文原文. 

參加本文的 讨論論壇。(您還可以點選本文頂部或底部的 讨論進入論壇。) 

閱讀Brian Goetz撰寫的一整套 Java理論和實踐文章 。尤其是2003年2月“ Java 理論與實踐：變還是不變？，”它讨論使用可變對象作為散列關鍵字的危害。 

Joshua Bloch傑作的第 7和 8部分 Java程式設計語言指南 ，詳細闡述圍繞 equals() 和 hashCode() 的問題。 

Tony Sintes在 JavaWorld提供的本文中解釋 基于散列的容器是如何工作的以及如何使用 equals() 和 hashCode() (2002年7月)。 

在幻燈片中，紐西蘭奧克蘭大學計算機科學系的Robert Uzgalis介紹一些 Java散列模式的批評意見，解釋一些散列函數背後的問題。 

Mark Roulo 在自己的文章“如何避免陷阱和正确忽略java.lang.Object的方法”( JavaWorld, 1999年1月)一文中提供了一些 忽略 equals() 和 hashCode() 的執行個體程式代碼 。 

紐西蘭坎特伯雷大學計算機科學系提供的這一份技術報告較長的描述了 what makes an effective hash function(PDF)。 

IBM軟體實驗室軟體工程師Sreekanth Iyer 探讨了Java對象相等性的各種不同意義( developerWorks, 2002年9月)。 

JavaWorld(獲得許可後才可再版)的提示略微談到 相等性比較的缺陷。 

在 developerWorksJava技術專區 可以找到數百篇有關 Java 技術的參考資料。. 

關于作者

Brian Goetz過去15年以來一直是專業軟體開發人員。他是 Quiotix的首席顧問， Quiotix是位于加利福尼亞 Los Altos的一家軟體開發和咨詢公司。參閱Brian在流行行業出版物中 已經出版和即将出版的文章。可以通過 [email protected]與 Brian聯系。