成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

HashMap就是這么簡(jiǎn)單【源碼剖析】

entner / 878人閱讀

前言 
聲明，本文用得是jdk1.8

前面已經(jīng)講了Collection的總覽和剖析List集合以及散列表、Map集合、紅黑樹(shù)的基礎(chǔ)了：

Collection總覽

List集合就這么簡(jiǎn)單【源碼剖析】

Map集合、散列表、紅黑樹(shù)介紹

本篇主要講解HashMap，以及涉及到一些與hashtable的比較~

看這篇文章之前最好是有點(diǎn)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)：

Java實(shí)現(xiàn)單向鏈表

棧和隊(duì)列就是這么簡(jiǎn)單

二叉樹(shù)就這么簡(jiǎn)單

當(dāng)然了，如果講得有錯(cuò)的地方還請(qǐng)大家多多包涵并不吝在評(píng)論去指正～

一、HashMap剖析

首先看看HashMap的頂部注釋說(shuō)了些什么：

再來(lái)看看HashMap的類繼承圖：

下面我們來(lái)看一下HashMap的屬性：

成員屬性有這么幾個(gè)：

再來(lái)看一下hashMap的一個(gè)內(nèi)部類Node：

我們知道Hash的底層是散列表，而在Java中散列表的實(shí)現(xiàn)是通過(guò)數(shù)組+鏈表的~

再來(lái)簡(jiǎn)單看看put方法就可以印證我們的說(shuō)法了：數(shù)組+鏈表-->散列表

我們可以簡(jiǎn)單總結(jié)出HashMap：

無(wú)序，允許為null，非同步

底層由散列表(哈希表)實(shí)現(xiàn)

初始容量和裝載因子對(duì)HashMap影響挺大的，設(shè)置小了不好，設(shè)置大了也不好

1.1HashMap構(gòu)造方法

HashMap的構(gòu)造方法有4個(gè)：

在上面的構(gòu)造方法最后一行，我們會(huì)發(fā)現(xiàn)調(diào)用了tableSizeFor()，我們進(jìn)去看看：

這是位運(yùn)算算法，具體流程可參考：

https://www.cnblogs.com/loading4/p/6239441.html

https://blog.csdn.net/fan2012huan/article/details/51097331

看完上面可能會(huì)感到奇怪的是：為啥是將2的整數(shù)冪的數(shù)賦給threshold？

threshold這個(gè)成員變量是閾值，決定了是否要將散列表再散列。它的值應(yīng)該是：capacity * load factor才對(duì)的。

其實(shí)這里僅僅是一個(gè)初始化，當(dāng)創(chuàng)建哈希表的時(shí)候，它會(huì)重新賦值的：

至于別的構(gòu)造方法都差不多，這里我就不細(xì)講了：

1.2put方法

put方法可以說(shuō)是HashMap的核心，我們來(lái)看看：

我們來(lái)看看它是怎么計(jì)算哈希值的：

為什么要這樣干呢？？我們一般來(lái)說(shuō)直接將key作為哈希值不就好了嗎，做異或運(yùn)算是干嘛用的？？

我們看下來(lái)：

我們是根據(jù)key的哈希值來(lái)保存在散列表中的，我們表默認(rèn)的初始容量是16，要放到散列表中，就是0-15的位置上。也就是tab[i = (n - 1) & hash]?？梢园l(fā)現(xiàn)的是：在做&運(yùn)算的時(shí)候，僅僅是后4位有效~那如果我們key的哈希值高位變化很大，低位變化很小。直接拿過(guò)去做&運(yùn)算，這就會(huì)導(dǎo)致計(jì)算出來(lái)的Hash值相同的很多。

而設(shè)計(jì)者將key的哈希值的高位也做了運(yùn)算(與高16位做異或運(yùn)算，使得在做&運(yùn)算時(shí)，此時(shí)的低位實(shí)際上是高位與低位的結(jié)合)，這就增加了隨機(jī)性，減少了碰撞沖突的可能性！

下面我們?cè)賮?lái)看看流程是怎么樣的：

新值覆蓋舊值，返回舊值測(cè)試：

接下來(lái)我們看看resize()方法，在初始化的時(shí)候要調(diào)用這個(gè)方法，當(dāng)散列表元素大于capacity * load factor的時(shí)候也是調(diào)用resize()

1.3get方法

接下來(lái)我們看看getNode()是怎么實(shí)現(xiàn)的：

1.4remove方法

再來(lái)看看removeNode()的實(shí)現(xiàn)：

二、HashMap與Hashtable對(duì)比 
從存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)來(lái)講基本上都是相同的。它和HashMap的最大的不同是它是線程安全的，另外它不允許key和value為null。Hashtable是個(gè)過(guò)時(shí)的集合類，不建議在新代碼中使用，不需要線程安全的場(chǎng)合可以用HashMap替換，需要線程安全的場(chǎng)合可以用ConcurrentHashMap替換

Hashtable具體閱讀源碼可參考：

https://blog.csdn.net/panweiwei1994/article/details/77427010

https://blog.csdn.net/panweiwei1994/article/details/77428710

四、總結(jié)

在JDK8中HashMap的底層是：數(shù)組+鏈表(散列表)+紅黑樹(shù)

在散列表中有裝載因子這么一個(gè)屬性，當(dāng)裝載因子*初始容量小于散列表元素時(shí)，該散列表會(huì)再散列，擴(kuò)容2倍！

裝載因子的默認(rèn)值是0.75，無(wú)論是初始大了還是初始小了對(duì)我們HashMap的性能都不好

裝載因子初始值大了，可以減少散列表再散列(擴(kuò)容的次數(shù))，但同時(shí)會(huì)導(dǎo)致散列沖突的可能性變大(散列沖突也是耗性能的一個(gè)操作，要得操作鏈表(紅黑樹(shù))！

裝載因子初始值小了，可以減小散列沖突的可能性，但同時(shí)擴(kuò)容的次數(shù)可能就會(huì)變多！

初始容量的默認(rèn)值是16，它也一樣，無(wú)論初始大了還是小了，對(duì)我們的HashMap都是有影響的：

初始容量過(guò)大，那么遍歷時(shí)我們的速度就會(huì)受影響~

初始容量過(guò)小，散列表再散列(擴(kuò)容的次數(shù))可能就變得多，擴(kuò)容也是一件非常耗費(fèi)性能的一件事~

從源碼上我們可以發(fā)現(xiàn)：HashMap并不是直接拿key的哈希值來(lái)用的，它會(huì)將key的哈希值的高16位進(jìn)行異或操作，使得我們將元素放入哈希表的時(shí)候增加了一定的隨機(jī)性。

還要值得注意的是：并不是桶子上有8位元素的時(shí)候它就能變成紅黑樹(shù)，它得同時(shí)滿足我們的散列表容量大于64才行的~

明天要是無(wú)意外的話，可能會(huì)寫(xiě)TreeMap，敬請(qǐng)期待哦~~~~

文章的目錄導(dǎo)航：https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li

如果文章有錯(cuò)的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y。為了大家方便，剛新建了一下qq群：742919422，大家也可以去交流交流。
謝謝支持了！希望能多介紹給其他有需要的朋友

參考資料：

《Core Java》

https://blog.csdn.net/panweiwei1994/article/details/76555359

https://zhuanlan.zhihu.com/p/28216267

https://blog.csdn.net/fan2012huan/article/details/51097331

https://www.cnblogs.com/chinajava/p/5808416.html

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69009.html

相關(guān)文章

  • 3分鐘搞掂Set集合

    摘要：下面總結(jié)一下集合常用的三個(gè)子類吧無(wú)序，允許為，底層是散列表紅黑樹(shù)，非線程同步有序，不允許為，底層是紅黑樹(shù)非線程同步迭代有序，允許為，底層是雙向鏈表，非線程同步從結(jié)論而言我們就可以根據(jù)自己的實(shí)際情況來(lái)使用了。 前言 聲明，本文用的是jdk1.8 前面章節(jié)回顧： Collection總覽 List集合就這么簡(jiǎn)單【源碼剖析】 Map集合、散列表、紅黑樹(shù)介紹 HashMap就是這么簡(jiǎn)單【源碼...

    widuu 評(píng)論0 收藏0

  • LinkedHashMap就這么簡(jiǎn)單【源碼剖析】

    摘要：習(xí)慣在微信看技術(shù)文章，想要獲取更多的資源的同學(xué)，可以關(guān)注微信公眾號(hào)。為了大家方便，剛新建了一下群，大家也可以去交流交流。謝謝支持了希望能多介紹給其他有需要的朋友 前言 聲明，本文用得是jdk1.8 前面已經(jīng)講了Collection的總覽和剖析List集合以及散列表、Map集合、紅黑樹(shù)還有HashMap基礎(chǔ)了： Collection總覽 List集合就這么簡(jiǎn)單【源碼剖析】 Map集合、...

    avwu 評(píng)論0 收藏0

  • ConcurrentHashMap基于JDK1.8源碼剖析

    摘要：下面我來(lái)簡(jiǎn)單總結(jié)一下的核心要點(diǎn)底層結(jié)構(gòu)是散列表數(shù)組鏈表紅黑樹(shù)，這一點(diǎn)和是一樣的。是將所有的方法進(jìn)行同步，效率低下。而作為一個(gè)高并發(fā)的容器，它是通過(guò)部分鎖定算法來(lái)進(jìn)行實(shí)現(xiàn)線程安全的。 前言 聲明，本文用的是jdk1.8 前面章節(jié)回顧： Collection總覽 List集合就這么簡(jiǎn)單【源碼剖析】 Map集合、散列表、紅黑樹(shù)介紹 HashMap就是這么簡(jiǎn)單【源碼剖析】 LinkedHas...

    sanyang 評(píng)論0 收藏0

  • Java集合總結(jié)【面試題+腦圖】，將知識(shí)點(diǎn)一網(wǎng)打盡！

    摘要：而在集合中，值僅僅是一個(gè)對(duì)象罷了該對(duì)象對(duì)本身而言是無(wú)用的。將這篇文章作為集合的總結(jié)篇，但覺(jué)得沒(méi)什么好寫(xiě)就回答一些面試題去了，找了一會(huì)面試題又覺(jué)得不夠系統(tǒng)。 前言 聲明，本文用的是jdk1.8 花了一個(gè)星期，把Java容器核心的知識(shí)過(guò)了一遍，感覺(jué)集合已經(jīng)無(wú)所畏懼了！！(哈哈哈....)，現(xiàn)在來(lái)總結(jié)一下吧~~ 回顧目錄： Collection總覽 List集合就這么簡(jiǎn)單【源碼剖析】 Ma...

    yearsj 評(píng)論0 收藏0

  • TreeMap就這么簡(jiǎn)單【源碼剖析】

    摘要：在這種情況下，是以其為根的樹(shù)的最后一個(gè)結(jié)點(diǎn)。來(lái)源二總結(jié)底層是紅黑樹(shù)，能夠?qū)崿F(xiàn)該集合有序如果在構(gòu)造方法中傳遞了對(duì)象，那么就會(huì)以對(duì)象的方法進(jìn)行比較。 前言 聲明，本文用得是jdk1.8 前面章節(jié)回顧： Collection總覽 List集合就這么簡(jiǎn)單【源碼剖析】 Map集合、散列表、紅黑樹(shù)介紹 HashMap就是這么簡(jiǎn)單【源碼剖析】 LinkedHashMap就這么簡(jiǎn)單【源碼剖析】 本...

    ormsf 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<