Effective Java 讀書筆記: Item 9 - 覆寫 equals 時, 一定要覆寫 hashCode

記錄讀書心得, 內容不一定和書上一致, 有些是我自己的看法。

覆寫 equals 卻沒覆寫 hashCode 的話, 使用 HashSet / HashMap / Hashtable 或任何用到 hashCode 的 class 就會出包: 使得兩個邏輯上相等的物件, 在 hash 的階段就被視作不同物件, 而無法找回來。

實作一個好的 hashCode 是一門學問, 作者列了很多注意事項, 看描述不如看 code, 引用 String 的 hashCode:

@Override
public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

value、offset、count 是 member field。不同 String 之間有共享 value, 用來避免在呼叫 substring 後增加重覆內容, 因此浪費記憶體。value[offset] ... value[offset + count -1] 是這個 String 實際用到的內容, 所以計算 hash code 時只看這些字元。

上面的程式有幾個重點

• result = 31 * result + c 的數學形式
• 選用質數當乘數較好 (如31), 別選 2 的倍數, 乘到溢位就都變零了
• 31 的另一好處是近代 JVM 會做最佳化, 31*h 會自動轉成 (h<<5) - h
• 用乘法可確保相同字元在不同順序的情況下, 會有不同的 hash code

其它相關要點

• 各種 primitive type 都有轉為 int 的方式, 像 long n 可用 (int)(n ^ (n>>>32))、float f 可用 Float.floatToIntBits(f)
• 寫 unit test 確保邏輯上相同的物件有相同的 hash code
• hashCode 計算量太大的話, 可考慮用 lazy evaluation + cache
• 別為了省計算時間而簡化產生 hash code 的方法, 這會反映在 hash table 的 collision 上, 資料量大時可能更不划算