主頁 > 軟體設計 > 當我們創建HashMap時,底層到底做了什么?

當我們創建HashMap時,底層到底做了什么?

2020-09-10 05:36:38 軟體設計

jdk1.7中的底層實作程序(底層基于陣列+鏈表)

在我們new HashMap()時,底層創建了默認長度為16的一維陣列Entry[ ] table,當我們呼叫map.put(key1,value1)方法向HashMap里添加資料的時候:

首先,呼叫key1所在類的hashCode()計算key1的哈希值,通過key1的hash值與陣列的最大索引進行位運算以后,得到了在 Entry陣列中的存放位置:

如果此位置上的資料為空,此時的key1-value1添加成功,

如果此位置上的資料不為空(意味著此位置已經存在一個或多個資料),比較key1和已經存在的一個或多個資料的哈希值:

如果key1的哈希值與已經存在的資料的哈希值都不相同,此時key1-value1添加成功,

如果key1的哈希值與已經存在的資料的某一個資料的哈希值相同,繼續比較:呼叫key1所在類的equals()方法:

如果equals()回傳false,此時key1-value1添加成功;

如果equals()回傳true,使用value1替換value2,

需要注意的是,若原來位置已有資料,則此時key1-value1和原來的資料以鏈表的方式存盤,

在不斷的添加程序中,會涉及到擴容問題,當陣列容量大于陣列現有長度乘以加載因子(如16*0.75,默認的加載因子為0.75)的時候,就會進行陣列擴容,以減少哈希沖突(哈希沖突是指哈希函式算出來的地址被別的元素占用了),提高查詢效率,默認的擴容方式,擴容為原來容量的2倍,并將原有的資料復制過來,

jdk1.8的底層實作程序(底層基于陣列+鏈表+紅黑樹)

jdk1.8與jdk1.7中底層的創建程序相似,但有不同,首先,new HashMap()底層沒有創建出一個長度為16的陣列,在呼叫put()方法時,判斷陣列是否存在,如果不存在創建長度為16的Node[ ]陣列,接下來的程序與jdk1.7相似,最后,當某一個索引位置上的元素以鏈表形式存在的資料個數>8且當前陣列的長度>64時,此時此索引位置上的所有資料改為使用紅黑樹存盤,

在jdk1.7中,即使在“陣列容量大于陣列現有長度乘以加載因子”時擴容,也不可避免地會有哈希沖突存在,因此,在jdk1.8中引入紅黑樹是為了進一步減少哈希沖突,提高查詢效率,

紅黑樹是一種自平衡的二叉查找樹,是一種資料結構,典型的用途是實作關聯陣列,根節點必須是黑色,其他每個節點要么是紅色,要么是黑色,

結論:HashMap鍵是不能重復的,去除重復的條件是依賴鍵的hashCode方法和equals方法,如果鍵是自己的物件型別,必須要重寫hashCode方法和equals方法,否則,不能去除重復的鍵,

轉載請註明出處,本文鏈接:https://www.uj5u.com/ruanti/1014.html

標籤:面向對象

上一篇:Python里面的xlrd模塊詳解

下一篇:Mybatis的sql映射

標籤雲
其他(123570) Java(13369) Python(12729) C(7542) 區塊鏈(7372) JavaScript(7049) 基礎類(6313) AI(6244) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4120) MySQL(4012) Linux(3394) C語言(3288) C++語言(3117) Java相關(2746) 疑難問題(2699) 單片機工控(2479) Web開發(1951) 網絡通信(1793) 數據庫相關(1767) VB基礎類(1755) PHP(1727) 開發(1646) 系統維護與使用區(1617) .NETCore(1586) 基礎和管理(1579) JavaEE(1566) C++(1527) 專題技術討論區(1515) Windows客戶端使用(1484) HtmlCss(1466) ASP.NET(1428) Unity3D(1354) VCL組件開發及應用(1353) HTML(CSS)(1220) 其他技術討論專區(1200) WindowsServer(1192) .NET技术(1165) 交換及路由技術(1149) 語言基礎算法系統設計(1133) WindowsSDKAPI(1124) 界面(1088) JavaSE(1075) Qt(1074) VBA(1048) 新手樂園(1016) 其他開發語言(947) Go(907) HTML5(901) 新技術前沿(898) 硬件設計(872) 區塊鏈技術(860) 網絡編程(857) 非技術版(846) 一般軟件使用(839) 網絡協議與配置(835) Eclipse(790) Spark(750) 下載資源懸賞專區(743)

熱門瀏覽
  • 面試突擊第一季,第二季,第三季

    第一季必考 https://www.bilibili.com/video/BV1FE411y79Y?from=search&seid=15921726601957489746 第二季分布式 https://www.bilibili.com/video/BV13f4y127ee/?spm_id_fro ......

    uj5u.com 2020-09-10 05:35:24 more
  • 第三單元作業總結

    1.前言 這應該是本學期最后一次寫作業總結了吧。總體來說,對作業的節奏也差不多掌握了,作業做起來的效率也更高了。雖然和之前的作業一樣,作業中都要用到新的知識,但是相比之前,更加懂得了如何利用工具以及資料。雖然之間卡過殼,但總體而言,這幾次作業還算完成的比較好。 2.作業程序總結 相比前兩個單元,此單 ......

    uj5u.com 2020-09-10 05:35:41 more
  • 北航OO(2020)第四單元博客作業暨課程總結博客

    北航OO(2020)第四單元博客作業暨課程總結博客 本單元作業的架構設計 在本單元中,由于UML圖具有比較清晰的樹形結構,因此我對其中需要進行查詢操作的元素進行了包裝,在樹的父節點中存盤所有孩子的參考。考慮到性能問題,我采用了快取機制,一次查詢后盡可能快取已經遍歷過的資訊,以減少遍歷次數。 本單元我 ......

    uj5u.com 2020-09-10 05:35:48 more
  • BUAA_OO_第四單元

    一、UML決議器設計 ? 先看下題目:第四單元實作一個基于JDK 8帶有效性檢查的UML(Unified Modeling Language)類圖,順序圖,狀態圖分析器 MyUmlInteraction,實際上我們要建立一個有向圖模型,UML中的物件(元素)可能與同級元素連接,也可與低級元素相連形成 ......

    uj5u.com 2020-09-10 05:35:54 more
  • 6.1邏輯運算子

    邏輯運算子 1. && 短路與 運算式1 && 運算式2 01.運算式1為true并且運算式2也為true 整體回傳為true 02.運算式1為false,將不會執行運算式2 整體回傳為false 03.只要有一個運算式為false 整體回傳為false 2. || 短路或 運算式1 || 運算式2 ......

    uj5u.com 2020-09-10 05:35:56 more
  • BUAAOO 第四單元 & 課程總結

    1. 第四單元:StarUml檔案決議 本單元采用了圖模型決議UML。 UML檔案可以抽象為圖、子圖、邊的邏輯結構。 在實作中,圖的節點包括類、介面、屬性,子圖包括狀態圖、順序圖等。 采用了三次遍歷UML元素的方法建圖,第一遍遍歷建點,第二、三次遍歷設定屬性、連邊,實作圖物件的初始化。這里借鑒了一些 ......

    uj5u.com 2020-09-10 05:36:06 more
  • 談談我對C# 多型的理解

    面向物件三要素:封裝、繼承、多型。 封裝和繼承,這兩個比較好理解,但要理解多型的話,可就稍微有點難度了。今天,我們就來講講多型的理解。 我們應該經常會看到面試題目:請談談對多型的理解。 其實呢,多型非常簡單,就一句話:呼叫同一種方法產生了不同的結果。 具體實作方式有三種。 一、多載 多載很簡單。 p ......

    uj5u.com 2020-09-10 05:36:09 more
  • Python 資料驅動工具:DDT

    背景 python 的unittest 沒有自帶資料驅動功能。 所以如果使用unittest,同時又想使用資料驅動,那么就可以使用DDT來完成。 DDT是 “Data-Driven Tests”的縮寫。 資料:http://ddt.readthedocs.io/en/latest/ 使用方法 dd. ......

    uj5u.com 2020-09-10 05:36:13 more
  • Python里面的xlrd模塊詳解

    那我就一下面積個問題對xlrd模塊進行學習一下: 1.什么是xlrd模塊? 2.為什么使用xlrd模塊? 3.怎樣使用xlrd模塊? 1.什么是xlrd模塊? ?python操作excel主要用到xlrd和xlwt這兩個庫,即xlrd是讀excel,xlwt是寫excel的庫。 今天就先來說一下xl ......

    uj5u.com 2020-09-10 05:36:28 more
  • 當我們創建HashMap時,底層到底做了什么?

    jdk1.7中的底層實作程序(底層基于陣列+鏈表) 在我們new HashMap()時,底層創建了默認長度為16的一維陣列Entry[ ] table。當我們呼叫map.put(key1,value1)方法向HashMap里添加資料的時候: 首先,呼叫key1所在類的hashCode()計算key1 ......

    uj5u.com 2020-09-10 05:36:38 more
最新发布
  • 想在$(document).ready()中使用函式

    我有一個類似的問題之前,我的問題是關于如何在網路瀏覽器控制臺中訪問所有的JavaScript函式,即使它們在window.onload = function() {//code and functions}內,但這次我想用jQu...

    uj5u.com 2021-10-16 15:31:25 more
  • 在AndroidStudio中允許HTTP下載

    我在Android Studio中得到了以下錯誤: > Could not download builder-4.1.2.jar (com.android.tools.build:builder:4.1.2)
    > 無法下載 builder-4.1.2.jar(com.android.tools....

    uj5u.com 2021-10-16 15:31:06 more
  • 如何抑制gradle關于DeprecatedGradle特性的警告?

    我使用的是最新的Gradle v7.2。
    當我編譯的時候,它給了我一個警告...

    uj5u.com 2021-10-16 15:30:48 more
  • Gradle7.2Java17Build問題java.lang.NullPointerException。無法

    > Task :compileJava
    注意:有些輸入檔案使用或覆寫了已廢棄的API。
    注意:用-Xlint:deprecation for詳細資訊進行重新編譯。
    在編譯器 (17)中發生了一個例外。請通過Java錯誤...

    uj5u.com 2021-10-16 15:30:05 more
  • 為什么我在JUnit4中得到這個例外?

    我是JUnit測驗和Gradle的新手,我試著做了我的第一個簡單的測驗,但它們并不作業。
    這是我的測驗代碼: 這是我的測驗代碼。
    import org.junit.Test;
    import static org.junit.Ass...

    uj5u.com 2021-10-16 15:28:38 more
  • 在模擬類中使用pytest夾具

    我需要使用一個夾具,在一個將用于模擬第三方庫的類中準備一些資料。現在,我有一個相當于這樣的方案: )
    def file(tmpdir_factory)。
    ""創建一個模擬檔案的長程序。""。
    ....

    uj5u.com 2021-10-16 15:27:47 more
  • 不能在型別引數化方法中隱含地將子類轉換為父類

    我最近不得不幫助解決某人在從泛型方法中回傳時遇到的問題,雖然有多個問題需要解決,但我理解并能解釋所有問題--除了讓編譯器接受回傳型別這一最后障礙。盡管我最終成功地讓程...

    uj5u.com 2021-10-16 15:27:39 more
  • JavaObjectMapper.readValue將通用型別變成LinkedHashMap

    @Service
    public class PokemonManager implements PokemonService {

    private HttpResponse<String> getStringHttpResponseByUrl(final String url) {
    HttpCli...

    uj5u.com 2021-10-16 15:26:15 more
  • 如何創建一個通用結構?

    我如何構建一個通用結構?
    我試過:
    type SafeSet[type T] struct {
    值 map[T]bool bool ?
    }



    我希望能夠做到例如 我希望能夠做到例如
    SafeSet{ Values: make(map[net.Co...

    uj5u.com 2021-10-16 15:25:33 more
  • 通用類在mutableMap中的轉換

    在我的應用程式中,我想做這樣的事情: 在我的應用程式中,我想做這樣的事情。
    interface Binder<in VB: ViewBinding, in T: Any> /span>{
    fun bind(binding。VB, item: T)
    }...

    uj5u.com 2021-10-16 15:23:51 more