熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> Javascript >> 正文

Java 理論與實踐:哈希

2013-11-23 17:53:56  來源: Javascript 

  有效和正確定義hashCode()和equals()
  
  級別入門級
  
  Brian Goetz
  
  Quiotix Corp首席顧問
  
  
  
  每個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()您仍舊可以使用SystemidentityHashCode()方法來接入這類缺省值
  
  忽略 equals() 簡單實例
  缺省情況下equals()和hashCode()基於標識的實施是合理的但對於某些類來說它們希望放寬等式的定義例如Integer類定義equals() 與下面類似
  
  public boolean equals(Object obj) {
  
  return (obj instanceof Integer
  
  && intvalue() == ((Integer) obj)intvalue());
  
  }
  
  在這個定義中只有在包含相同的整數值的情況下這兩個Integer對象是相等的結合將不可修改的Integer這使得使用Integer作為HashMap中的關鍵字是切實可行的這種基於值的Equal方法可以由Java類庫中的所有原始封裝類使用如IntegerFloatCharacter和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)的重要性如HashtableHashMap和HashSet並且使用equals()與許多對象進行比較在計算方面非常昂貴使所有Java對象都能夠支持 hashCode()並結合使用基於散列的集合可以實現有效的存儲和檢索
  
  實施equals()和hashCode()的需求
  實施equals()和 hashCode()有一些限制Object文件中列舉出了這些限制特別是equals()方法必須顯示以下屬性
  
  Symmetry兩個引用a和 baequals(b) if and only if bequals(a)
  
  Reflexivity所有非空引用 aequals(a)
  
  TransitivityIf aequals(b) and bequals(c) then aequals(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 bit表示那麼它們是相等的
  
  對於比較復雜的類來說equals()和hashCode()的行為可能甚至受到superclass或interface的影響例如List接口要求如果並且只有另一個對象是List而且它們有相同順序的相同的Elements(由Element上的Objectequals() 定義)List對象等於另一個對象hashCode()的需求更特殊list的hashCode()值必須符合以下計算
  
  hashCode = ;
  
  Iterator i = erator();
  
  while (ihasNext()) {
  
  Object obj = inext();
  
  hashCode = *hashCode + (obj==null ? : objhashCode());
  
  }
  
  不僅僅散列值取決於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
  
  (someNonNullFieldequals(otherAsomeNonNullField))
  
  && ((someOtherField == null)
  
  ? otherAsomeOtherField == null
  
  : someOtherFieldequals(otherAsomeOtherField)));
  
  }
  
  現在我們定義了equals()我們必須以統一的方法來定義hashCode()一種統一但並不總是有效的定義hashCode()的方法如下
  
  public int hashCode() { return ; }
  
  這種方法將生成大量的條目並顯著降低HashMaps的性能但它符合規范一個更合理的hashCode()實施應該是這樣
  
  public int hashCode() {
  
  int hash = ;
  
  hash = hash * + someNonNullFieldhashCode();
  
  hash = hash *
  
  + (someOtherField == null ? : someOtherFieldhashCode());
  
  return hash;
  
  }
  
  注意這兩種實施都降低了類狀態字段的equals()或hashCode()方法一定比例的計算能力根據您使用的類您可能希望降低superclass的equals()或ha
From:http://tw.wingwit.com/Article/program/Java/Javascript/201311/25309.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.