資訊專(zhuān)欄INFORMATION COLUMN
摘要：當(dāng)一個(gè)值中要存儲(chǔ)到的時(shí)候會(huì)根據(jù)的值來(lái)計(jì)算出他的，通過(guò)哈希來(lái)確認(rèn)到數(shù)組的位置，如果發(fā)生哈希碰撞就以鏈表的形式存儲(chǔ)在源碼分析中解釋過(guò)，但是這樣如果鏈表過(guò)長(zhǎng)來(lái)的話，會(huì)把這個(gè)鏈表轉(zhuǎn)換成紅黑樹(shù)來(lái)存儲(chǔ)。
正文開(kāi)始 注:JDK版本為1.8
HashMap1.8和1.8之前的源碼差別很大
目錄
簡(jiǎn)介
數(shù)據(jù)結(jié)構(gòu)
類(lèi)結(jié)構(gòu)
屬性
構(gòu)造方法
增加
刪除
修改
總結(jié)
1.HashMap簡(jiǎn)介HashMap基于哈希表的Map接口實(shí)現(xiàn)，是以key-value存儲(chǔ)形式存在。（除了不同步和允許使用 null 之外，HashMap 類(lèi)與 Hashtable 大致相同。)
HashMap 的實(shí)現(xiàn)不是同步的，這意味著它不是線程安全的。它的key、value都可以為null。此外，HashMap中的映射不是有序的。在 JDK1.8 中，HashMap 是由 數(shù)組+鏈表+紅黑樹(shù)構(gòu)成，新增了紅黑樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)變得復(fù)雜了，但是效率也變的更高效。
在 JDK1.8 中，HashMap 是由 數(shù)組+鏈表+紅黑樹(shù)構(gòu)成，新增了紅黑樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)變得復(fù)雜了，但是效率也變的更高效。當(dāng)一個(gè)值中要存儲(chǔ)到Map的時(shí)候會(huì)根據(jù)Key的值來(lái)計(jì)算出他的
hash，通過(guò)哈希來(lái)確認(rèn)到數(shù)組的位置，如果發(fā)生哈希碰撞就以鏈表的形式存儲(chǔ)在Object源碼分析中解釋過(guò)，但是這樣如果鏈表過(guò)長(zhǎng)來(lái)的話，HashMap會(huì)把這個(gè)鏈表轉(zhuǎn)換成紅黑樹(shù)來(lái)存儲(chǔ)。
來(lái)看依一下HashMap的存儲(chǔ)結(jié)構(gòu)
但是這樣的話問(wèn)題來(lái)了，HashMap為什么要使用紅黑樹(shù)呢，這樣結(jié)構(gòu)的話不是更麻煩了嗎？？
這個(gè)問(wèn)題我也沒(méi)有想過(guò)，其實(shí)很多在看的時(shí)候只會(huì)在乎紅黑樹(shù)的實(shí)現(xiàn)而忽略到了為什么要使用的這個(gè)問(wèn)題，我也是在寫(xiě)本文的時(shí)候突發(fā)疑惑。參考了網(wǎng)上的例子，同時(shí)也解釋了為什么閥值為8：
因?yàn)镸ap中桶的元素初始化是鏈表保存的，其查找性能是O(n)，而樹(shù)結(jié)構(gòu)能將查找性能提升到O(log(n))。當(dāng)鏈表長(zhǎng)度很小的時(shí)候，即使遍歷，速度也非常快，但是當(dāng)鏈表長(zhǎng)度不斷變長(zhǎng)，肯定會(huì)對(duì)查詢(xún)性能有一定的影響，所以才需要轉(zhuǎn)成樹(shù)。至于為什么閾值是8，我想，去源碼中找尋答案應(yīng)該是最可靠的途徑。2.類(lèi)結(jié)構(gòu)參考地址：https://dwz.cn/nPFXmXwJ
我們來(lái)看一下類(lèi)結(jié)構(gòu)
在閱讀源碼的時(shí)候一直有個(gè)問(wèn)題很困惑就是HashMap已經(jīng)繼承了AbstractMap而AbstractMap類(lèi)實(shí)現(xiàn)了Map接口，那為什么HashMap還要在實(shí)現(xiàn)Map接口呢？同樣在ArrayList中LinkedList中都是這種結(jié)構(gòu)。
據(jù) java 集合框架的創(chuàng)始人Josh Bloch描述，這樣的寫(xiě)法是一個(gè)失誤。在java集合框架中，類(lèi)似這樣的寫(xiě)法很多，最開(kāi)始寫(xiě)java集合框架的時(shí)候，他認(rèn)為這樣寫(xiě)，在某些地方可能是有價(jià)值的，直到他意識(shí)到錯(cuò)了。顯然的，JDK的維護(hù)者，后來(lái)不認(rèn)為這個(gè)小小的失誤值得去修改，所以就這樣存在下來(lái)了。
Cloneable 空接口，表示可以克隆
Serializable 序列化
AbstractMap 提供Map實(shí)現(xiàn)接口
3.屬性初始化容量(必須是二的n次冪)
集合最大容量(必須是二的冪)
負(fù)載因子，默認(rèn)的0.75
當(dāng)鏈表的值超過(guò)8則會(huì)轉(zhuǎn)紅黑樹(shù)(1.8新增)
當(dāng)鏈表的值小于6則會(huì)從紅黑樹(shù)轉(zhuǎn)回鏈表
當(dāng)Map里面的數(shù)量超過(guò)這個(gè)值時(shí)，表中的桶才能進(jìn)行樹(shù)形化 ，否則桶內(nèi)元素太多時(shí)會(huì)擴(kuò)容，而不是樹(shù)形化 為了避免進(jìn)行擴(kuò)容、樹(shù)形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
table用來(lái)初始化(必須是二的n次冪)
用來(lái)存放緩存
HashMap中存儲(chǔ)的數(shù)量
用來(lái)記錄HashMap的修改次數(shù)
用來(lái)調(diào)整大小下一個(gè)容量的值計(jì)算方式為(容量*負(fù)載因子)
哈希表的加載因子
重點(diǎn)屬性
table 在JDK1.8中我們了解到HashMap是由數(shù)組加鏈表加紅黑樹(shù)來(lái)組成的結(jié)構(gòu)其中table就是HashMap中的數(shù)組
Size 為HashMap中K-V的實(shí)時(shí)數(shù)量
loadFactor 加載因子，是用來(lái)衡量 HashMap 滿(mǎn)的程度，計(jì)算HashMap的實(shí)時(shí)加載因子的方法為：size/capacity，而不是占用桶的數(shù)量去除以capacity。capacity 是桶的數(shù)量，也就是 table 的長(zhǎng)度length。
threshold 計(jì)算公式：capacity * loadFactor。這個(gè)值是當(dāng)前已占用數(shù)組長(zhǎng)度的最大值。過(guò)這個(gè)數(shù)目就重新resize(擴(kuò)容)，擴(kuò)容后的 HashMap 容量是之前容量的兩倍
4.構(gòu)造方法開(kāi)始看構(gòu)造方法。
4.1 HashMap()構(gòu)造一個(gè)空的 HashMap ，默認(rèn)初始容量（16）和默認(rèn)負(fù)載因子（0.75）。
4.2 HashMap(int initialCapacity)構(gòu)造一個(gè)空的 HashMap具有指定的初始容量和默認(rèn)負(fù)載因子（0.75）。
4.3 HashMap(int initialCapacity, float loadFactor)構(gòu)造一個(gè)空的 HashMap具有指定的初始容量和負(fù)載因子。我們來(lái)分析一下。
最后調(diào)用了tableSizeFor，來(lái)看一下方法實(shí)現(xiàn)：
5.增加現(xiàn)在我們開(kāi)始分析put()方法
我們可以看到put調(diào)用的是putVal來(lái)進(jìn)行數(shù)據(jù)插入，但是要注意到key在這里執(zhí)行了一下hash()方法,來(lái)看一下Hash方法是如何實(shí)現(xiàn)的。
從上面可以得知HashMap是支持Key為空的，而HashTable是直接用過(guò)Key來(lái)獲取HashCode所以key為空會(huì)拋異常其實(shí)上面就已經(jīng)解釋了為什么HashMap的長(zhǎng)度為什么要是2的冪因?yàn)镠ashMap 使用的方法很巧妙，它通過(guò) hash & (table.length -1)來(lái)得到該對(duì)象的保存位，前面說(shuō)過(guò) HashMap 底層數(shù)組的長(zhǎng)度總是2的n次方，這是HashMap在速度上的優(yōu)化。當(dāng) length 總是2的n次方時(shí)，hash & (length-1)運(yùn)算等價(jià)于對(duì) length 取模，也就是 hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)。
現(xiàn)在看putVal()方法，看看它到底做了什么。
主要參數(shù)：
hash key的hash值
key 原始Key
value 要存放的值
onlyIfAbsent 如果true代表不更改現(xiàn)有的值
evict 如果為false表示table為創(chuàng)建狀態(tài)
完整源碼分析，放圖片的話會(huì)太長(zhǎng)了，所以就截取了一下分為兩部。
暫時(shí)分析到添加 ，首發(fā)亂敲代碼公眾號(hào)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/75286.html
摘要：簡(jiǎn)介繼續(xù)分析源碼，上一篇文章把的分析完畢。本文開(kāi)始分析簡(jiǎn)單的介紹一下。存儲(chǔ)的元素是無(wú)序的并且允許使用空的元素。 1.簡(jiǎn)介 繼續(xù)分析源碼，上一篇文章把HashMap的分析完畢。本文開(kāi)始分析HashSet簡(jiǎn)單的介紹一下。 HashSet是一個(gè)無(wú)重復(fù)元素集合，內(nèi)部使用HashMap實(shí)現(xiàn)，所以HashMap的特征耶繼承了下來(lái)。存儲(chǔ)的元素是無(wú)序的并且HashSet允許使用空的元素。 HashSe...
摘要：三系列用于保存鍵值對(duì)，無(wú)論是，還是已棄用的或者線程安全的等，都是基于紅黑樹(shù)。是完全基于紅黑樹(shù)的，并在此基礎(chǔ)上實(shí)現(xiàn)了接口。可以看到，只有紅黑樹(shù)，且紅黑樹(shù)是通過(guò)內(nèi)部類(lèi)來(lái)實(shí)現(xiàn)的。 JDK容器 前言 閱讀JDK源碼有段時(shí)間了，準(zhǔn)備以博客的形式記錄下來(lái)，也方便復(fù)習(xí)時(shí)查閱，本文參考JDK1.8源碼。 一、Collection Collection是所有容器的基類(lèi)，定義了一些基礎(chǔ)方法。List、Se...
摘要：哈希表碰撞攻擊就是通過(guò)精心構(gòu)造數(shù)據(jù)，使得所有數(shù)據(jù)全部碰撞，人為將哈希表變成一個(gè)退化的單鏈表，此時(shí)哈希表各種操作的時(shí)間均提升了一個(gè)數(shù)量級(jí)，因此會(huì)消耗大量資源，導(dǎo)致系統(tǒng)無(wú)法快速響應(yīng)請(qǐng)求，從而達(dá)到拒絕服務(wù)攻擊的目的。 showImg(https://segmentfault.com/img/remote/1460000013650897); 前言 似乎所有的java面試或者考察都繞不開(kāi)has...
摘要：則使用了拉鏈?zhǔn)降纳⒘兴惴?，并在中引入了紅黑樹(shù)優(yōu)化過(guò)長(zhǎng)的鏈表。如果大家對(duì)紅黑樹(shù)感興趣，可以閱讀我的另一篇文章紅黑樹(shù)詳細(xì)分析。構(gòu)造方法構(gòu)造方法分析的構(gòu)造方法不多，只有四個(gè)。 1.概述 本篇文章我們來(lái)聊聊大家日常開(kāi)發(fā)中常用的一個(gè)集合類(lèi) - HashMap。HashMap 最早出現(xiàn)在 JDK 1.2中，底層基于散列算法實(shí)現(xiàn)。HashMap 允許 null 鍵和 null 值，在計(jì)算哈鍵的哈希值...
閱讀 4165·2021-11-24 10:46
閱讀 1954·2021-11-16 11:44
閱讀 2451·2021-09-22 16:02
閱讀 1544·2019-08-30 15:55
閱讀 1250·2019-08-30 12:46
閱讀 712·2019-08-28 18:31
閱讀 2924·2019-08-26 18:38
閱讀 1216·2019-08-23 16:51
