ITEM 11：ALWAYS OVERRIDE HASHCODE WHEN YOU OVERRIDE EQUALS
??必須在每個重寫了 equals 方法的類中重寫 hashCode 方法急黎，如果不這樣做，您的類將違反 hashCode 的通用契約侧到，這可能導致它在 HashMap 和HashSet 這類集合中運行異常勃教。根據(jù) Object 規(guī)范，下面是具體的條款：

• 當在程序執(zhí)行過程中反復調(diào)用對象的 hashCode 方法時匠抗，它必須始終返回相同的值（前提是在equals方法中不修改任何信息）故源，此值不需要在程序的一次執(zhí)行與另一次執(zhí)行之間保持一致。
• 如果兩個對象 調(diào)用equals(Object) 方法汞贸，結果是相等的绳军，那么對這兩個對象調(diào)用hashCode 也必須返回相同的結果。
• 如果兩個對象 調(diào)用equals(Object) 方法矢腻，結果不相等门驾，則不需要對每個對象調(diào)用hashCode 都必須產(chǎn)生不同的結果。但是多柑，程序員應該意識到奶是，為不同的對象生成不同的 hashcode 可以提高哈希表的性能。
  當您無法重寫 hashCode 方法時竣灌，違反的關鍵條款是第二個：相等的對象必須具有相等的 hashcode诫隅。類的equals方法的語義是，判斷兩個不同的實例在邏輯上是否是相等的帐偎，但是對于對象的 hashCode 方法來說逐纬，它們只是兩個沒有太多共同點的對象。因此削樊，Object 的 hashCode 方法可以返回兩個看似隨機的數(shù)字豁生，而不是契約要求的兩個相等的數(shù)字。
  ??例如漫贞，假設您嘗試使用 item 10 中的 PhoneNumber 類的實例作為 HashMap 中的鍵:
  Map<PhoneNumber, String> m = new HashMap<>(); m.put(new PhoneNumber(707, 867, 5309), "Jenny");
  ??此時甸箱，你也許希望 m.get(new PhoneNumber(707, 867, 5309)) 返回 "Jenny"，但實際上代碼將返回null迅脐。注意芍殖，涉及兩個 PhoneNumber 實例：一個用于插入HashMap，另一個實例是我們檢索時新生成的谴蔑。PhoneNumber 類未能覆蓋hashCode 導致兩個相等的實例具有不同的散列碼豌骏，這違反了 hashCode 契約龟梦。因此，get方法可能會在與 put 方法命中的散列桶中查找窃躲。
  ??即使這兩個實例碰巧散列到同一個 bucket计贰，get 方法也幾乎肯定會返回 null，因為HashMap 有一個優(yōu)化蒂窒，可以緩存與每個條目關聯(lián)的散列碼躁倒，如果散列代碼不匹配，也不需要檢查對象是否相等洒琢。
  ??解決這個問題很簡單秧秉，只要為 PhoneNumber 編寫一個合適的 hashCode 方法就可以了。那么hashCode 方法應該是什么樣的呢衰抑？寫一個不符合規(guī)范的例子很簡單福贞，例如下面這條是合法的，但我們不應該使用：

// The worst possible legal hashCode implementation - never use!
@Override public int hashCode() { return 42; }

??這是合法的停士，因為它確保相等的對象具有相同的哈希碼挖帘。但它很糟糕，因為它讓所有對象都有相同的哈希碼恋技。因此拇舀，每個對象都散列到同一個桶中，散列表退化為鏈表蜻底。程序應該在 O(n) 時間運行骄崩，而不是在 O(n2) 運行。對于大型哈希表薄辅，可能導致程序無法工作要拂。
??一個好的哈希函數(shù)往往會為不相等的實例生成不同的哈希碼。這正是 hashCode 契約的第三部分的含義站楚。理想情況下脱惰，哈希函數(shù)應該在所有 int 值上均勻地分布任何合理的不相等實例集合。實現(xiàn)這一理想可能很困難窿春。幸運的是拉一，得到一個合理的近似并不難。這里有一個簡單的方法:

• 1. 聲明一個名為 result 的 int 變量旧乞，并將其初始化為對象中第一個重要字段的哈希碼c蔚润，如步驟2.a中計算的那樣。(回顧 itme 10尺栖，一個重要字段是一個影響等號比較的字段嫡纠。)
• 2. 對于對象中剩余的重要字段f，執(zhí)行以下操作:
     a.計算字段的int哈希碼c：
     i. 如果字段是基本類型，計算 Type.hashCode(f)除盏，其中type是與f的類型對應的裝箱基元類叉橱。
     ii. 如果字段是對象引用，并且該類的 equals 方法通過遞歸調(diào)用 equals 來比較字段痴颊，則遞歸調(diào)用字段上的 hashCode。如果需要更復雜的比較屡贺，請為該字段計算一個“規(guī)范表示”蠢棱，并在規(guī)范表示上調(diào)用hashCode。如果字段的值為null甩栈，則使用0 (或其他常量泻仙，但0是傳統(tǒng)的)。
     iii. 如果字段是一個數(shù)組量没，則將其中每個重要元素視為一個單獨的字段玉转。也就是說，通過遞歸地應用這些規(guī)則殴蹄，為每個重要元素計算一個哈希碼究抓，并在每個步驟2.b中組合這些值。如果數(shù)組沒有重要元素袭灯，則使用常量刺下，最好不是0。如果所有的元素都是重要的稽荧，使用Arrays.hashCode橘茉。
     b.結合步驟2中計算的哈希碼c。a轉化結果如下:
     result = 31 * result + c;
• 3. Return result.
     ??當您完成 hashCode 方法的編寫時姨丈，請自問 equal 實例是否具有相同的散列代碼畅卓。編寫單元測試來驗證您的直覺(除非您使用AutoValue來生成equals和hashCode方法，在這種情況下蟋恬，您可以安全地忽略這些測試)翁潘。如果相等的實例有不相等的哈希碼，找出原因并解決問題歼争。
     ??可以在哈希碼計算中排除派生字段唐础。換句話說，您可以忽略任何字段矾飞，其值可以從計算中包含的字段計算出來一膨。
     ??您必須排除在equals比較中沒有使用的任何字段，否則您可能會違反 hashCode 契約的第二項規(guī)定洒沦。
     ??2.b 中的乘法使結果依賴于字段的順序豹绪，如果類有多個類似的字段，則生成更好的散列函數(shù)。例如瞒津，如果從字符串哈希函數(shù)中省略乘法蝉衣，所有的字謎都將具有相同的哈希代碼。之所以選擇31巷蚪，是因為它是一個質(zhì)數(shù)病毡。如果它是偶數(shù)，并且乘法溢出屁柏，信息就會丟失啦膜，因為乘以2等于移位。使用質(zhì)數(shù)的優(yōu)勢不太明顯淌喻，但它是傳統(tǒng)的僧家。31的一個很好的特性是，可以用移位和減法替換乘法裸删，從而在某些架構上獲得更好的性能:
     31 * i == (i << 5) - i
     ??讓我們將之前的方法應用到PhoneNumber類：

// Typical hashCode method
@Override public int hashCode() {
  int result = Short.hashCode(areaCode);
  result = 31 * result + Short.hashCode(prefix); 
  result = 31 * result + Short.hashCode(lineNum); 
  return result;
}

??由于該方法返回一個簡單確定性計算的結果八拱，該計算的唯一輸入是PhoneNumber實例中的三個重要字段。顯然涯塔，相同的PhoneNumber實例具有相同的哈希碼肌稻。實際上，這個方法是 PhoneNumber 的一個非常好的 hashCode 實現(xiàn)匕荸，可以與Java平臺庫中的實現(xiàn)相媲美灯萍。它很簡單，速度也相當快每聪，并且能夠?qū)⒉幌嗟鹊碾娫捥柎a分散到不同的散列桶中旦棉。
??雖然上面的例子是一個相當好的散列函數(shù)，但它們并不是最棒的药薯。它們在質(zhì)量上可以與Java平臺庫的值類型中的散列函數(shù)相媲美绑洛，并且對于大多數(shù)用途都是足夠的。如果您確實需要不太可能產(chǎn)生沖突的散列函數(shù)童本，請參閱Guava的com.google.common.hash.Hashing [Guava]真屯。
??Objects類有一個靜態(tài)方法，它接受任意數(shù)量的對象并為它們返回一個散列代碼穷娱。這個名為 hash 的方法允許您編寫單行 hashCode 方法绑蔫，其質(zhì)量可與根據(jù)該項目中的配方編寫的方法相媲美。不幸的是泵额，它們運行得更慢配深，因為它們需要創(chuàng)建數(shù)組來傳遞可變數(shù)量的參數(shù)，如果其中任何參數(shù)是原始類型嫁盲，則需要裝箱和解箱篓叶。建議只在性能不重要的情況下使用這種類型的哈希函數(shù)。下面是一個使用這種技術編寫的PhoneNumber 函數(shù):

// One-line hashCode method - mediocre performance
@Override public int hashCode() {
  return Objects.hash(lineNum, prefix, areaCode);
}

??如果一個類是不可變的，并且計算散列代碼的成本很高缸托，那么您可以考慮將散列代碼緩存到對象中左敌，而不是每次請求時重新計算它。如果您認為這種類型的大多數(shù)對象都將用作散列鍵俐镐，那么您應該在創(chuàng)建實例時計算散列代碼矫限。否則，您可能選擇在第一次調(diào)用散列代碼時惰性地初始化散列代碼佩抹。需要注意叼风，確保類在存在延遲初始化的字段時仍然是線程安全的。我們的 PhoneNumber 類不需要這種處理匹摇，但只是向您展示它是如何完成的咬扇，在這里甲葬。注意廊勃，hashCode字段的初始值(在本例中為0)不應該是通常創(chuàng)建的實例的哈希碼：

// hashCode method with lazily initialized cached hash code private int hashCode; 
// Automatically initialized to 0
@Override public int hashCode() { 
  int result = hashCode;
  if (result == 0) {
    result = Short.hashCode(areaCode);
    result = 31 * result + Short.hashCode(prefix); 
    result = 31 * result + Short.hashCode(lineNum); 
    hashCode = result;
  }
  return result; 
}

??不要試圖從哈希代碼計算中排除重要字段來提高性能。雖然生成的哈希函數(shù)可能運行得更快经窖，但其質(zhì)量差可能會降低哈希表的性能坡垫，使其無法使用。特別是画侣，哈希函數(shù)可能會遇到大量實例冰悠，這些實例主要在您選擇忽略的區(qū)域中不同。如果發(fā)生這種情況配乱，哈希函數(shù)將把所有這些實例映射到幾個哈希代碼溉卓，應該在線性時間內(nèi)運行的程序?qū)⒃诙螘r間內(nèi)運行。
??這不僅僅是一個理論問題搬泥。在Java 2之前桑寨，字符串哈希函數(shù)最多使用16個字符，以第一個字符開始忿檩，在整個字符串中平均間隔尉尾。對于層次結構名稱的大集合(如url)，此函數(shù)完全顯示了前面描述的病態(tài)行為燥透。
??不要為 hashCode 返回的值提供詳細的規(guī)范沙咏，因此客戶端不能合理地依賴它；這使您可以靈活地更改它班套。Java庫中的許多類肢藐，如 String 和 Integer，都指定它們的hashCode 方法返回的確切值作為實例值的函數(shù)吱韭。這不是一個好主意窖壕，而是我們不得不面對的一個錯誤：它阻礙了在未來版本中改進 hash 函數(shù)的能力。如果您沒有指定細節(jié)，并且在散列函數(shù)中發(fā)現(xiàn)了一個缺陷瞻讽，或者發(fā)現(xiàn)了一個更好的散列函數(shù)鸳吸，您可以在后續(xù)版本中修改它。
??總之速勇，每次重寫 equals 時都必須重寫 hashCode晌砾，否則程序?qū)o法正確運行。您的hashCode 方法必須遵守對象中指定的通用契約烦磁，并且必須合理地為不相等的實例分配不相等的哈希碼养匈。使用本文提供的規(guī)范，這很容易實現(xiàn)都伪，盡管有點乏味呕乎。正如item 10 中提到的，AutoValue 框架提供了一個很好的替代方法陨晶，可以替代手工編寫 equals 和hashCode 方法猬仁，IDE也提供了一些功能。