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

閱覽次數(shù):
文章來源:
整理日期: 2005-05-12
字體大小: 小
 中
 大
 
原文：http://www-128.ibm.com/developerworks/cn/java/j-jtp05273/

Brian Goetz
首席顧問, Quiotix Corp
2003 年 8 月 11 日

每個(gè)Java對(duì)象都有 hashCode() 和 equals() 方法。許多類忽略（Override)這些方法的缺省實(shí)施,以在對(duì)象實(shí)例之間提供更深層次的語義可比性。在 Java理念和實(shí)踐這一部分，Java開發(fā)人員Brian Goetz向您介紹在創(chuàng)建Java類以有效和準(zhǔn)確定義 hashCode() 和 equals() 時(shí)應(yīng)遵循的規(guī)則和指南。您可以在 討論論壇與作者和其它讀者一同探討您對(duì)本文的看法。(您還可以點(diǎn)擊本文頂部或底部的 討論進(jìn)入論壇。)
雖然Java語言不直接支持關(guān)聯(lián)數(shù)組 -- 可以使用任何對(duì)象作為一個(gè)索引的數(shù)組 -- 但在根 Object 類中使用 hashCode() 方法明確表示期望廣泛使用 HashMap (及其前輩 Hashtable )。理想情況下基于散列的容器提供有效插入和有效檢索；直接在對(duì)象模式中支持散列可以促進(jìn)基于散列的容器的開發(fā)和使用。

定義對(duì)象的相等性
Object 類有兩種方法來推斷對(duì)象的標(biāo)識(shí)： equals() 和 hashCode() 。一般來說，如果您忽略了其中一種，您必須同時(shí)忽略這兩種，因?yàn)閮烧咧g有必須維持的至關(guān)重要的關(guān)系。特殊情況是根據(jù) equals() 方法，如果兩個(gè)對(duì)象是相等的，它們必須有相同的 hashCode() 值(盡管這通常不是真的)。

特定類的 equals() 的語義在Implementer的左側(cè)定義；定義對(duì)特定類來說 equals() 意味著什么是其設(shè)計(jì)工作的一部分。 Object 提供的缺省實(shí)施簡(jiǎn)單引用下面等式：

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

在這種缺省實(shí)施情況下，只有它們引用真正同一個(gè)對(duì)象時(shí)這兩個(gè)引用才是相等的。同樣， Object 提供的 hashCode() 的缺省實(shí)施通過將對(duì)象的內(nèi)存地址對(duì)映于一個(gè)整數(shù)值來生成。由于在某些架構(gòu)上，地址空間大于 int 值的范圍，兩個(gè)不同的對(duì)象有相同的 hashCode() 是可能的。如果您忽略了 hashCode() ，您仍舊可以使用 System.identityHashCode() 方法來接入這類缺省值。

忽略equals() -- 簡(jiǎn)單實(shí)例
缺省情況下， equals() 和 hashCode() 基于標(biāo)識(shí)的實(shí)施是合理的，但對(duì)于某些類來說，它們希望放寬等式的定義。例如， Integer 類定義 equals() 與下面類似：

  public boolean equals(Object obj) {
    return (obj instanceof Integer
            && intValue() == ((Integer) obj).intValue());
  }

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

為什么忽略equals()和hashCode()?
如果 Integer 不忽略 equals() 和 hashCode() 情況又將如何?如果我們從未在 HashMap 或其它基于散列的集合中使用 Integer 作為關(guān)鍵字的話，什么也不會(huì)發(fā)生。但是，如果我們?cè)?HashMap中 使用這類 Integer 對(duì)象作為關(guān)鍵字，我們將不能夠可靠地檢索相關(guān)的值，除非我們?cè)?get() 調(diào)用中使用與 put() 調(diào)用中極其類似的 Integer 實(shí)例。這要求確保在我們的整個(gè)程序中，只能使用對(duì)應(yīng)于特定整數(shù)值的 Integer 對(duì)象的一個(gè)實(shí)例。不用說，這種方法極不方便而且錯(cuò)誤頻頻。

Object 的interface contract要求如果根據(jù) equals() 兩個(gè)對(duì)象是相等的，那么它們必須有相同的 hashCode() 值。當(dāng)其識(shí)別能力整個(gè)包含在 equals() 中時(shí)，為什么我們的根對(duì)象類需要 hashCode() ？ hashCode() 方法純粹用于提高效率。Java平臺(tái)設(shè)計(jì)人員預(yù)計(jì)到了典型Java應(yīng)用程序中基于散列的集合類（Collection Class)的重要性--如 Hashtable 、 HashMap 和 HashSet ，并且使用 equals() 與許多對(duì)象進(jìn)行比較在計(jì)算方面非常昂貴。使所有Java對(duì)象都能夠支持 hashCode() 并結(jié)合使用基于散列的集合，可以實(shí)現(xiàn)有效的存儲(chǔ)和檢索。

實(shí)施equals()和hashCode()的需求
實(shí)施 equals() 和 hashCode() 有一些限制， Object 文件中列舉出了這些限制。特別是 equals() 方法必須顯示以下屬性：

Symmetry：兩個(gè)引用， 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() ：兩個(gè)相等的對(duì)象必須有相同的 hashCode() 值
Object 的規(guī)范中并沒有明確要求 equals() 和 hashCode() 必須 一致-- 它們的結(jié)果在隨后的調(diào)用中將是相同的，假設(shè)“不改變對(duì)象相等性比較中使用的任何信息。”這聽起來象“計(jì)算的結(jié)果將不改變，除非實(shí)際情況如此。”這一模糊聲明通常解釋為相等性和散列值計(jì)算應(yīng)是對(duì)象的可確定性功能，而不是其它。

對(duì)象相等性意味著什么？
人們很容易滿足Object類規(guī)范對(duì) equals() 和 hashCode() 的要求。決定是否和如何忽略 equals() 除了判斷以外，還要求其它。在簡(jiǎn)單的不可修值類中，如 Integer (事實(shí)上是幾乎所有不可修改的類)，選擇相當(dāng)明顯 -- 相等性應(yīng)基于基本對(duì)象狀態(tài)的相等性。在 Integer 情況下，對(duì)象的唯一狀態(tài)是基本的整數(shù)值。

對(duì)于可修改對(duì)象來說，答案并不總是如此清楚。 equals() 和 hashCode() 是否應(yīng)基于對(duì)象的標(biāo)識(shí)(象缺省實(shí)施)或?qū)ο蟮臓顟B(tài)(象Integer和String)？沒有簡(jiǎn)單的答案 -- 它取決于類的計(jì)劃使用。對(duì)于象 List 和 Map 這樣的容器來說，人們對(duì)此爭(zhēng)論不已。Java類庫(kù)中的大多數(shù)類，包括容器類，錯(cuò)誤出現(xiàn)在根據(jù)對(duì)象狀態(tài)來提供 equals() 和 hashCode() 實(shí)施。

如果對(duì)象的 hashCode() 值可以基于其狀態(tài)進(jìn)行更改，那么當(dāng)使用這類對(duì)象作為基于散列的集合中的關(guān)鍵字時(shí)我們必須注意，確保當(dāng)它們用于作為散列關(guān)鍵字時(shí)，我們并不允許更改它們的狀態(tài)。所有基于散列的集合假設(shè)，當(dāng)對(duì)象的散列值用于作為集合中的關(guān)鍵字時(shí)它不會(huì)改變。如果當(dāng)關(guān)鍵字在集合中時(shí)它的散列代碼被更改，那么將產(chǎn)生一些不可預(yù)測(cè)和容易混淆的結(jié)果。實(shí)踐過程中這通常不是問題 -- 我們并不經(jīng)常使用象 List 這樣的可修改對(duì)象做為 HashMap 中的關(guān)鍵字。

一個(gè)簡(jiǎn)單的可修改類的例子是Point，它根據(jù)狀態(tài)來定義 equals() 和 hashCode() 。如果兩個(gè) Point 對(duì)象引用相同的 (x, y) 座標(biāo)， Point 的散列值來源于 x 和 y 座標(biāo)值的IEEE 754-bit表示，那么它們是相等的。

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

  hashCode = 1;
  Iterator i = list.iterator();
  while (i.hasNext()) {
      Object obj = i.next();
      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
  }

不僅僅散列值取決于list的內(nèi)容，而且還規(guī)定了結(jié)合各個(gè)Element的散列值的特殊算法。( String 類規(guī)定類似的算法用于計(jì)算 String 的散列值。)

編寫自己的equals()和hashCode()方法
忽略缺省的 equals() 方法比較簡(jiǎn)單，但如果不違反對(duì)稱（Symmetry）或傳遞性（Transitivity）需求，忽略已經(jīng)忽略的 equals() 方法極其棘手。當(dāng)忽略 equals() 時(shí)，您應(yīng)該總是在 equals() 中包括一些Javadoc注釋，以幫助那些希望能夠正確擴(kuò)展您的類的用戶。

作為一個(gè)簡(jiǎn)單的例子，考慮以下類：

  class A {
    final B someNonNullField;
    C someOtherField;
    int someNonStateField;
  }

我們應(yīng)如何編寫該類的 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)));
  }

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

  public int hashCode() { return 0; }

這種方法將生成大量的條目并顯著降低 HashMap s的性能，但它符合規(guī)范。一個(gè)更合理的 hashCode() 實(shí)施應(yīng)該是這樣：

  public int hashCode() {
    int hash = 1;
    hash = hash * 31 + someNonNullField.hashCode();
    hash = hash * 31
                + (someOtherField == null ? 0 : someOtherField.hashCode());
    return hash;
  }

注意：這兩種實(shí)施都降低了類狀態(tài)字段的 equals() 或 hashCode() 方法一定比例的計(jì)算能力。根據(jù)您使用的類，您可能希望降低superclass的 equals() 或 hashCode() 功能一部分計(jì)算能力。對(duì)于原始字段來說，在相關(guān)的封裝類中有helper功能，可以幫助創(chuàng)建散列值，如 Float.floatToIntBits 。

編寫一個(gè)完美的 equals() 方法是不現(xiàn)實(shí)的。通常，當(dāng)擴(kuò)展一個(gè)自身忽略了 equals() 的instantiable類時(shí)，忽略 equals() 是不切實(shí)際的，而且編寫將被忽略的 equals() 方法(如在抽象類中)不同于為具體類編寫 equals() 方法。關(guān)于實(shí)例以及說明的更詳細(xì)信息請(qǐng)參閱 Effective Java Programming Language Guide, Item 7 ( 參考資料) 。

有待改進(jìn)?
將散列法構(gòu)建到Java類庫(kù)的根對(duì)象類中是一種非常明智的設(shè)計(jì)折衷方法 -- 它使使用基于散列的容器變得如此簡(jiǎn)單和高效。但是，人們對(duì)Java類庫(kù)中的散列算法和對(duì)象相等性的方法和實(shí)施提出了許多批評(píng)。 java.util 中基于散列的容器非常方便和簡(jiǎn)便易用，但可能不適用于需要非常高性能的應(yīng)用程序。雖然其中大部分將不會(huì)改變，但當(dāng)您設(shè)計(jì)嚴(yán)重依賴于基于散列的容器效率的應(yīng)用程序時(shí)必須考慮這些因素，它們包括：

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

糟糕的散列值分配。短strings和小型integers的散列值是它們自己的小整數(shù)，接近于其它“鄰近”對(duì)象的散列值。一個(gè)循規(guī)導(dǎo)矩（Well-behaved）的散列函數(shù)將在該散列范圍內(nèi)更均勻地分配散列值。
無定義的散列操作。雖然某些類，如 String 和 List ，定義了將其Element的散列值結(jié)合到一個(gè)散列值中使用的散列算法，但語言規(guī)范不定義將多個(gè)對(duì)象的散列值結(jié)合到新散列值中的任何批準(zhǔn)的方法。我們?cè)谇懊?編寫自己的equals()和hashCode()方法中討論的 List 、 String 或?qū)嵗?A 使用的訣竅都很簡(jiǎn)單，但算術(shù)上還遠(yuǎn)遠(yuǎn)不夠完美。類庫(kù)不提供任何散列算法的方便實(shí)施，它可以簡(jiǎn)化更先進(jìn)的 hashCode() 實(shí)施的創(chuàng)建。

當(dāng)擴(kuò)展已經(jīng)忽略了 equals() 的 instantiable類時(shí)很難編寫 equals() 。當(dāng)擴(kuò)展已經(jīng)忽略了 equals() 的 instantiable類時(shí)，定義 equals() 的“顯而易見的”方式都不能滿足 equals() 方法的對(duì)稱或傳遞性需求。這意味著當(dāng)忽略 equals() 時(shí)，您必須了解您正在擴(kuò)展的類的結(jié)構(gòu)和實(shí)施詳細(xì)信息，甚至需要暴露基本類中的機(jī)密字段，它違反了面向?qū)ο蟮脑O(shè)計(jì)的原則。
結(jié)束語
通過統(tǒng)一定義 equals() 和 hashCode()， 您可以提升類作為基于散列的集合中的關(guān)鍵字的使用性。有兩種方法來定義對(duì)象的相等性和散列值：基于標(biāo)識(shí)，它是 Object 提供的缺省方法；基于狀態(tài)，它要求忽略 equals() 和 hashCode() 。當(dāng)對(duì)象的狀態(tài)更改時(shí)如果對(duì)象的散列值發(fā)生變化，確信當(dāng)狀態(tài)作為散列關(guān)鍵字使用時(shí)您不允許更更改其狀態(tài)。

參考資料

您可以參閱本文在 developerWorks 全球站點(diǎn)上的 英文原文.

參加本文的 討論論壇。(您還可以點(diǎn)擊本文頂部或底部的 討論進(jìn)入論壇。)

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

Joshua Bloch杰作的第 7和 8部分 Java編程語言指南 ，詳細(xì)闡述圍繞 equals() 和 hashCode() 的問題。

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

在幻燈片中，新西蘭奧克蘭大學(xué)計(jì)算機(jī)科學(xué)系的Robert Uzgalis介紹一些 Java散列模式的批評(píng)意見，解釋一些散列函數(shù)背后的問題。

Mark Roulo 在自己的文章“如何避免陷阱和正確忽略java.lang.Object的方法”( JavaWorld, 1999年1月)一文中提供了一些 忽略 equals() 和 hashCode() 的實(shí)例程序代碼 。

新西蘭坎特伯雷大學(xué)計(jì)算機(jī)科學(xué)系提供的這一份技術(shù)報(bào)告詳細(xì)描述了 what makes an effective hash function(PDF)。

IBM軟件實(shí)驗(yàn)室軟件工程師Sreekanth Iyer 探討了Java對(duì)象相等性的各種不同意義( developerWorks, 2002年9月)。

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

在 developerWorksJava技術(shù)專區(qū) 可以找到數(shù)百篇有關(guān) Java 技術(shù)的參考資料。.

關(guān)于作者
Brian Goetz過去15年以來一直是專業(yè)軟件開發(fā)人員。他是 Quiotix的首席顧問， Quiotix是位于加利福尼亞 Los Altos的一家軟件開發(fā)和咨詢公司。參閱Brian在流行行業(yè)出版物中 已經(jīng)出版和即將出版的文章。可以通過 brian@quiotix.com與 Brian聯(lián)系。