深入探究Java中hashCode()和equals()的關係

来源:https://www.cnblogs.com/tanshaoshenghao/archive/2019/05/23/10915055.html
-Advertisement-
Play Games

[toc] 一. 基礎: hashCode()和equals()簡介 在學習hashCode()和equals()之間的關係之前, 我們有必要先單獨瞭解他倆自身的特點. equals()方法用於比較兩個對象是否相等, 它與"=="相等比較符有著本質的不同. 在萬物皆對象的Java體系中, 系統把判斷 ...


目錄

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

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

  • equals()方法用於比較兩個對象是否相等, 它與"=="相等比較符有著本質的不同. 在萬物皆對象的Java體系中, 系統把判斷對象是否相等的權力交給程式員, 具體的措施是把equals()方法寫入到Object類中, 並讓所有類繼承Object類. 這樣程式員就能在類中自定義equals()方法, 從而實現自己的業務邏輯.
  • 關於equals()和"=="的區別你可以--參考這篇文章--

 

  • 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()之間的關係.

  • 上面提到Set和Map不存放重覆的元素(key), 那麼在存儲元素的時候就必須對元素做出判斷: 在當前的容器中有沒有和新元素相同的元素?.
  • 你可能會想: 這容易呀, 直接調用元素對象的equals()方法進行比較不就行了嗎? 如果容器中的存儲的對象數量較少, 這確實是個好主意, 但是如果容器中存放的對象達到了一定的規模, 要調用容器中所有對象的equals()方法和新元素進行比較就不是一件容易的事情了, 就算equals()方法的比較邏輯簡單無比, 這也是一個時間複雜度為O(n)的操作啊.

 

  • 但在散列表的基礎上判斷"新對象是否和容器中任一對象相同"就容易得多了. 由於每個對象都自帶有hashCode(), 這個hashCode將會用作散列表哈希函數的輸入, hashCode經過哈希函數計算後得到哈希值, 新對象根據哈希值存儲到相應的記憶體的單元.
  • 我們不妨假設兩個相同的對象, hashCode()一定相同, 這麼一來就體現出哈希函數的威力了, 由於相同的輸入一定會產生相同的輸出, 於是如果新對象和容器中已存在的對象相同, 新對象計算出的哈希值就會和已存在的對象的哈希值產生衝突, 這時容器就能判斷: 這個新加入的元素已經存在, 需要另作處理(覆蓋掉原來的元素(key)或捨棄).
  • 按照這個思路, 如果這個元素計算出的哈希值所對應的地址沒有產生衝突, 也就是沒有重覆的元素, 那麼它就可以直接插入. 所以當運用hashCode()時, 判斷是否有相同元素的代價只是一次哈希計算, 時間複雜度為O(1), 這極大地提高了數據的存儲性能.

 

  • 但是前面我們還提到: 當輸入樣本量足夠大時, 不相同的輸入是會產生相同輸出的, 也就是形成哈希衝突. 這麼一來就麻煩了, 原來我們設定的"如果產生衝突, 就意味著兩個對象相同"的規則瞬間被打破, 產生衝突的很有可能是兩個不同的對象!
  • 而令人欣慰的是我們除了hashCode()方法, 還有一張王牌: equals()方法. 也就是說當兩個不相同的對象產生哈希衝突後, 我們可以用equals()方法進一步判斷兩個對象是否相同. 這時equals()方法就相當重要了, 這個情況下它必須要能判定這兩個對象是不相同的.
  • 講到這裡就引出了Java程式設計中一些重要原則:
  • 如果兩個對象是相等的, 它們的equals()方法應該要返回true, 它們的hashCode()需要返回相同的結果.
  • 但有時候面試題不會問得這麼直接, 它會問你:兩個對象的hashCdoe()相同, 它的equals()方法一定要返回true, 對嗎?
  • 那答案肯定不對. 因為我們不能保證每個程式設計者都會遵循編碼規則, 有可能兩個不同對象的hashCode()會返回相同的結果. 如果你理解上面的內容, 這個問題就很好解答: 兩個對象的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後端面試題分析, 將會囊括Java基礎知識到主流框架原理. 還會分享關於編程的趣味漫畫.

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 伺服器免密登錄
    伺服器免密登錄 由於有多台伺服器，每次登錄還需要 去找對應的伺服器地址，然後輸入密碼，為了避免麻煩，就使用了免密登錄。普通登錄方式： ssh -p 22 [email protected] 每次登錄還需要輸入密碼，比較麻煩 更換免密碼登錄： 本地操作： 本地的公鑰位置： ~/.ssh/i... ...
  • php高併發之opcache
    今天工作的時候接觸到客戶的一臺伺服器，業務邏輯比較簡單 。估算pv在120w左右吧，用的是阿裡雲2c4g的伺服器。一大早就開始卡頓了，登陸伺服器後查看負載到了八九十。 之後就想辦法調整一下吧。突然想起某位前輩說過的：開啟opcache吧，真的會變快的。 於是我馬上就開始整，過程很簡單 1.進入php ...
  • Java環境的配置
    對於Java初學者，可能會面對這麼一個問題，Java環境的配置，那麼廢話少說，直接開始。首先找到jdk的安裝包（我這邊以jdk1.8為例），雙擊安裝。 到這邊我們的jdk已經成功安裝，但這樣我們有些同學的eclipse依然沒法使用，那是因為eclipse需要配置jdk才能正常使用，下麵開始配置jdk ...
  • C++中多態的概念和意義
    1，函數重寫回顧： 1，父類中被重寫的函數依然會繼承給子類； 2，子類中重寫的函數將覆蓋父類中的函數； 1，重寫父類當中提供的函數是因為父類當中提供的這個函數版本不能滿足我們的需求，因此我們要重寫； 2，期望只要是子類對象，則調用子類當中的版本，而不是父類當中定義的函數版本； 3，通過作用域分辨符（ ...
  • 死磕 java同步系列之自己動手寫一個鎖Lock
    自己動手寫一個鎖需要哪些知識？ 自己動手寫一個鎖到底有多簡單？ 自己能不能寫出來一個完美的鎖？ ...
  • C++繼承中的同名覆蓋
    1，父子間的衝突是由繼承帶來的，兩個類之間存在了繼承的關係，必然的會帶來一 些問題，本文要討論的是父子之間成員變數或成員函數的命名問題； 2，思考： 1，子類中是否可以定義父類中的同名成員？ 1，可以，本文先編程解決這個問題； 2，這個問題就是同名覆蓋問題； 2，如果可以，如何區分？如果不可以，為什 ...
  • python正則表達式入門篇
    <!--done--> 文章來源於：https://www.cnblogs.com/chuxiuhong/p/5885073.html Python 正則表達式入門（初級篇） 本文主要為沒有使用正則表達式經驗的新手入門所寫。 轉載請寫明出處 引子 首先說 正則表達式是什麼？ 正則表達式，又稱正規表示 ...
  • [NOI2006] 網路收費
    賊有意思的一道題。考慮把費用給轉化一下，觀察 如果定義葉節點的狀態 {{A,0},{B,1}}，非葉節點的狀態 {{nA =nB,0},{nA define ls (x 1; int key=!(1&(set (dep i))); //相異有貢獻 if(l 1,len=r l+1; lq[dep]= ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類