Java 中 hashCode() 與 equals() 的關系(面試)

Posted on by

前言：

Java 中 hashCode() 和 equals() 的關系是面試中的常考點，如果沒有深入思考過兩者設計的初衷，這個問題將很難回答。除瞭應付面試，理解二者的關系更有助於我們寫出高質量且準確的代碼。

一.基礎：hashCode() 和 equals() 簡介

在學習 hashCode() 和 equals() 之間的關系之前, 我們有必要先單獨地瞭解他倆的特點.

equals()

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

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

hashCode()

hashCode() 的意思是哈希值, 哈希值是經哈希函數運算後得到的結果，哈希函數能夠保證相同的輸入能夠得到相同的輸出(哈希值)，但是不能夠保證不同的輸入總是能得出不同的輸出。

當輸入的樣本量足夠大時，是會產生哈希沖突的，也就是說不同的輸入產生瞭相同的輸出。

暫且不談沖突，就相同的輸入能夠產生相同的輸出這點而言，是及其寶貴的。它使得系統隻需要通過簡單的運算，在時間復雜度O(1)的情況下就能得出數據的映射關系，根據這種特性，散列表應運而生。

一種主流的散列表實現是：用數組作為哈希函數的輸出域，輸入值經過哈希函數計算後得到哈希值。然後根據哈希值，在數組種找到對應的存儲單元。當發生沖突時，對應的存儲單元以鏈表的形式保存沖突的數據。

二. 漫談：初識 hashCode() 與 equals() 之間的關系

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

在大多數編程實踐中，歸根結底會落實到數據的存取問題上。在匯編語言時代，你需要老老實實地對每個數據操作編寫存取語句。

而隨著時代發展到今天，我們都用更方便靈活的高級語言編寫代碼，比如 Java。

Java 以面向對象為核心思想，封裝瞭一系列操作數據的 api，降低瞭數據操作的復雜度。

但在我們對數據進行操作之前，首先要把數據按照一定的數據結構保存到存儲單元中，否則操作數據將無從談起。

然而不同的數據結構有各自的特點，我們在存儲數據的時候需要選擇合適的數據結構進行存儲。Java 根據不同的數據結構提供瞭豐富的容器類，方便程序員選擇適合業務的容器類進行開發。

通過繼承關系圖我們看到 Java 的容器類被分為 Collection 和 Map 兩大類，Collection 又可以進一步分為 List 和 Set。 其中 Map 和 Set 都是不允許元素重復的，嚴格來說Map存儲的是鍵值對，它不允許重復的鍵值。

值得註意的是：Map 和 Set 的絕大多數實現類的底層都會用到散列表結構。

講到這裡我們提取兩個關鍵字不允許重復和散列表結構，回顧 hashCode() 和 equals() 的特點，你是否想到瞭些什麼東西呢？

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

equals() 會有力不從心的時候

上面提到 Set 和 Map 不存放重復的元素（key），這些容器在存儲元素的時必須對元素做出判斷：在當前的容器中有沒有和新元素相同的元素？

你可能會想：這容易呀，直接調用元素對象的 equals() 方法進行比較不就行瞭嗎？

如果容器中的存儲的對象數量較少，這確實是個好主意，但是如果容器中存放的對象達到瞭一定的規模，要調用容器中所有對象的 equals() 方法和新元素進行比較，就不是一件容易的事情瞭。

就算 equals() 方法的比較邏輯簡單無比，總的來說也是一個時間復雜度為 O(n) 的操作啊。

hashCode() 小力出奇跡

但在散列表的基礎上，判斷“新對象是否和已存在對象相同”就容易得多瞭。

由於每個對象都自帶有 hashCode()，這個 hashCode 將會用作散列表哈希函數的輸入，hashCode 經過哈希函數計算後得到哈希值，新對象會根據哈希值，存儲到相應的內存的單元。

我們不妨假設兩個相同的對象，hashCode() 一定相同，這麼一來就體現出哈希函數的威力瞭。

由於相同的輸入一定會產生相同的輸出，於是如果新對象，和容器中已存在的對象相同，新對象計算出的哈希值就會和已存在的對象的哈希值產生沖突。

這時容器就能判斷：這個新加入的元素已經存在，需要另作處理：覆蓋掉原來的元素（key）或舍棄。

按照這個思路，如果這個元素計算出的哈希值所對應的內存單元沒有產生沖突，也就是沒有重復的元素，那麼它就可以直接插入。

所以當運用 hashCode() 時，判斷是否有相同元素的代價，隻是一次哈希計算，時間復雜度為O(1)，這極大地提高瞭數據的存儲性能。

Java 設計 equals()，hashCode() 時約定的規則

前面我們還提到：當輸入樣本量足夠大時，不相同的輸入是會產生相同輸出的，也就是形成哈希沖突。

這麼一來就麻煩瞭，原來我們設定的“如果產生沖突，就意味著兩個對象相同”的規則瞬間被打破，因為產生沖突的很有可能是兩個不同的對象！

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

也就是說當兩個不相同的對象產生哈希沖突後，我們可以用 equals() 方法進一步判斷兩個對象是否相同。

這時 equals() 方法就相當重要瞭，這個情況下它必須要能判定這兩個對象是不相同的。

講到這裡就引出瞭 Java 程序設計中一個重要原則：

如果兩個對象是相等的，它們的 equals() 方法應該要返回 true，它們的 hashCode() 需要返回相同的結果。

但有時候面試不會問得這麼直接，他會問你：兩個對象的 hashCdoe() 相同，它的 equals() 方法一定要返回 true，對嗎？

那答案肯定不對。因為我們不能保證每個程序設計者，都會遵循編碼約定。

有可能兩個不同對象的hashCode()會返回相同的結果，但是由於他們是不同的對象，他們的 equals() 方法會返回false。

如果你理解上面的內容，這個問題就很好解答，我們再回顧一下：

如果兩個對象的 hashCode() 相同，將來就會在散列表中產生哈希沖突，但是它們不一定是相同的對象呀。

當產生哈希沖突時，我們還得通過 equals() 方法進一步判斷兩個對象是否相同，equals() 方法不一定會返回 true。

這也是為什麼 Java 官方推薦我們在一個類中，最好同時重寫 hashCode() 和 equals() 方法的原因。

四. 驗證：結合 HashMap 的源碼和官方文檔，驗證兩者的關系

以上的文字，是我經過思考後得出的，它有一定依據但並非完全可靠。下面我們根據 HashMap 的源碼（JDK1.8）和官方文檔，來驗證這些推論是否正確。

通過閱讀JDK8的官方文檔，我們發現 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.

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

也就是說如果我們通過重寫 equals() 方法判斷兩個對象相同時，他們的hash code也應該相同，這樣才能讓hashCode()方法發揮它的作用。

那它究竟能發會怎樣的作用呢？

我們結合部分較為常用的 HashMap 源碼進一步分析。（像 HashSet 底層也是通過 HashMap 實現的）

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

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

我們可以看到 put() 方法實際調用的是 putVal() 方法，繼續跟進：

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

    //((n - 1) & hash)確定瞭要put的元素的位置, 如果要插入的地方是空的, 就可以直接插入.
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//如果發生瞭沖突, 就要在沖突位置的鏈表末尾插入元素
        Node<K,V> e; K k;
        if (p.hash == hash &&   
            ((k = p.key) == key || (key != null && key.equals(k))))
            //關鍵!!!當判斷新加入的元素是否與已有的元素相同, 首先判斷的是hash值, 後面再調用equals()方法. 如果hash值不同是直接跳過的
            e = p;
        else if (p instanceof TreeNode)//如果沖突解決方案已經變成紅黑樹的話, 按紅黑樹的策略添加結點. 
            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);//插入之後要判斷鏈表的長度, 如果到達一定的值就可能要轉換為紅黑樹. 
                    break;
                }//在遍歷的過程中仍會不停地判定當前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的次數增加
    if (++size > threshold)//如果hashMap的容量到達瞭一定值就要進行擴容
        resize();
    afterNodeInsertion(evict);
    return null;
}

我們可以看到每當判斷 key 是否相同時，首先會判斷 hash 值，如果 hash 值相同（產生瞭沖突），然後會判斷 key 引用所指的對象是否相同，最終會通過 equals() 方法作最後的判定。

如果 key 的 hash 值不同，後面的判斷將不會執行，直接認定兩個對象不相同。

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

五. 結束

講到這裡希望大傢對 hashCode() 與 equals() 方法能有更深入的理解，明白背後的設計思想與原理。

我之前有一個疑問，可能大傢看完這篇文章後也會有：equals() 方法平時我會用到，所以我知道它除瞭和 hashCode() 方法有密切聯系外，還有別的用途。

但是hashCode()呢？它除瞭和equals()方法有密切聯系外，還有其他用途嗎？經過在互聯網上一番搜尋，我目前給出的答案是沒有。也就是說 hashCode() 僅在散列表中才有用，在其它情況下沒用。

到此這篇關於Java 中 hashCode() 與 equals() 的關系(面試)的文章就介紹到這瞭,更多相關Java hashCode與equals內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：