Java 中 hashCode() 和 equals() 的關(guān)系是面試中的?？键c(diǎn)，如果沒有深入思考過(guò)兩者設(shè)計(jì)的初衷，這個(gè)問(wèn)題將很難回答。除了應(yīng)付面試，理解二者的關(guān)系更有助于我們寫出高質(zhì)量且準(zhǔn)確的代碼。

一.基礎(chǔ)：hashCode() 和 equals() 簡(jiǎn)介

在學(xué)習(xí) hashCode() 和 equals() 之間的關(guān)系之前, 我們有必要先單獨(dú)地了解他倆的特點(diǎn).

equals()

equals() 方法用于比較兩個(gè)對(duì)象是否相等，它與 == 相等比較符有著本質(zhì)的不同。

在萬(wàn)物皆對(duì)象的 Java 體系中，系統(tǒng)把判斷對(duì)象是否相等的權(quán)力交給程序員。具體的措施是把 equals() 方法寫到 Object 類中，并讓所有類繼承 Object 類。這樣程序員就能在自定義的類中重寫 equals() 方法, 從而實(shí)現(xiàn)自己的比較邏輯。

hashCode()

hashCode() 的意思是哈希值, 哈希值是經(jīng)哈希函數(shù)運(yùn)算后得到的結(jié)果，哈希函數(shù)能夠保證相同的輸入能夠得到相同的輸出(哈希值)，但是不能夠保證不同的輸入總是能得出不同的輸出。

當(dāng)輸入的樣本量足夠大時(shí)，是會(huì)產(chǎn)生哈希沖突的，也就是說(shuō)不同的輸入產(chǎn)生了相同的輸出。

暫且不談沖突，就相同的輸入能夠產(chǎn)生相同的輸出這點(diǎn)而言，是及其寶貴的。它使得系統(tǒng)只需要通過(guò)簡(jiǎn)單的運(yùn)算，在時(shí)間復(fù)雜度O(1)的情況下就能得出數(shù)據(jù)的映射關(guān)系，根據(jù)這種特性，散列表應(yīng)運(yùn)而生。

一種主流的散列表實(shí)現(xiàn)是：用數(shù)組作為哈希函數(shù)的輸出域，輸入值經(jīng)過(guò)哈希函數(shù)計(jì)算后得到哈希值。然后根據(jù)哈希值，在數(shù)組種找到對(duì)應(yīng)的存儲(chǔ)單元。當(dāng)發(fā)生沖突時(shí)，對(duì)應(yīng)的存儲(chǔ)單元以鏈表的形式保存沖突的數(shù)據(jù)。

二. 漫談：初識(shí) hashCode() 與 equals() 之間的關(guān)系

下面我們從一個(gè)宏觀的角度討論 hashCode() 和 equals() 之間的關(guān)系。

在大多數(shù)編程實(shí)踐中，歸根結(jié)底會(huì)落實(shí)到數(shù)據(jù)的存取問(wèn)題上。在匯編語(yǔ)言時(shí)代，你需要老老實(shí)實(shí)地對(duì)每個(gè)數(shù)據(jù)操作編寫存取語(yǔ)句。

而隨著時(shí)代發(fā)展到今天，我們都用更方便靈活的高級(jí)語(yǔ)言編寫代碼，比如 Java。

Java 以面向?qū)ο鬄楹诵乃枷?，封裝了一系列操作數(shù)據(jù)的 api，降低了數(shù)據(jù)操作的復(fù)雜度。

但在我們對(duì)數(shù)據(jù)進(jìn)行操作之前，首先要把數(shù)據(jù)按照一定的數(shù)據(jù)結(jié)構(gòu)保存到存儲(chǔ)單元中，否則操作數(shù)據(jù)將無(wú)從談起。

然而不同的數(shù)據(jù)結(jié)構(gòu)有各自的特點(diǎn)，我們?cè)诖鎯?chǔ)數(shù)據(jù)的時(shí)候需要選擇合適的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)。Java 根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)提供了豐富的容器類，方便程序員選擇適合業(yè)務(wù)的容器類進(jìn)行開發(fā)。

通過(guò)繼承關(guān)系圖我們看到 Java 的容器類被分為 Collection 和 Map 兩大類，Collection 又可以進(jìn)一步分為 List 和 Set。 其中 Map 和 Set 都是不允許元素重復(fù)的，嚴(yán)格來(lái)說(shuō)Map存儲(chǔ)的是鍵值對(duì)，它不允許重復(fù)的鍵值。

值得注意的是：Map 和 Set 的絕大多數(shù)實(shí)現(xiàn)類的底層都會(huì)用到散列表結(jié)構(gòu)。

講到這里我們提取兩個(gè)關(guān)鍵字不允許重復(fù)和散列表結(jié)構(gòu)，回顧 hashCode() 和 equals() 的特點(diǎn)，你是否想到了些什么東西呢？

三. 解密：深入理解 hashCode() 和 equals() 之間的關(guān)系

equals() 會(huì)有力不從心的時(shí)候

上面提到 Set 和 Map 不存放重復(fù)的元素（key），這些容器在存儲(chǔ)元素的時(shí)必須對(duì)元素做出判斷：在當(dāng)前的容器中有沒有和新元素相同的元素？

你可能會(huì)想：這容易呀，直接調(diào)用元素對(duì)象的 equals() 方法進(jìn)行比較不就行了嗎？

如果容器中的存儲(chǔ)的對(duì)象數(shù)量較少，這確實(shí)是個(gè)好主意，但是如果容器中存放的對(duì)象達(dá)到了一定的規(guī)模，要調(diào)用容器中所有對(duì)象的 equals() 方法和新元素進(jìn)行比較，就不是一件容易的事情了。

就算 equals() 方法的比較邏輯簡(jiǎn)單無(wú)比，總的來(lái)說(shuō)也是一個(gè)時(shí)間復(fù)雜度為 O(n) 的操作啊。

hashCode() 小力出奇跡

但在散列表的基礎(chǔ)上，判斷“新對(duì)象是否和已存在對(duì)象相同”就容易得多了。

由于每個(gè)對(duì)象都自帶有 hashCode()，這個(gè) hashCode 將會(huì)用作散列表哈希函數(shù)的輸入，hashCode 經(jīng)過(guò)哈希函數(shù)計(jì)算后得到哈希值，新對(duì)象會(huì)根據(jù)哈希值，存儲(chǔ)到相應(yīng)的內(nèi)存的單元。

我們不妨假設(shè)兩個(gè)相同的對(duì)象，hashCode() 一定相同，這么一來(lái)就體現(xiàn)出哈希函數(shù)的威力了。

由于相同的輸入一定會(huì)產(chǎn)生相同的輸出，于是如果新對(duì)象，和容器中已存在的對(duì)象相同，新對(duì)象計(jì)算出的哈希值就會(huì)和已存在的對(duì)象的哈希值產(chǎn)生沖突。

這時(shí)容器就能判斷：這個(gè)新加入的元素已經(jīng)存在，需要另作處理：覆蓋掉原來(lái)的元素（key）或舍棄。

按照這個(gè)思路，如果這個(gè)元素計(jì)算出的哈希值所對(duì)應(yīng)的內(nèi)存單元沒有產(chǎn)生沖突，也就是沒有重復(fù)的元素，那么它就可以直接插入。

所以當(dāng)運(yùn)用 hashCode() 時(shí)，判斷是否有相同元素的代價(jià)，只是一次哈希計(jì)算，時(shí)間復(fù)雜度為O(1)，這極大地提高了數(shù)據(jù)的存儲(chǔ)性能。

Java 設(shè)計(jì) equals()，hashCode() 時(shí)約定的規(guī)則

前面我們還提到：當(dāng)輸入樣本量足夠大時(shí)，不相同的輸入是會(huì)產(chǎn)生相同輸出的，也就是形成哈希沖突。

這么一來(lái)就麻煩了，原來(lái)我們?cè)O(shè)定的“如果產(chǎn)生沖突，就意味著兩個(gè)對(duì)象相同”的規(guī)則瞬間被打破，因?yàn)楫a(chǎn)生沖突的很有可能是兩個(gè)不同的對(duì)象！

而令人欣慰的是我們除了 hashCode() 方法，還有一張王牌：equals() 方法。

也就是說(shuō)當(dāng)兩個(gè)不相同的對(duì)象產(chǎn)生哈希沖突后，我們可以用 equals() 方法進(jìn)一步判斷兩個(gè)對(duì)象是否相同。

這時(shí) equals() 方法就相當(dāng)重要了，這個(gè)情況下它必須要能判定這兩個(gè)對(duì)象是不相同的。

• 講到這里就引出了 Java 程序設(shè)計(jì)中一個(gè)重要原則：

如果兩個(gè)對(duì)象是相等的，它們的 equals() 方法應(yīng)該要返回 true，它們的 hashCode() 需要返回相同的結(jié)果。

但有時(shí)候面試不會(huì)問(wèn)得這么直接，他會(huì)問(wèn)你：兩個(gè)對(duì)象的 hashCdoe() 相同，它的 equals() 方法一定要返回 true，對(duì)嗎？

那答案肯定不對(duì)。因?yàn)槲覀儾荒鼙ＷC每個(gè)程序設(shè)計(jì)者，都會(huì)遵循編碼約定。

有可能兩個(gè)不同對(duì)象的hashCode()會(huì)返回相同的結(jié)果，但是由于他們是不同的對(duì)象，他們的 equals() 方法會(huì)返回false。

如果你理解上面的內(nèi)容，這個(gè)問(wèn)題就很好解答，我們?cè)倩仡櫼幌拢?/p>

如果兩個(gè)對(duì)象的 hashCode() 相同，將來(lái)就會(huì)在散列表中產(chǎn)生哈希沖突，但是它們不一定是相同的對(duì)象呀。

當(dāng)產(chǎn)生哈希沖突時(shí)，我們還得通過(guò) equals() 方法進(jìn)一步判斷兩個(gè)對(duì)象是否相同，equals() 方法不一定會(huì)返回 true。

這也是為什么 Java 官方推薦我們?cè)谝粋€(gè)類中，最好同時(shí)重寫 hashCode() 和 equals() 方法的原因。

四. 驗(yàn)證：結(jié)合 HashMap 的源碼和官方文檔，驗(yàn)證兩者的關(guān)系

以上的文字，是我經(jīng)過(guò)思考后得出的，它有一定依據(jù)但并非完全可靠。下面我們根據(jù) HashMap 的源碼（JDK1.8）和官方文檔，來(lái)驗(yàn)證這些推論是否正確。

通過(guò)閱讀JDK8的官方文檔，我們發(fā)現(xiàn) equals() 方法介紹的最后有這么一段話：

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

官方文檔提醒我們當(dāng)重寫 equals() 方法的時(shí)候，最好也要重寫 hashCode() 方法。

也就是說(shuō)如果我們通過(guò)重寫 equals() 方法判斷兩個(gè)對(duì)象相同時(shí)，他們的hash code也應(yīng)該相同，這樣才能讓hashCode()方法發(fā)揮它的作用。

那它究竟能發(fā)會(huì)怎樣的作用呢？

我們結(jié)合部分較為常用的 HashMap 源碼進(jìn)一步分析。（像 HashSet 底層也是通過(guò) HashMap 實(shí)現(xiàn)的）

在 HashMap 中用得最多無(wú)疑是 put() 方法了，以下是put()的源碼：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

我們可以看到 put() 方法實(shí)際調(diào)用的是 putVal() 方法，繼續(xù)跟進(jìn)：

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //在我們創(chuàng)建HashMap對(duì)象的時(shí)候, 內(nèi)存中并沒有為HashMap分配表的空間, 直到往HashMap中put添加元素的時(shí)候才調(diào)用resize()方法初始化表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//同時(shí)確定了表的長(zhǎng)度

    //((n - 1) & hash)確定了要put的元素的位置, 如果要插入的地方是空的, 就可以直接插入.
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//如果發(fā)生了沖突, 就要在沖突位置的鏈表末尾插入元素
        Node<K,V> e; K k;
        if (p.hash == hash &&   
            ((k = p.key) == key || (key != null && key.equals(k))))
            //關(guān)鍵!!!當(dāng)判斷新加入的元素是否與已有的元素相同, 首先判斷的是hash值, 后面再調(diào)用equals()方法. 如果hash值不同是直接跳過(guò)的
            e = p;
        else if (p instanceof TreeNode)//如果沖突解決方案已經(jīng)變成紅黑樹的話, 按紅黑樹的策略添加結(jié)點(diǎn). 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//解決沖突的方式仍是鏈表
            for (int binCount = 0; ; ++binCount) {//找到鏈表的末尾, 插入.
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);//插入之后要判斷鏈表的長(zhǎng)度, 如果到達(dá)一定的值就可能要轉(zhuǎn)換為紅黑樹. 
                    break;
                }//在遍歷的過(guò)程中仍會(huì)不停地判定當(dāng)前key是否與傳入的key相同, 判斷的第一條件仍然是hash值. 
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;//修改map的次數(shù)增加
    if (++size > threshold)//如果hashMap的容量到達(dá)了一定值就要進(jìn)行擴(kuò)容
        resize();
    afterNodeInsertion(evict);
    return null;
}

我們可以看到每當(dāng)判斷 key 是否相同時(shí)，首先會(huì)判斷 hash 值，如果 hash 值相同（產(chǎn)生了沖突），然后會(huì)判斷 key 引用所指的對(duì)象是否相同，最終會(huì)通過(guò) equals() 方法作最后的判定。

如果 key 的 hash 值不同，后面的判斷將不會(huì)執(zhí)行，直接認(rèn)定兩個(gè)對(duì)象不相同。

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

五. 結(jié)束

講到這里希望大家對(duì) hashCode() 與 equals() 方法能有更深入的理解，明白背后的設(shè)計(jì)思想與原理。

我之前有一個(gè)疑問(wèn)，可能大家看完這篇文章后也會(huì)有：equals() 方法平時(shí)我會(huì)用到，所以我知道它除了和 hashCode() 方法有密切聯(lián)系外，還有別的用途。

但是hashCode()呢？它除了和equals()方法有密切聯(lián)系外，還有其他用途嗎？

經(jīng)過(guò)在互聯(lián)網(wǎng)上一番搜尋，我目前給出的答案是沒有。

也就是說(shuō) hashCode() 僅在散列表中才有用，在其它情況下沒用。