HashCode規(guī)范
一個很常見的錯誤根源在于沒有覆蓋hashCode方法它褪。在每個覆蓋了equals方法的類中，也必須覆蓋hashCode方法凡桥。如果不這樣的話户辞，就會違反Object.hashCode的通用約定，從而導(dǎo)致該類無法結(jié)合所有基于散列的集合一起愉快的正常運作卧抗，這樣的集合包括HashMap藤滥，HashSet以及Hashtable。
下面是約定的內(nèi)容颗味，Object規(guī)范[JavaSE6]：
1.在應(yīng)用程序的執(zhí)行期間，只要對象的equals方法的比較操作所用的信息沒有被修改牺弹，那么對這個對象調(diào)用多次浦马，hashCode方法都必須始終如一地返回同一個整數(shù)时呀。在同一個應(yīng)用程序的多次執(zhí)行過程中，每次執(zhí)行所返回的整數(shù)可以不一致晶默。
2.如果兩個對象根據(jù)equals(Object)方法比較結(jié)果相等的谨娜，那么調(diào)用這兩個對象中任意一個對象的hashCode方法都必須產(chǎn)生同樣的整數(shù)結(jié)果。
3.如果兩個對象根據(jù)equals(Object)方法比較是不相等的磺陡，那么調(diào)用這兩個對象中任意一個對象的hashCode方法不一定要產(chǎn)生不一樣的整數(shù)結(jié)果趴梢。但是我們應(yīng)該知道，給不相等的對象產(chǎn)生不相同的整數(shù)結(jié)果币他，可以提高散列表(hashtable)的性能坞靶。
未覆蓋hashCode()方法的后果
因為沒有覆蓋hashCode而違反的關(guān)鍵約定是第二條：相等的對象必須具有相等的散列碼(hash code)。
根據(jù)類的equals方法蝴悉，兩個截然不同的實例在邏輯上有可能是相等的彰阴，但是根據(jù)Object類的hashCode方法，它們僅僅是兩個沒有任何共同之處的對象拍冠。因此尿这，對象的hashCode方法返回兩個看起來是隨機(jī)的整數(shù)，而不是根據(jù)第二個約定那樣庆杜，返回兩個相等的整數(shù)射众。
例如下面這個例子：
public final 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, "lineNumber");
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);
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (!(o instanceof PhoneNumber))
return false;
PhoneNumber pn = (PhoneNumber) o;
return pn.lineNumber == lineNumber
&& pn.prefix == prefix
&& pn.areaCode == areaCode;
}
}
如果和HashMap一起使用，則會出現(xiàn)問題晃财。
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)));
輸出結(jié)果為：
null
由于PhoneNumber類中沒有重寫hashCode方法叨橱，即使兩個PhoneNumber實例是相等的(通過equals()方法比較相等)，但是兩個相等的類不具有相同的散列碼拓劝，違反了hashCode的約定雏逾。因此，put方法把電話號碼對象存放在一個散列桶(hash bucket)中郑临，get方法卻在另外一個散列桶里面查找栖博。即使這兩個實例正好被放到了同一個散列桶里面，get方法也一定會返回null厢洞，因為HashMap做了一項優(yōu)化仇让，將每個項相關(guān)聯(lián)的散列碼存放起來，如果hash碼不匹配躺翻，則不會去檢驗對象的等同性丧叽，充分利用了邏輯與運算的惰性(&&)。
如何覆蓋hashCode()方法
修正這個問題也非常的簡單公你，只需要為PhoneNumber類提供了一個適當(dāng)?shù)膆ashCode方法即可踊淳。編寫一個合法但是并不好用的hashCode方法并沒有任何的價值，例如下面的這個hashCode()方法：
@Override
public int hashCode() { return 42;}
上面這個方法雖然是合法的，因為它確保了相等的對象總是具有同樣的散列碼迂尝。但是對于每個實例對象的散列碼是相同的= =脱茉。因此，每個對象都被映射到了同一個散列桶中垄开，散列表退化成鏈表琴许。使得本該以線性時間運行的程序似乎變成了以方級時間在運行。
一個好的散列函數(shù)通常傾向于“為不相等的對象產(chǎn)生不相等的散列碼”溉躲。這正是hashCode約定中的第三條含義榜田。在理想的情況下，散列函數(shù)應(yīng)該把集合中不相等的實例均勻的分不到所有可能的散列值上锻梳。要想達(dá)到理想的情況是非常困難的箭券，幸運的是相對接近理想情況并不太困難，例如下面的這種解決方法：
把某個非零的常數(shù)值唱蒸，比如說17邦鲫，保存到一個名為result的int類型變量中。
對于對象中每個關(guān)鍵域f (指equals方法中涉及的每個域)神汹，完下面的步驟：
a. 為該域計算int類型的散列碼c:
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)撬统，然后按照步驟2.a.iii适滓，為得到long類型值計算散列值。
vi. 如果該域是一個對象引用恋追，并且該類的equals方法通過遞歸地調(diào)用equals的方式來比較這個域凭迹，則同樣為這個域遞歸地調(diào)用hashCode。如果需要更復(fù)雜的比較苦囱，則為這個域計算一個范式(canonical representation)嗅绸，然后針對這個范式調(diào)用hashCode。如果這個域為null,則返回0撕彤。
vii. 如果該域是一個數(shù)組鱼鸠，則要把每個元素當(dāng)作單獨的域來處理。
b. 按照下面的公式，將2.a計算得到的散列碼c合并到result中：
result = 31 * result + c;
3.返回result蚀狰。
4.寫完了之后漆弄，檢查是否符合上述的三條規(guī)定。
在散列碼的計算過程中造锅，可以把冗余域(redundant field)排除在外。換句話說廉邑，如果一個域的值可以根據(jù)參與計算的其他域計算出來哥蔚，則可以把這樣的域排除在外。必須排除equals比較計算中沒有用到的域蛛蒙，否則很有可能違反hashCode約定中的第二條了糙箍。
在計算過程中選擇31的原因，是因為31有個很好的性能牵祟，現(xiàn)代的JVM可以自動的優(yōu)化計算過程深夯，將31 * i優(yōu)化成為(i << 5) - i。用位運算和減法替代了乘法诺苹。
下面開始為PhoneNumber類編寫hashCode()方法咕晋。其中有三個關(guān)鍵域，都是short類型的收奔，根據(jù)上面的規(guī)則2.a.ii,則hashCode代碼如下：
@Override
public int hashCode() {
int result = 17;
result = 31 * result + areaCode;
result = 31 * result + prefix;
result = 31 * result + lineNumber;
return result;
}
如果一個類是不可變的掌呜，并且計算散列碼的開銷比較大，就應(yīng)該考慮把散列碼緩存在對象內(nèi)部坪哄，而不是每次請求的時候都重新計算散列碼质蕉。如果你就得這種類型的大多數(shù)對象會被用作散列鍵，就應(yīng)該在創(chuàng)建實例的時候計算散列碼翩肌。否則模暗，可以選擇“延遲初始化”散列碼，一直到hashCode被第一次調(diào)用的時候才初始化念祭。
//Lzzily initialized, cached hashCode
private volatile int hashCode;
@Override public int hashCode(){
int result = hashCode;
if(result == 0){
int result = 17;
result = 31 * result + areaCode;
result = 31 * result + prefix;
result = 31 * result + lineNumber;
}
return result;
}
