面試官問我：hashcode 是什么？和equals是兄弟嗎？
?
? ? 秋招的時(shí)候還記得面試官問過我hashcode是什么，對(duì)于int、long、string類型的hashcode有什么區(qū)別，和equals一起是怎么使用的，為什么重寫hashcode的同時(shí)也要重寫equals。
? ? ? 八股文背多了，也只是會(huì)表面，有空的時(shí)候還是整理一下，順便寫了幾個(gè)例子加深下印象。
hashcode 是什么？
hash 一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長(zhǎng)度的輸入，通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。hash 是一個(gè)函數(shù)，該函數(shù)中的實(shí)現(xiàn)就是一種算法，就是通過一系列的算法來(lái)得到一個(gè) hash 值。每個(gè)對(duì)象都有 hashcode，對(duì)象的 hashcode 怎么得來(lái)的呢？
首先一個(gè)對(duì)象肯定有物理地址，對(duì)象的物理地址跟這個(gè) hashcode 地址不一樣，hashcode 代表對(duì)象的地址說的是對(duì)象在 hash 表中的位置，通過對(duì)象的內(nèi)部地址(也就是物理地址)轉(zhuǎn)換成一個(gè)整數(shù)，然后該整數(shù)通過 hash 函數(shù)的算法就得到了 hashcode。所以，hashcode 就是在 hash 表中對(duì)應(yīng)的位置。
所有散列函數(shù)都有如下一個(gè)基本特性：根據(jù)同一散列函數(shù)計(jì)算出的散列值如果不同，那么輸入值肯定也不同。但是，根據(jù)同一散列函數(shù)計(jì)算出的散列值如果相同，輸入值不一定相同。
兩個(gè)不同的輸入值，根據(jù)同一散列函數(shù)計(jì)算出的散列值相同的現(xiàn)象叫做碰撞。
常見的 Hash 函數(shù)有以下幾個(gè)：
直接定址法：直接以關(guān)鍵字 k 或者 k 加上某個(gè)常數(shù)（k+c）作為哈希地址。
數(shù)字分析法：提取關(guān)鍵字中取值比較均勻的數(shù)字作為哈希地址。
除留余數(shù)法：用關(guān)鍵字 k 除以某個(gè)不大于哈希表長(zhǎng)度 m 的數(shù) p，將所得余數(shù)作為哈希表地址。
分段疊加法：按照哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分，其中最后一部分可以比較短。然后將這幾部分相加，舍棄最高進(jìn)位后的結(jié)果就是該關(guān)鍵字的哈希地址。
平方取中法：如果關(guān)鍵字各個(gè)部分分布都不均勻的話，可以先求出它的平方值，然后按照需求取中間的幾位作為哈希地址。
偽隨機(jī)數(shù)法：采用一個(gè)偽隨機(jī)數(shù)當(dāng)作哈希函數(shù)。
定義
以下是關(guān)于 HashCode 的官方文檔定義：
hashcode 方法返回該對(duì)象的哈希碼值。支持該方法是為哈希表提供一些優(yōu)點(diǎn)，例如，java.util.Hashtable 提供的哈希表。
hashCode 的常規(guī)協(xié)定是：
在 Java 應(yīng)用程序執(zhí)行期間，在同一對(duì)象上多次調(diào)用 hashCode 方法時(shí)，必須一致地返回相同的整數(shù)，前提是對(duì)象上 equals 比較中所用的信息沒有被修改。從某一應(yīng)用程序的一次執(zhí)行到同一應(yīng)用程序的另一次執(zhí)行，該整數(shù)無(wú)需保持一致。
如果根據(jù) equals(Object) 方法，兩個(gè)對(duì)象是相等的，那么在兩個(gè)對(duì)象中的每個(gè)對(duì)象上調(diào)用 hashCode 方法都必須生成相同的整數(shù)結(jié)果。
以下情況不是必需的：
如果根據(jù) equals(java.lang.Object)方法，兩個(gè)對(duì)象不相等，那么在兩個(gè)對(duì)象中的任一對(duì)象上調(diào)用 hashCode 方法必定會(huì)生成不同的整數(shù)結(jié)果。但是，程序員應(yīng)該知道，為不相等的對(duì)象生成不同整數(shù)結(jié)果可以提高哈希表的性能
實(shí)際上，由 Object 類定義的 hashCode 方法確實(shí)會(huì)針對(duì)不同的對(duì)象返回不同的整數(shù)。（這一般是通過將該對(duì)象的內(nèi)部地址轉(zhuǎn)換成一個(gè)整數(shù)來(lái)實(shí)現(xiàn)的，但是 JavaTM 編程語(yǔ)言不需要這種實(shí)現(xiàn)技巧。）當(dāng) equals 方法被重寫時(shí)，通常有必要重寫 hashCode 方法，以維護(hù) hashCode 方法的常規(guī)協(xié)定，該協(xié)定聲明相等對(duì)象必須具有相等的哈希碼。
總結(jié)一下：
1.hashcode 一致性 同一個(gè)對(duì)象的 hashcode 肯定是一樣的，無(wú)論調(diào)用多少次 hashcode 都不會(huì)變化，隨著 equals 肯定也是一樣的
2.兩個(gè)對(duì)象的 hashCode 相同，并不一定表示兩個(gè)對(duì)象就相同，也就是不一定適用于 equals(java.lang.Object) 方法，只能夠說明這兩個(gè)對(duì)象在散列存儲(chǔ)結(jié)構(gòu)中，如 Hashtable，他們“存放在同一個(gè)籃子里”。
3.如果對(duì)象的 equals 方法被重寫，那么對(duì)象的 hashCode 也盡量重寫，并且產(chǎn)生 hashCode 使用的對(duì)象，一定要和 equals 方法中使用的一致，
剛剛提到的碰撞，指的是不同對(duì)象的 hashcode 處在同一個(gè) bucket 當(dāng)中，這個(gè)情況發(fā)生的概率越大說明這個(gè) hashcode 設(shè)計(jì)的不夠理想
hashcode 和 equals 的聯(lián)系
當(dāng)且僅當(dāng)兩個(gè)對(duì)象的hashcode和equals相同時(shí)，這兩個(gè)對(duì)象才是同一個(gè)對(duì)象，否則不是。
那么快速判斷兩個(gè)對(duì)象的步驟是怎么樣的呢，我們假設(shè)這里有兩個(gè)不同的對(duì)象A和B。當(dāng)我們的hashcode設(shè)計(jì)合理的時(shí)候，這兩個(gè)對(duì)象的hashcode(A)是和hashcode(B)不相等的，那么這個(gè)時(shí)候我們就可以直接判斷A和B不是同一對(duì)象。但如果hashcode(A)==hashcode(B)呢？ 這個(gè)時(shí)候就要繼續(xù)通過equals方法進(jìn)行比較了，但是整個(gè)equals方法比hashcode復(fù)雜，所以設(shè)計(jì)一個(gè)好的hashcode函數(shù)至少可以節(jié)約90%以上的時(shí)間。
java 中的 hashcode 是如何實(shí)現(xiàn)的
我們知道 java 內(nèi)部 HashSet 和 HashMap 都是基于 hash 算法去實(shí)現(xiàn)的
hash算法的好壞，直接影響這個(gè)hashcode碰撞的幾率，好的hashcode可以使得所有對(duì)象均勻地分布在bucket中
1.Integer、Byte、Short、Character都是轉(zhuǎn)換為int類型作為hashcode
????public?static?int?hashCode(int?value)?{
????????return?value;
????}
可以看到hashcode在遇到Integer、Byte、Short、Character直接返回原數(shù)，不做處理。
public?class?HashMapTest?{
????public?static?void?main(String[]?args)?{
????????Integer?a?=?1;
????????Integer?b?=?1;
????????System.out.println(a.hashCode()+"??"+b.hashCode());
????????System.out.println(a.equals(b));
????}
}
------------------------------------------------------------
1??1
true
2.Long ?取高32位和低32位與值轉(zhuǎn)成int類型作為hashcode
Double ?將64bit值轉(zhuǎn)成long類型，然后按照Long類型進(jìn)行獲取hashcode**
????public?static?int?hashCode(double?value)?{
????????long?bits?=?doubleToLongBits(value);
????????return?(int)(bits?^?(bits?>>>?32));
????}
long型是將自己的高32位和低32位拆成兩個(gè)部分，然后兩個(gè)部份直接做與操作得出的數(shù)字作為hashcode。
demo中a=1,b=1<<32，均為L(zhǎng)ong型，按照我們的設(shè)計(jì)兩者的hashcode應(yīng)該是一樣的，但是不equals。看看我們的實(shí)驗(yàn)是否驗(yàn)證這個(gè)說法。
public?class?HashMapTest?{
????public?static?void?main(String[]?args)?{
????????long?number?=?1;
????????Long?a?=(long)1;
????????Long?b?=?number<<32;
????????System.out.println(a+"?"+b);
????????System.out.println(a.hashCode()+"?"+b.hashCode()?);
????????System.out.println(a.equals(b));
????}
}
------------------
1?4294967296
1?1
false
看來(lái)還是逃不過equals。
doubleToLongBits該方法可以將double類型數(shù)據(jù)轉(zhuǎn)換成long類型數(shù)據(jù)，從而可以使double類型數(shù)據(jù)按照l(shuí)ong的方法判斷大小（<, >, ==）。
3.String 將字符串里面的字符以31進(jìn)制求和，既hash=hash*31+value[i]
????public?int?hashCode()?{
????????int?h?=?hash;
????????if?(h?==?0?&&?value.length?>?0)?{
????????????char?val[]?=?value;
????????????for?(int?i?=?0;?i?????????????????h?=?31?*?h?+?val[i];
????????????}
????????????hash?=?h;
????????}
????????return?h;
????}
為什么選擇31作為乘子
31是一個(gè)不大不小的質(zhì)數(shù)，是作為 hashCode 乘子的優(yōu)選質(zhì)數(shù)之一。另外一些相近的質(zhì)數(shù)，比如37、41、43等等，也都是不錯(cuò)的選擇。那么為啥偏偏選中了31呢？請(qǐng)看第二個(gè)原因。
31可以被 JVM 優(yōu)化，31 * i = (i << 5) - i。
4.Boolean true值hashcode為1231，false值hashcode為1237
??????public?static?int?hashCode(boolean?value)?{
????????return?value???1231?:?1237;
????}
5.hashmap 放置元素的hashcode
????static?final?int?hash(Object?key)?{
????????int?h;
????????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
????}
由于和（length-1）運(yùn)算，length 絕大多數(shù)情況小于2的16次方。所以始終是hashcode 的低16位（甚至更低）參與運(yùn)算。要是高16位也參與運(yùn)算，會(huì)讓得到的下標(biāo)更加散列。
所以這樣高16位是用不到的，如何讓高16也參與運(yùn)算呢。所以才有hash(Object key)方法。讓他的hashCode()和自己的高16位^運(yùn)算。所以(h >>> 16)得到他的高16位與hashCode()進(jìn)行^運(yùn)算。
值得注意的是hashset存放的時(shí)候也是聲明了一個(gè)hashmap進(jìn)行存儲(chǔ)，所以原理等同于hashmap
demo
demo1 案例 不重寫 hashcode 和 equals：
public?class?HashCodeTest?{
????private?int?number;
????public?HashCodeTest(int?number){
????????this.number?=number;
????}
????public?static?void?main(String[]?args)?{
????????HashCodeTest?a?=?new?HashCodeTest(1);
????????HashCodeTest?b?=?new?HashCodeTest(1);
????????System.out.println(a.hashCode());
????????System.out.println(b.hashCode());
????????System.out.println(a.equals(b));
????}
}
輸出
460141958
1163157884
false
分析:
兩個(gè)不同的對(duì)象hashcode(a)和hashcode(b)肯定不同,a 對(duì)象和 b 對(duì)象調(diào)用 equal 函數(shù)肯定返回 false
demo2 案例 只重寫 hashcode:
public?class?HashCodeTest?{
????private?int?number;
????public?HashCodeTest(int?number){
????????this.number?=number;
????}
????@Override
????public?int?hashCode()?{
????????return?number%8;
????}
????public?static?void?main(String[]?args)?{
????????HashCodeTest?a?=?new?HashCodeTest(1);
????????HashCodeTest?b?=?new?HashCodeTest(1);
????????System.out.println(a.hashCode());
????????System.out.println(b.hashCode());
????????System.out.println(a.equals(b));
????}
}
輸出：
1
1
false
分析:
這個(gè)案例中只是覆寫了 hashcode 這個(gè)方法，沒有覆寫 equals。
這兩個(gè)不同的對(duì)象 hashcode 相同，但是 equals 不同。
從定義上看是 可以成立的。
但是 hashcode 過于簡(jiǎn)單，可能存在嚴(yán)重的哈希碰撞問題。而且必須滿足同一對(duì)象的 hashcode 是一致的。最好是 equals 和 hashcode 同時(shí)覆寫。
demo3 只重寫equals
public?class?HashCodeTest?{
????private?int?number;
????public?HashCodeTest(int?number){
????????this.number?=number;
????}
????@Override
????public?boolean?equals(Object?o)?{
????????HashCodeTest?that?=?(HashCodeTest)?o;
????????return?number?==?that.number;
????}
????public?static?void?main(String[]?args)?{
????????HashCodeTest?a?=?new?HashCodeTest(1);
????????HashCodeTest?b?=?new?HashCodeTest(1);
????????System.out.println(a.hashCode());
????????System.out.println(b.hashCode());
????????System.out.println(a.equals(b));
????}
}
輸出：
1956725890
356573597
true
只重寫equals，可能會(huì)因?yàn)橹貙懙姆椒ú粔蛲晟茖?dǎo)致原本兩個(gè)hashcode不同的對(duì)象equals返回true,這是最無(wú)法容忍的現(xiàn)象。
最近面試BAT，整理一份面試資料《Java面試BAT通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：點(diǎn)“在看”，關(guān)注公眾號(hào)并回復(fù)?Java?領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
明天見(??ω??)??