重寫(xiě)equals方法時(shí)一定要重寫(xiě)hashCode方法.
"重寫(xiě)equals方法時(shí)為啥要重寫(xiě)hashCode方法?"這個(gè)可能是面試出場(chǎng)率最高的問(wèn)題了, 沒(méi)有之一. 不重寫(xiě)hashCode方法會(huì)導(dǎo)致所有使用hash值的集合類(lèi)處理異常, 比如HashMap和HashSet. 原理很好理解, 以HashMap為例, 在get和put時(shí), 會(huì)認(rèn)為equals和hash值都相等的元素才是同一個(gè)元素.
Object中提供的hashCode方法是一個(gè)native方法, 它的底層實(shí)現(xiàn)邏輯是將對(duì)象內(nèi)存地址轉(zhuǎn)換為整數(shù)返回, 所以可以保證同一個(gè)對(duì)象的hashCode返回是一致的.
下面java規(guī)范中關(guān)于hashCode的部分
- 一致性, 對(duì)于一個(gè)對(duì)象, 當(dāng)equals方法使用的比較屬性沒(méi)有變化時(shí), hashCode多次執(zhí)行結(jié)果是一樣的.
- 如果兩個(gè)對(duì)象的equals方法判斷相等, 那么這兩個(gè)對(duì)象的hashCode方法返回值也必須相等.
- equals判斷不相等的兩個(gè)對(duì)象, 不要求這兩個(gè)對(duì)象的hashCode返回結(jié)果一定不一樣, 但是如果不一樣的話會(huì)提供系統(tǒng)性能.
作者給出了實(shí)現(xiàn)hashCode的方法
- 定義一個(gè)整數(shù)result = 17.
- 將每一個(gè)會(huì)影響equals方法的屬性轉(zhuǎn)換為一個(gè)整數(shù).
- 將每一個(gè)屬性的整數(shù)結(jié)果通過(guò)下面的公式累加到result
result = result * 31 + c // c是屬性的整數(shù)值.
在第二步中作者給出了每一個(gè)類(lèi)型轉(zhuǎn)換為整數(shù)的方式, 如下(f表示屬性):
- boolean: 返回 f ? 1 : 0;
- byte, char, short, int: 返回(int) f;
- long: (int)(f ^ (f >>> 32));
- float: Float.floatToIntBits(f);
- double: Double.doubleToLongBits(f), 得到long結(jié)果, 再按照l(shuí)ong類(lèi)型處理.
- 引用類(lèi)型: 使用其hashCode方法. 對(duì)于null返回0.
- 數(shù)組類(lèi)型: 對(duì)其中每一個(gè)元素按照上述規(guī)則求值, 或者使用Arrays.hashCode().
關(guān)于上面的規(guī)則, 有兩個(gè)問(wèn)題
- 這么多轉(zhuǎn)換規(guī)則, 我不可能記住.
- 上面17, 31為啥是17, 31?
問(wèn)題一:
剛看到這里的時(shí)候就懵了, 這么多都要記? 看到第四條Float.floatToIntBits(f)想到一點(diǎn), 不如看看它們的包裝類(lèi)型是怎么做的. 果然, 這些數(shù)字類(lèi)型的包裝類(lèi)型會(huì)實(shí)現(xiàn)一個(gè)靜態(tài)的hashCode方法, 入?yún)⑹菍?shí)際值, 實(shí)現(xiàn)內(nèi)容跟作者說(shuō)的基本一樣(jdk 1.8), 除了boolean, 作者說(shuō)的是1和0, jdk中是1231和1237. 所以對(duì)于數(shù)字類(lèi)型, 我們不需要再記憶這些, 直接使用對(duì)應(yīng)的靜態(tài)方法即可. 比如double類(lèi)型, 我們可以直接返回Double.hashCode(f), Double的hashCode如下:
@Override
public int hashCode() {
return Double.hashCode(value);
}
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
問(wèn)題二:
回憶下文章開(kāi)始的hashCode規(guī)范, 三條規(guī)則概括起來(lái)是兩條內(nèi)容: 一是hashCode返回要正確, 不會(huì)影響業(yè)務(wù); 二是好的hashCode會(huì)系統(tǒng)提高性能.
問(wèn)題二中的17和31就要從系統(tǒng)性能說(shuō)起. 那么hashCode的值為什么會(huì)影響系統(tǒng)性能? 舉個(gè)例子, 如果hashCode方法對(duì)于任何對(duì)象都返回1會(huì)怎么樣? 首先這樣是滿(mǎn)足規(guī)范要求, 不影響業(yè)務(wù)判斷. 但是當(dāng)我們把這樣的對(duì)象插入到hash表中時(shí)會(huì)發(fā)現(xiàn), 因?yàn)樗械膶?duì)象的hash值一樣, 所以都插入到了同一個(gè)槽中, 也就是說(shuō)hash表退化成了鏈表結(jié)構(gòu), 查詢(xún)性能從O(1)惡化為O(n).
為了讓hash表更平均需要hashCode返回值更合理, "更合理"意思就是"更少的hash沖突", 所以hashCode方法多使用17和31這樣的質(zhì)數(shù)來(lái)參加運(yùn)算, Boolean的hashCode方法中的1231和1237也是同樣道理.
那為什么質(zhì)數(shù)的hash沖突更少? 這個(gè)應(yīng)該有嚴(yán)格的數(shù)學(xué)推論, 簡(jiǎn)單來(lái)說(shuō), hash槽是通過(guò) hashCode % n (n為hash表大小) 確定的, 如果值為0表示可以被n整除, 那么所有可以被n整除的hashCode都會(huì)被分配到同一個(gè)槽中, 所以如果是質(zhì)數(shù)的話就不會(huì)出現(xiàn)整除情況(HashMap大小是2的n次方), 所以沖突的可能性更小(以上沒(méi)有數(shù)學(xué)證明, 只是感覺(jué)~).
