面試官：換人！他連哈?？鄣亩疾欢?/h1>

作者：煙雨星空 2020-06-22 08:16:16

我們通常說的 hashCode 其實(shí)就是一個(gè)經(jīng)過哈希運(yùn)算之后的整型值。而這個(gè)哈希運(yùn)算的算法，在 Object 類中就是通過一個(gè)本地方法 hashCode() 來實(shí)現(xiàn)的(HashMap 中還會有一些其它的運(yùn)算)。

前言

相信你面試的時(shí)候，肯定被問過 hashCode 和 equals 相關(guān)的問題。如：

hashCode 是什么?它是怎么得來的?有什么用?
經(jīng)典題，equals 和 == 有什么區(qū)別?
為什么要重寫 equals 和 hashCode ?
重寫了 equals ，就必須要重寫 hashCode 嗎?為什么?
hashCode 相等時(shí)，equals 一定相等嗎?反過來呢?

好的，上面就是靈魂拷問環(huán)節(jié)。其實(shí)，這些問題仔細(xì)想一下也不難，主要是平時(shí)我們很少去思考它。

[[330868]]

正文

下面就按照上邊的問題順序，一個(gè)一個(gè)剖析它。扒開 hashCode 的神秘面紗。

什么是 hashCode?

public native int hashCode();

可以看到它是一個(gè)本地方法。那么，想要了解這個(gè)方法到底是用來干嘛的，最直接有效的方法就是，去看它的源碼注釋。

下邊我就用我蹩腳的英文翻譯一下它的意思。。。

返回當(dāng)前對象的一個(gè)哈希值。這個(gè)方法用于支持一些哈希表，例如 HashMap 。

通常來講，它有如下一些約定：

若對象的信息沒有被修改，那么，在一個(gè)程序的執(zhí)行期間，對于相同的對象，不管調(diào)用多少次 hashCode 方法，都應(yīng)該返回相同的值。當(dāng)然，在相同程序的不同執(zhí)行期間，不需要保持結(jié)果一致。
若兩個(gè)對象的 equals 方法返回值相同，那么，調(diào)用它們各自的 hashCode 方法時(shí)，也必須返回相同的結(jié)果。(ps: 這句話解答了上邊的一些問題，后面會用例子來證明這一點(diǎn))
當(dāng)兩個(gè)對象的 equals 方法返回值不同時(shí)，那么它們的 hashCode 方法不用保證必須返回不同的值。但是，我們應(yīng)該知道，在這種情況下，我們最好也設(shè)計(jì)成 hashCode 返回不同的值。因?yàn)?，這樣做有助于提高哈希表的性能。

在實(shí)際情況下，Object 類的 hashCode 方法在不同的對象中確實(shí)返回了不同的哈希值。這通常是通過把對象的內(nèi)部地址轉(zhuǎn)換為一個(gè)整數(shù)來實(shí)現(xiàn)的。

ps: 這里說的內(nèi)部地址就是指物理地址，也就是內(nèi)存地址。需要注意的是，雖然 hashCode 值是依據(jù)它的內(nèi)存地址而得來的。但是，不能說 hashCode 就代表對象的內(nèi)存地址，實(shí)際上，hashCode 地址是存放在哈希表中的。

上邊的源碼注釋真可謂是句句珠璣，把 hashCode 方法解釋的淋漓盡致。一會兒我通過一個(gè)案例說明，就能明白我為什么這樣說了。

什么是哈希表?

上文中提到了哈希表。什么是哈希表呢?我們直接看百度百科的解釋。

用一張圖來表示它們的關(guān)系。

左邊一列就是一些關(guān)鍵碼(key)，通過哈希函數(shù)，它們都會得到一個(gè)固定的值，分別對應(yīng)右邊一列的某個(gè)值。右邊的這一列就可以認(rèn)為是一張哈希表。

而且，我們會發(fā)現(xiàn)，有可能有些 key 不同，但是它們對應(yīng)的哈希值卻是一樣的，例如 aa，bb 都指向 1001 。但是，一定不會出現(xiàn)同一個(gè) key 指向不同的值。

這也非常好理解，因?yàn)楣１砭褪怯脕聿檎?key 的哈希地址的。在 key 確定的情況下，通過哈希函數(shù)計(jì)算出來的哈希地址，一定也是確定的。如圖中的 cc 已經(jīng)確定在 1002 位置了，那么就不可能再占據(jù) 1003 位置。

思考一下，如果有另外一個(gè)元素 ee 來了，它的哈希地址也落在 1002 位置，怎么辦呢?

hashCode 有什么用?

其實(shí)，上圖就已經(jīng)可以說明一些問題了。我們通過一個(gè) key 計(jì)算出它的 hashCode 值，就可以唯一確定它在哈希表中的位置。這樣，在查詢時(shí)，就可以直接定位到當(dāng)前元素，提高查詢效率。

現(xiàn)在我們假設(shè)有這樣一個(gè)場景。我們需要在內(nèi)存中的一塊兒區(qū)域存放 10000 個(gè)不同的元素(以aa,bb,cc,dd 等為例)。那怎么實(shí)現(xiàn)不同的元素插入，相同的元素覆蓋呢?

我們最容易想到的方法就是，每當(dāng)存一個(gè)新元素時(shí)，就遍歷一遍已經(jīng)存在的元素，看有沒有相同的。這樣雖然也是可以實(shí)現(xiàn)的，但是，如果已經(jīng)存在了 9000 個(gè)元素，你就需要去遍歷一下這 9000 個(gè)元素。很明顯，這樣的效率是非常低下的。

我們轉(zhuǎn)換一種思路，還是以上圖為例。若來了一個(gè)新元素 ff，首先去計(jì)算它的 hashCode 值，得出為 1003 。發(fā)現(xiàn)此處還沒有元素，則直接把這個(gè)新元素 ff 放到此位置。

然后，ee 來了，通過計(jì)算哈希值得到 1002 。此時(shí)，發(fā)現(xiàn) 1002 位置已經(jīng)存在一個(gè)元素了。那么，通過 equals 方法比較它們是否相等，發(fā)現(xiàn)只有一個(gè) dd 元素，很明顯和 ee 不相等。那么，就把 ee 元素放到 dd 元素的后邊(可以用鏈表形式存放)。

我們會發(fā)現(xiàn)，當(dāng)有新元素來的時(shí)候，先去計(jì)算它們的哈希值，再去確定存放的位置，這樣就可以減少比較的次數(shù)。如 ff 不需要比較， ee 只需要和 dd 比較一次。

當(dāng)元素越來越多的時(shí)候，新元素也只需要和當(dāng)前哈希值相同的位置上，已經(jīng)存在的元素進(jìn)行比較。而不需要和其他哈希值不同的位置上的元素進(jìn)行比較。這樣就大大減少了元素的比較次數(shù)。

圖中為了方便，畫的哈希表比較小。現(xiàn)在假設(shè)，這個(gè)哈希表非常的大，例如有這么非常多個(gè)位置，從 1001 ~ 9999。那么，新元素插入的時(shí)候，有很大概率會插入到一個(gè)還沒有元素存在的位置上，這樣就不需要比較了，效率非常高。但是，我們會發(fā)現(xiàn)這樣也有一個(gè)弊端，就是哈希表所占的內(nèi)存空間就會變大。因此，這是一個(gè)權(quán)衡的過程。

有心的同學(xué)可能已經(jīng)發(fā)現(xiàn)了。我去，上邊的這個(gè)做法好熟悉啊。沒錯(cuò)，它就是大名鼎鼎的 HashMap 底層實(shí)現(xiàn)的思想。對 HashMap 還不了解的，趕緊看這篇文章理一下思路：HashMap 底層實(shí)現(xiàn)原理及源碼分析

所以，hashCode 有什么用。很明顯，提高了查詢，插入元素的效率呀。

equals 和 == 有什么區(qū)別?

這是萬年不變，經(jīng)久不衰的經(jīng)典面試題了。讓我油然想起，當(dāng)初為了面試，背誦過的面經(jīng)了，簡直是一把心酸一把淚。現(xiàn)在還能記得這道題的標(biāo)準(zhǔn)答案：equals 比較的是內(nèi)容， == 比較的是地址。

當(dāng)時(shí)，真的就只是背答案，知其然而不知其所以然。再往下問，為什么要重寫 equals ，就懵逼了。

首先，我們應(yīng)該知道 equals 是定義在所有類的父類 Object 中的。

public boolean equals(Object obj) { 
    return (this == obj); 
}

可以看到，它的默認(rèn)實(shí)現(xiàn)，就是 == ，這是用來比較內(nèi)存地址的。所以，如果一個(gè)對象的 equals 不重寫的話，和 == 的效果是一樣的。

我們知道，當(dāng)創(chuàng)建兩個(gè)普通對象時(shí)，一般情況下，它們所對應(yīng)的內(nèi)存地址是不一樣的。例如，我定義一個(gè) User 類。

public class User { 
    private String name; 
    private int age; 
 
    public String getName() { 
        return name; 
    } 
 
    public void setName(String name) { 
        this.name = name; 
    } 
 
    public int getAge() { 
        return age; 
    } 
 
    public void setAge(int age) { 
        this.age = age; 
    } 
 
    public User(String name, int age) { 
        this.name = name; 
        this.age = age; 
    } 
 
    public User() { 
 
    } 
} 
 
public class TestHashCode { 
    public static void main(String[] args) { 
        User user1 = new User("zhangsan", 20); 
        User user2 = new User("lisi", 18);  
 
        System.out.println(user1 == user2); 
        System.out.println(user1.equals(user2)); 
    } 
} 
// 結(jié)果：false false

很明顯，zhangsan 和 lisi 是兩個(gè)人，兩個(gè)不同的對象。因此，它們所對應(yīng)的內(nèi)存地址不同，而且內(nèi)容也不相等。

注意，這里我還沒有對 User 重寫 equals，實(shí)際此時(shí) equals 使用的是父類 Object 的方法，返回的肯定是不相等的。因此，為了更好地說明問題，我僅把第二行代碼修改如下：

//User user2 = new User("lisi", 18); 
User user2 = new User("zhangsan", 20);

讓 user1 和 user2 的內(nèi)容相同，都是 zhangsan，20歲。按我們的理解，這雖然是兩個(gè)對象，但是應(yīng)該是指的同一個(gè)人，都是張三。但是，打印結(jié)果，如下：

這有悖于我們的認(rèn)知，明明是同一個(gè)人，為什么 equals 返回的卻不相等呢。因此，此時(shí)我們就需要把 User 類中的 equals 方法重寫，以達(dá)到我們的目的。在 User 中添加如下代碼(使用 idea 自動生成代碼)：

public class User { 
    ... //省略已知代碼 
         
    @Override 
    public boolean equals(Object o) { 
        //若兩個(gè)對象的內(nèi)存地址相同，則說明指向的是同一個(gè)對象，故內(nèi)容一定相同。 
        if (this == o) return true; 
        //類都不是同一個(gè)，更別談相等了 
        if (o == null || getClass() != o.getClass()) return false; 
        User user = (User) o; 
        //比較兩個(gè)對象中的所有屬性，即name和age都必須相同，才可認(rèn)為兩個(gè)對象相等 
        return age == user.age && 
                Objects.equals(name, user.name); 
    } 
    
} 
//打印結(jié)果：  false  true

再次執(zhí)行程序，我們會發(fā)現(xiàn)此時(shí) equals 返回 true ，這才是我們想要的。

因此，當(dāng)我們使用自定義對象時(shí)。如果需要讓兩個(gè)對象的內(nèi)容相同時(shí)，equals 返回 true，則需要重寫 equals 方法。

為什么要重寫 equals 和 hashCode ?

在上邊的案例中，其實(shí)我們已經(jīng)說明了為什么要去重寫 equals 。因?yàn)?，在對象?nèi)容相同的情況下，我們需要讓對象相等。因此，不能用 Object 類的默認(rèn)實(shí)現(xiàn)，只去比較內(nèi)存地址，這樣是不合理的。

那 hashCode 為什么要重寫呢?這就涉及到集合，如 Map 和 Set (底層其實(shí)也是 Map)了。

我們以 HashMap JDK1.8的源碼來看，如 put 方法。

我們會發(fā)現(xiàn)，代碼中會多次進(jìn)行 hash 值的比較，只有當(dāng)哈希值相等時(shí)，才會去比較 equals 方法。當(dāng) hashCode 和 equals 都相同時(shí)，才會覆蓋元素。get 方法也是如此(先比較哈希值，再比較equals)，

只有 hashCode 和 equals 都相等時(shí)，才認(rèn)為是同一個(gè)元素，找到并返回此元素，否則返回 null。

這也對應(yīng) “hashCode 有什么用?”這一小節(jié)。重寫 equals 和 hashCode 的目的，就是為了方便哈希表這樣的結(jié)構(gòu)快速的查詢和插入。如果不重寫，則無法比較元素，甚至造成元素位置錯(cuò)亂。

重寫了 equals ，就必須要重寫 hashCode 嗎?

答案是肯定的。首先，在上邊的 JDK 源碼注釋中第第二點(diǎn)，我們就會發(fā)現(xiàn)這句說明。其次，我們嘗試重寫 equals ，而不重寫 hashCode 看會發(fā)生什么現(xiàn)象。

public class TestHashCode { 
    public static void main(String[] args) { 
        User user1 = new User("zhangsan", 20); 
        User user2 = new User("zhangsan", 20); 
 
        HashMap<User, Integer> map = new HashMap<>(); 
        map.put(user1,90); 
        System.out.println(map.get(user2)); 
    } 
} 
// 打印結(jié)果：null

對于代碼中的 user1 和 user2 兩個(gè)對象來說，我們認(rèn)為他是同一個(gè)人張三。定義一個(gè) map ，key 存儲 User 對象， value 存儲他的學(xué)習(xí)成績。

當(dāng)把 user1 對象作為 key ，成績 90 作為 value 存儲到 map 中時(shí)，我們肯定希望，用 key 為 user2 來取值時(shí)，得到的結(jié)果是 90 。但是，結(jié)果卻大失所望，得到了 null 。

這是因?yàn)?，我們自定義的 User 類，雖然重寫了 equals ，但是沒有重寫 hashCode 。當(dāng) user1 放到 map 中時(shí)，計(jì)算出來的哈希值和用 user2 去取值時(shí)計(jì)算的哈希值不相等。因此，equals 方法都沒有比較的機(jī)會。認(rèn)為他們是不同的元素。然而，其實(shí)，我們應(yīng)該認(rèn)為 user1 和 user2 是相同的元素的。

用圖來說明就是，user1 和 user2 存放在了 HashMap 中不同的桶里邊，導(dǎo)致查詢不到目標(biāo)元素。

因此，當(dāng)我們用自定義類來作為 HashMap 的 key 時(shí)，必須要重寫 hashCode 和 equals 。否則，會得到我們不想要的結(jié)果。

這也是為什么，我們平時(shí)都喜歡用 String 字符串來作為 key 的原因。因?yàn)椋?String 類默認(rèn)就幫我們實(shí)現(xiàn)了 equals 和 hashCode 方法的重寫。如下，

// String.java 
public boolean equals(Object anObject) { 
    if (this == anObject) { 
        return true; 
    } 
    if (anObject instanceof String) { 
        String anotherString = (String)anObject; 
        int n = value.length; 
        //從前向后依次比較字符串中的每個(gè)字符 
        if (n == anotherString.value.length) { 
            char v1[] = value; 
            char v2[] = anotherString.value; 
            int i = 0; 
            while (n-- != 0) { 
                if (v1[i] != v2[i]) 
                    return false; 
                i++; 
            } 
            return true; 
        } 
    } 
    return false; 
} 
 
public int hashCode() { 
    int h = hash; 
    if (h == 0 && value.length > 0) { 
        char val[] = value; 
  //把字符串中的每個(gè)字符都取出來，參與運(yùn)算 
        for (int i = 0; i < value.length; i++) { 
            h = 31 * h + val[i]; 
        } 
        //把計(jì)算出來的最終值，存放在hash變量中。 
        hash = h; 
    } 
    return h; 
}

重寫 equals 時(shí)，可以使用 idea 提供的自動代碼，也可以自己手動實(shí)現(xiàn)。

public class User { 
    ... //省略已知代碼 
         
    @Override 
    public int hashCode() { 
        return Objects.hash(name, age); 
    } 
    
} 
//此時(shí)，map.get(user2) 可以得到 90 的正確值

在重寫了 hashCode 后，使用自定義對象作為 key 時(shí)，還需要注意一點(diǎn)，不要在使用過程中，改變對象的內(nèi)容，這樣會導(dǎo)致 hashCode 值發(fā)生改變，同樣得不到正確的結(jié)果。如下，

public class TestHashCode { 
    public static void main(String[] args) { 
        User user = new User("zhangsan", 20); 
 
        HashMap<User, Integer> map = new HashMap<>(); 
        map.put(user,90); 
        System.out.println(map.get(user)); 
        user.setAge(18); //把對象的年齡修改為18 
        System.out.println(map.get(user)); 
    } 
} 
// 打印結(jié)果： 
// 90 
// null

會發(fā)現(xiàn)，修改后，拿到的值是 null 。這也是，hashCode 源碼注釋中的第一點(diǎn)說明的，hashCode 值不變的前提是，對象的信息沒有被修改。若被修改，則有可能導(dǎo)致 hashCode 值改變。

此時(shí)，有沒有聯(lián)想到其他一些問題。比如，為什么 String 類要設(shè)計(jì)成不可以變的呢?這里用 String 作為 HashMap 的 key 時(shí)，可以算作一個(gè)原因。你肯定不希望，放進(jìn)去的時(shí)候還好好的，取出來的時(shí)候，卻找不到元素了吧。

String 類內(nèi)部會有一個(gè)變量(hash)來緩存字符串的 hashCode 值。只有字符串不可變，才可以保證哈希值不變。