2014-11-09

Effective Java - 覆寫 equals() 時，總是一併覆寫 hashCode()


"覆寫 equals() 時，總是一併覆寫 hashCode()"

無論何時，對同一個物件 (Object) 呼叫 hashCode() 都應該生成同樣的值。












一、Hash code用途：
  1. 任何兩物件 hash code 不相同，則這兩個物件必定不同。(但，不同物件仍可能產生相同 hash code)。
  2. 運用在雜湊集合 (HashMap, HashTable, HashSet...etc) 中來判斷是不是有該物件，集合中不允許相同物件的存在。
    ※ 可參考 HashMap.put(K key, V value) 和 HashMap.get(K key):Object 的實作

二、equals() 用途：
  1. 判斷兩物件是否相同。
  2. 若為 true 兩物件 hash code 值必定相同；為 false 兩物件值不一定不同。
  3. Object 預設的行為是比較兩個物件的記憶體位址。

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

三、Java.lang.Integer 為例：
java.lang.Integer 物件, 改寫了 equals() 和 hashCode() 方法，如下：

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

public int hashCode() {
        return value;
}

public static void main(String[] args) {
    Integer i = 10;
    HashMap<Integer, String> map = new HashMap<Integer, String<>();
    map.put(i, "10");

    System.out.println(map.get(new Integer(10)));
}


---------------------------------------------------------------------------------------------
輸出結果：
10

結論：
HashMap.get(K key):Object 的實作上，會先找取得 key 的 hashcode (key.hashCode()) 來計算出對映於 hash table 真正的 key，找到物件後，再將兩個物件作 equals() 比較。
所以就算是這行這麼寫：

    System.out.println(map.get(new Integer(10)));

經過 override equals() 和 hashCode() 後仍然能取得 "10" 的值。

----------------------------------------------------------------------------------------------

四、寫一個 FakeInteger 來測試看看：
接著，我們做一個對照組，建立一個 FakeInteger 物件，這個物件的作用與 Integer 相同，同樣以這個物件當作 HashMap 的 Key ，一開始我們只覆寫了 equals() 這個方法。
程式如下：

class FakeInteger {
    private int value;

    public FakeInteger(int i) {
       this.value = i;
    }
    
    public int getValue() {
        return value;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof FakeInteger) {
            return value == ((FakeInteger) obj).getValue();
        }
        return false;
   }
}

public static void main(String[] args) {
    FakeInteger i = new FakeInteger(10);
    HashMap<FakeInteger, String> map = new HashMap<FakeInteger, String<>();
    map.put(i, "10");

    System.out.println(map.get(new FakeInteger(10)));
}

---------------------------------------------------------------------------------------------
輸出結果：
null

結論：
依照上面的結論來看，兩個物件有不同的 hash code，當然在 hash table 裡找不到。

----------------------------------------------------------------------------------------------

因此，我們再覆寫 hashCode() 這個方法，然後測測看：

class FakeInteger {
    private int value;

    public FakeInteger(int i) {
       this.value = i;
    }
    
    public int getValue() {
        return value;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof FakeInteger) {
            return value == ((FakeInteger) obj).getValue();
        }
        return false;
   }

    @Override
   public int hashCode() {
        return FakeInteger.class.getName().hashCode() + value;
   }
}

public static void main(String[] args) {
    FakeInteger i = new FakeInteger(10);
    HashMap<FakeInteger, String> map = new HashMap<FakeInteger, String<>();
    map.put(i, "10");

    System.out.println(map.get(new FakeInteger(10)));
}

---------------------------------------------------------------------------------------------
輸出結果：
10

結論：
所以，如果想要讓物件成為雜湊資料結構的 Key，那麼在覆寫 equals() 的同時，就應該要覆寫 hashCode()，這樣才能夠達成你想要的結果。
----------------------------------------------------------------------------------------------



五、覆寫 hashCode() 方法應注意
  1. 一個好的雜湊函數通常是，為不相同的物件產出不相等的 hash code。
  2. 一個雜湊函式應該把在一個集合中所有不相等的實例，盡可能均勻分佈至所有可能的雜湊值。
  3. 底下是一個簡單的步驟，用來達成以上兩點：
    • 將一個非 0 的整數儲存到一個變數 result，我們隨機一個 17 整數
    • 對於每個物件的 significant field f 做以下的計算：
      • 若 field 是 boolean，則計算 (f ? 1 : 0)
      • 若 field 是 byte, char, short, int，則計算 (int) f
      • 若 field 是 long，則計算 (int) ( f ^ ( f  >>> 32))
      • 若 field 是 float，則計算 Float.floatToIntBits(f)
      • 若 field 是 double，則計算 Double.doubleToLongBits(f)，然後再計算 (int) ( f ^ ( f >>> 32))
      • 若 field 是 instance，透過遞迴呼叫 class 的 equals() 與 field 比較，那麼 field 的 hashCode 就會被遞迴呼叫到。若需要更複雜的計算，那麼就為該 field 計算出 canonical representation，並呼叫 canonical representation 的 hashCode。若 field 的值是 null，就返回 0 。
      • 若 field 是 array，則計算
    • 組合計算的結果：result = 37 * result + c
    • 返回 result
  4. 如果一個類別是不可變的，計算 hash code 的成本又很高，那麼可以考慮將 hash code 暫存起來，而不是每次請求都重新計算。
  5. 如果物件被建立後，很容易被變成 hash key，那麼物件被建立的時候就應該計算出它的 hash code，否則延遲計算它 (第一次被呼叫時)。
  6. 不要在計算 hash code 時，排除物件關鍵的部分，以提高計算的效能，這樣反而會導致 hash table 不可用。


六、 總結
當類別 需要放在 HashTable、HashMap、HashSet 等等，雜湊結構的集合時才需要覆寫 hashCode()，Hash 集合利用 hash table 來查找對應於 Object Key 的資料，所以會先利用 hash code 來查找 hash table 真正的 key，然後再透過這個 key 找出資料。

所以，當 equal 相等時，hashCode 必須相等，而且如果是 Object 就必須覆寫 hashCode() 和equal() 方法。

一般來說，不管什麼情況下，只要覆寫 equals() 就覆寫 hashCode() 這樣可以省去往後當需要這個物件當 hash key 時的麻煩。

注意第五點，這樣可以讓你在撰寫 hashCode() 方法時，有一個遵循的依歸。



張貼者： 於

沒有留言 :

張貼留言

訂閱： 張貼留言 ( Atom )