碼處高效：覆蓋 equals() 時切記要覆蓋 hashCode()
- 2019 年 10 月 5 日
- 筆記
在每個覆蓋了 equals 方法的類中，都必須覆蓋 hashCode 方法。如果不這樣做的話，就會違反 hashCode 的通用約定，從而導致該類無法結合所有的給予散列的集合一起正常運作。這類集合包括 HashSet、HashMap，下面是Object 的通用規範：
- 在應用程式的執行期間，只要對象的 equals 方法的比較操作所用到的資訊沒有被修改，那麼同一個對象的多次調用，hashCode 方法都必須返回同一個值。在一個應用程式和另一個應用程式的執行過程中，執行 hashCode 方法返回的值可以不相同。
- 如果兩個對象根據 equals 方法比較出來是相等的，那麼調用這兩個對象的 hashCode 方法都必須產生同樣的整數結果
- 如果兩個對象根據 equals 方法比較是不相等的，那麼調用這兩個對象的 hashCode 方法不一定要求其產生相同的結果，但是程式設計師應該知道，給不相等的對象產生截然不同的整數結果，有可能提高散列表的性能。
因沒有覆蓋 hashCode ,容易違反上面第二條的約定，即相等的對象必須擁有相同的 hashCode 散列值
根據類的 equals 方法，兩個截然不同的實例在邏輯上有可能是相等的。但是根據 Object 的 hashCode 方法來看，它們僅僅是兩個截然不同的對象而已。因此對象的 hashCode 方法返回兩個看起來是隨機的整數，而不是根據第二個約定所要求的那樣，返回兩個相等的整數。
例如下面這個例子:
public class PhoneNumber { int numbersOne; int numbersTwo; int numbersThree; public PhoneNumber(int numbersOne, int numbersTwo, int numbersThree) { this.numbersOne = numbersOne; this.numbersTwo = numbersTwo; this.numbersThree = numbersThree; } @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof PhoneNumber)) return false; PhoneNumber that = (PhoneNumber) o; return Objects.equals(numbersOne, that.numbersOne) && Objects.equals(numbersTwo, that.numbersTwo) && Objects.equals(numbersThree, that.numbersThree); } public static void main(String[] args) { Map numberMap = new HashMap(); numberMap.put(new PhoneNumber(707,867,5309),"Jenny"); System.out.println(numberMap.get(new PhoneNumber(707,867,5309))); } }
此時，你可能希望 numberMap.get(new PhoneNumber(707,867,5309)) 會返回 "Jerry"，但它實際上返回的是null 。這裡會涉及到兩個實例：第一個實例是第一次添加進入的 PhoneNumber , 它會被添加到一個桶中。因為沒有重寫 hashCode 方法，所以你取的時候是去另外一個桶中取出來的 PhoneNumber 實例。所以自然兩個實例不相等，因為 HashMap 有一項優化，可以將與每個項相關聯的散列碼快取起來，如果散列碼不匹配，也就不再去檢驗對象的等同性。
修正這個問題非常的簡單，只要提供一個相等的散列碼就可以了
@Override public int hashCode() { return 42; }
上面這個 hashCode 方法是合法的。因為它確保了相等的對象總是具有同樣的散列碼。但是它也極為惡劣，因為每個對象都具有相同的散列碼。因此，多個具有相同散列碼的 HashMap 就會彼此連在一起形成鏈表。它使得本該以線性時間運行的程式變成了以平方級的時間運行。
一個好的散列通常是 "為不相等的對象產生不相等的散列碼"。這正是 hashCode 約定中的第三條含義。理想情況下，散列函數應該把集合中不相等的實例均勻地分布到所有可能的 int 值上。下面是一種簡單的解決辦法：
- 聲明一個 int 變數並命名為 result，將它初始化為對象中的第一個關鍵域散列碼 c.
- 對象中剩下的每一個關鍵域 f 都完成以下步驟： 為該域計算 int 類型的散列碼 c： 按照 下面的公式，把散列碼 c 合併到 result 中。 result = 31 * result + c;
1）如果該域是基本類型，則計算 Type.hashCode(f)，這裡的 Type 是集裝箱基本類型的類，與 f 的類型相對應
2）如果該域是一個對象引用，並且該類的 equals 方法通過遞歸地調用 equals 的方式來比較這個域，則同樣為這個域遞歸地調用 hashCode 。如果為null ，則返回0
3）如果該域是一個數組，則要把每一個元素當作單獨的域來處理。也就是說，遞歸地應用上述規則，對每個重要的元素計算一個散列碼，然後根據步驟2 . b中的做法把這些散列值組合起來。如果數組域中沒有重要的元素，可以使用一個常量，但最好不要用0。如果數組域中的所有元素都很重要，可以使用 Arrays.hashCode 方法。
- 返回result
寫完了之後，還要進行驗證，相等的實例是否具有相同的散列碼，可以把上述解決辦法用到 PhoneNumber 中
@Override public int hashCode() { int result = Integer.hashCode(numbersOne); result = 31 * result + Integer.hashCode(numbersTwo); result = 31 * result + Integer.hashCode(numbersThree); return result; }
雖然上述給出了 hashCode 實現，但它不是最先進的。它們的品質堪比 Java 平台類庫提供的散列函數。這些方法對於大多數應用程式而言已經足夠了。
Objects 類有一個靜態方法，它帶有任意數量的對象，並為它們返回一個散列碼。這個方法名為 hash 。你只需要一行程式碼就可以編寫它的 hashCode 方法。它們的品質也是很高的，但是，它的運行速度相對慢一些，因為它們會引發數組的創建，以便傳入數目可變的參數，如果參數中有基本類型，還需要裝箱和拆箱。例如：
@Override public int hashCode(){ return Objects.hash(numbersOne,numbersTwo,numbersThree); }
如果一個類是不可變的，並且計算 hashCode 的開銷也大，那麼應該把它快取在對象內部，而不是每次請求都重新創建 hashCode。你可以選擇 "延遲初始化" 的散列碼。即一直到 hashCode 被第一次使用的時候進行初始化。如下：
private int hashCode; @Override public int hashCode() { int result = hashCode; if(result == 0){ result = Integer.hashCode(numbersOne); result = 31 * result + Integer.hashCode(numbersTwo); result = 31 * result + Integer.hashCode(numbersThree); hashCode = result; } return result; }
當你要重寫對象的 hashCode 方法時，下面這兩個約定我希望你能遵守：
- 不要對 hashCode 方法的返回值做具體的規定，因此客戶端無法理所當然地依賴它；這樣可以為修改提供靈活性。
- 不要試圖從散列碼計算中排除掉一個對象的關鍵域來提高性能。
總而言之，每當覆蓋 equals 方法時都必須覆蓋 hashCode。否則程式將無法正確運行。hashCode 方法必須遵守 Object 規定的通用約定，並且一起完成一定的工作。將不相等的散列碼分配給不相等的實例。這個很容易實現，但是如果不想那麼費力，可以直接使用 eclipse 或者 Idea 提供的 AutoValue 自動生成就可以了。
