Effective Java筆記第二章對所有對象都通用的方法
第二節覆寫equals時總要覆寫hashCode
本文提到了volatile關鍵字,如果不是很清楚的話建議看一下這篇文章volatile關鍵字的作用,相信會對你有些許幫助。
1.在每個覆寫了equals方法的類中,也必須覆寫hashCode方法,如果不這樣做的話,就會違反Object.hashCode的通用約定,進而導緻該類無法結合所有基于散列的集合一起正常運作,這樣的集合包括HashMap,HashSet和Hashtable。
2.Object.hashCode的通用約定:
1)在應用程式的執行期間,隻要對象的equals方法的比較操作所用到的資訊沒有被修改,那麼對這同一個對象調用多次,hashCode方法必須始終如一的傳回同一個整數。在同一個應用程式的多次執行過程中,每次執行所傳回的整數可以不一緻。
2)如果兩個對象根據equals(Object)方法比較是相等的,那麼調用這兩個對象中任意一個對象的hashCode方法都必須産生同樣的整數結果。
3)如果兩個對象根據equals(Object)方法比較是不等的,那麼調用這兩個對象中任意一個對象的hashCode方法不一定要産生不同的整數結果。但是給不相等的對象産生截然不同的整數結果,有可能提高散清單的性能。
因沒有覆寫hashCode而違反的關鍵約定是第二條:相等對象必須具有相同的散列碼。根據類的equals方法,兩個截然不同的執行個體在邏輯上可能是相等的,但是根據Object類的hashCode方法,他們僅僅是兩個沒有任何共同之處的對象,是以會傳回兩個看起來是随機的整數。
下面我們舉個例子:
public class PhoneNumber {
private final short areaCode;
private final short prefix;
private final short lineNumber;
public PhoneNumber(int areaCode, int prefix, int lineNumber) {
rangeCheck(areaCode, 999, "area code");
rangeCheck(prefix, 999, "prefix");
rangeCheck(lineNumber, 9999, "line Number");
this.areaCode = (short) areaCode;
this.prefix = (short) prefix;
this.lineNumber = (short) lineNumber;
}
//設定數字的範圍
private static void rangeCheck(int arg, int max, String name) {
if (arg < 0 || arg > max) {
throw new IllegalArgumentException(name + ": " + arg);
}
}
//覆寫equals方法
@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.areaCode == areaCode && pn.prefix == prefix;
}
public static void main(String[] args) {
Map<PhoneNumber,String> map=new HashMap<>();
PhoneNumber pn1 = new PhoneNumber(707, 867, 5309);
System.out.println(pn1.hashCode());
PhoneNumber pn2 = new PhoneNumber(707, 867, 5309);
System.out.println(pn2.hashCode());
map.put(pn1,"Jenny");
String name = map.get(pn2);
System.out.println(name);
}
}
輸出:
1956725890
356573597
null
我們希望傳回的"Jenny",但是傳回了null。這裡我們有兩個PhoneNumber 執行個體,第一個被插入到了HashMap中,第二個執行個體和第一個相等,被用來擷取HashMap中的值。由于PhoneNumber 類沒有覆寫hashCode方法,進而導緻兩個相等的執行個體具有不相等的散列碼,違反了hashCode約定。是以,put方法把PhoneNumber 對象存放在了一個散列桶中,get方法卻在另一個散列桶中查找這個PhoneNumber 。即使這兩個執行個體正好被放在一個散列桶中,get方法也必定會傳回null,因為HashMap有一項優化,可以将每個項相關聯的散列碼緩存起來,如果散列碼不比對,也不必檢驗對象的等同性。
3.一個好的散列函數通常傾向于"為不相等的對象産生不相等的散列碼"。理想情況下,散列函數應該把集合中不相等的執行個體均勻的分布到所有可能的散列值上。要達到理想狀态非常困難,但是接近理想情形并不太困難,下面給出一種簡單的解決方法:
1)把某個非零的常數值(最好是素數,也就是質數,隻能被1和本身整除),比如說17,儲存在一個 名為result的int類型的變量中。
2)對于對象中每個關鍵域(指equals方法中涉及的每個域),完成以下步驟:
a)為該域計算int類型的散列碼:
i)如果該域是boolean類型,則計算(f?1:0)。
ii)如果該域是byte,char,short或者int類型,則計算(int)f。
iii)如果該域是long類型,則計算(int)(f^(f>>>32))。
iv)如果該域是float類型,則計算Float.floatToIntBits(f)。
v)如果該域是double類型,則計算Double.doubleToLongBits(f),然後再按照long類型來計算散列值。
vi)如果該域是一個對象引用,并且該類的equals方法通過遞歸的調用equals方式來比較這個域,則同樣為這個域遞歸的調用hashCode。如果需要更複雜的比較,則為這個域計算一個"範式",然後針對這個範式調用hashCode。如果這個域的值為null,則傳回0。
vii)如果該域是一個數組,則要把每一個元素當做單獨的域來處理。也就是說,遞歸的應用上述規則,對每個重要的元素計算一個散列碼,然後根據步驟2.b中的做法把這些散列值組合起來,如果數組域中的每個元素都很重要,可以利用發行版本1.5中增加的其中一個Arrays.hashCode方法。
b)按照下面的公式,把步驟2.a中計算得到的散列碼c合并到result中:
result = 31*result + c ;
3)傳回result。
下面我們示範一下:
public class Person {
public boolean Aboolean;
public short Ashort;
public long Along;
public float Afloat;
public double Adouble;
public Man Aman;
public int[] ints;
public Person(boolean aboolean, short ashort, long along, float afloat, double adouble, Man aman, int[] ints) {
Aboolean = aboolean;
Ashort = ashort;
Along = along;
Afloat = afloat;
Adouble = adouble;
Aman = aman;
this.ints = ints;
}
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Person)) {
return false;
}
Person p = (Person) o;
return p.Aboolean == Aboolean &&
p.Ashort == Ashort &&
p.Along == Along &&
p.Afloat == Afloat &&
p.Adouble == Adouble &&
//調用對象類的equals方法比較
p.Aman.equals(Aman) &&
p.ints == ints;
}
@Override
public int hashCode() {
int result = 17;
result = 31 * result + (Aboolean ? 1 : 0);
result = 31 * result + Ashort;
result = 31 * result + (int) (Along ^ (Along >>> 32));
result = 31 * result + Float.floatToIntBits(Along);
result = 31 * result + Float.floatToIntBits(Double.doubleToLongBits(Adouble));
//調用對象類的hashCode
int i = Aman.hashCode();
result = 31 * result + i;
//數組的hashCode判斷
for (int anInt : ints) {
result=31*result+anInt;
}
return result;
}
public static void main(String[] args) {
short s = 11;
Man man = new Man(11);
int[] ints = {1, 2,3};
Person p = new Person(true, s, 22L, 22.2f, 22.1, man, ints);
System.out.println(p.hashCode());
}
}
class Man {
public int Aint;
public Man(int aint) {
Aint = aint;
}
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Man)) {
return false;
}
Man man = (Man) o;
return man.Aint == Aint;
}
@Override
public int hashCode() {
int result = 17;
result = 31 * result + Aint;
return result;
}
}
在散列碼的計算過程中,可以把備援域排除在外,也就是說如果一個域的值可以根據參與計算的其他域值計算出來,則可以把這樣的域排除在外,必須排除equals比較計算中沒有用到的任何域,否則很可能違反hashCode約定的第二條。
步驟2.b中的乘法部分使得散列值依賴于域的順序,如果一個類包含多個相似的域,這樣的乘法運算就會産生一個更好的散列函數。加入String散列函數省略了這個乘法部分,那麼隻是字母順序不同的所有字元串都會有相同的散列碼。之是以選擇31,因為他是一個奇素數,我們習慣上使用素數來計算散列結果。如果乘數是偶數,并且乘法溢出,資訊就會丢失,因為與2相乘等價于移位運算。31有個很好的特性,即用移位和減法來代替乘法,可以得到更好的性能:31*i==(i<<5)-i。現代的VM可以自動完成這種優化。
4.現在再看2的問題就簡單很多了,PhoneNumber 有三個關鍵域,都是short類型,我們可以這樣寫:
@Override
public int hashCode() {
int result=17;
result=31*result+areaCode;
result=31*result+prefix;
result=31*result+lineNumber;
return result;
}
如果一個類是不可變的,并且計算散列嗎開銷也比較大,就應該考慮把散列碼緩存在對象内部,而不是每次請求的時候都重新計算散列碼。如果你覺得這種類型的大多數對象會被用作散列鍵,就應該在建立執行個體的時候計算散列碼。否則,可以選擇"延遲初始化"散列碼,一直到hashCode被第一次調用的時候才初始化。
也就是說可以用下面這種寫法:
public class Demo {
private final short areaCode;
private final short prefix;
private final short lineNumber;
private volatile int hashCode;
public Demo(int areaCode, int prefix, int lineNumber, int hashCode) {
rangeCheck(areaCode, 999, "area code");
rangeCheck(prefix, 999, "prefix");
rangeCheck(lineNumber, 9999, "line Number");
this.areaCode = (short) areaCode;
this.prefix = (short) prefix;
this.lineNumber = (short) lineNumber;
this.hashCode = hashCode;
}
//設定數字的範圍
private static void rangeCheck(int arg, int max, String name) {
if (arg < 0 || arg > max) {
throw new IllegalArgumentException(name + ": " + arg);
}
}
//覆寫equals方法
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Demo)) {
return false;
}
Demo pn = (Demo) o;
return pn.lineNumber == lineNumber && pn.areaCode == areaCode && pn.prefix == prefix;
}
@Override
public int hashCode() {
int result = hashCode;
if (result == 0) {
result = 17;
result = 31 * result + areaCode;
result = 31 * result + prefix;
result = 31 * result + lineNumber;
hashCode = result;
}
return result;
}
public static void main(String[] args) {
Map<Demo, String> map = new HashMap<>();
Demo pn1 = new Demo(707, 867, 5309, 0);
System.out.println(pn1.hashCode);
System.out.println(pn1.hashCode());
System.out.println(pn1.hashCode);
Demo pn2 = new Demo(707, 867, 5309, 0);
System.out.println(pn2.hashCode());
map.put(pn1, "Jenny");
String name = map.get(pn2);
System.out.println(name);
}
}
輸出為:
1218060
1218060
1218060
Jenny
5.注意:不要試圖從散列碼計算中排除掉一個對象的關鍵部分來提高性能,雖然這樣得到的散列函數運作可能更快,但是可能會導緻散清單慢到根本無法使用。