转载

Effective Java Item11 - 覆蓋equals時總要覆蓋hashCode

這篇是Effective Java - Always override hashcode when you override equals章節的讀書筆記本篇的程式碼來自於原書內容

Item11: 覆蓋equals時總要覆蓋hashCode

tldr 這是規定

Object的規範及約定

1.只要物件的equals方法的比較操作所用到的信息沒被修改那麼對一個對象調用多次hashCode 要始終如一的返回同一個整數

2.如果兩個對象根據equals的比較是相等的那麼對這兩個對象呼叫hashCode的整數也要相等

3.反之則否如果對兩個對象呼叫hashCode的整數相等並不要求兩個對象根據equals的比較要相等但相等的話 hash table的性能會比較好

沒有複寫hashCode的話很可能會違反第二點

PhoneNumber

public final class PhoneNumber {
  private final short areaCode;
  private final short prefix;
  private final short lineNumber;

  public PhoneNumber(int areaCode, int prefix, int lineNumber) {
    this.areaCode = (short) areaCode;
    this.prefix = (short) prefix;
    this.lineNumber = (short) lineNumber;
  }
  @Override
  public boolean equals(Object o) {
    if (o == this)
      return true;
    if (!(o instanceof PhoneNumber))
      return false;
    PhoneNumber pn = (PhoneNumber) o;
    return pn.lineNumber == lineNumber && pn.prefix == prefix
        && pn.areaCode == areaCode;
  }
}

現在用個hashmap來記一下電話

Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny");
System.out.println(m.get(new PhoneNumber(707, 867, 5309)));//return null

很抱歉 HashMap使用hashCode來計算一個物件的hash值而如果你沒有複寫的話兩個不同的物件回傳的值就會不一樣(對大部分的JVM來說預設的hashCode是用記憶體位置來計算) 即使這兩個的物件裡的每一個域的值都一樣

hash collision

那雖然說要複寫但也不要說就直接寫死

@Override
public int hashCode(){return 42;}

雖然合法是合法但是每次hashmap要計算hash值的時候都會跑到同一個bucket

一個Map硬生生比你拉成linked-list O(1)的操作全部變成O(n)

所以你要為你的類別寫一個好的hash function 讓不同的的物件返回不同的hash值(且越平均的分配越好)

設計hash

那麼要如何設計hash呢作者給了一個通用的公式:

1.給一個非0的常數比如說17 存進result變量

2.對於每個equals用到的變數f 計算c:

2-1.如果f是primitive type, c = Type.hashCode(f) Type就是f的boxed primitive type

比如說f是整數 c = Integer.hashCode(f)

2-2.如果f是對象引用 recursively呼叫這個物件的hashCode()

2-3.如果是個Array 那就對每一個元素做一樣的處理

算完c之後 result = 31*result + c

3.result就是hash值

4.確認是否相同的實例會有相同的hash值

來看看電話號碼的例子我們只要加上hashCode

@Override public int hashCode() {
  int result = 17;
  result = 31 * result + Short.hashCode(areaCode);
  result = 31 * result + Short.hashCode(prefix);
  result = 31 * result + Short.hashCode(lineNumber);
  return result;
}

剛剛的程式就會正確地返回Jenny

為什麼乘數選31 應該不難理解選奇數比選偶數好如果選的是偶數則hash的結果則不夠平均分佈經驗法則是選質數最好那選31的理由是因為31是個對於電腦來說很好記算乘法的質數

31 * i == (i « 5) - i

如果不在乎performance

那你就還有另一個選項

@Override public int hashCode() {
  return Objects.hash(areaCode, prefix, lineNumber)
}

就把所有你有的東西丟進去他就會幫你算了但是這個函式的性能很低要小心使用

不可變類

如果類別是不可變類那你可以在第一次hashCode被呼叫的時候把hash值算好時存在一個變數裡這樣以後就不用重新再算這是lazy initialize

private int hashCode;

  @Override public int hashCode() {
    int result = hashCode;
    if (result == 0) {
      result = 17;
      result = 31 * result + Long.hashCode(areaCode);
      result = 31 * result + prefix;
      result = 31 * result + lineNumber;
      hashCode = result;
  }
  return result;
}

注意如果執行環境不是thread-safe 則hashCode需要加上volatile

最後兩點

1.不用為了性能而忽略一個對象的關鍵域(significant field)的計算: 雖然這看起來是省下了計算的時間但之後處理hash碰撞的時間會加倍奉還給你

2.不要在你的spec中跟你的client保證hashCode的實作方式: 當你的客戶依賴著你的實作你之後就很難再修改你的程式

結論

你每次複寫equals 都必須要複寫hashCode 這個hashCode不但要遵守規範而且hash值散佈的越平均越好

原文 https://jyt0532.github.io/2018/06/23/always-override-hashcode-when-you-override-equals/

正文到此结束

所属分类：编程技术 Java

本文标签： client final JVM https volatile equals git list HashMap tab CEO id java GitHub IO IDE ORM map http
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二