概述

①以數(shù)組+鏈表+紅黑樹(shù)實(shí)現(xiàn)。主要用來(lái)處理具有鍵值對(duì)特征的數(shù)據(jù)。
②當(dāng)鏈表長(zhǎng)度大于閾值（或者紅黑樹(shù)的邊界值，默認(rèn)為 8 ）并且當(dāng)前數(shù)組的長(zhǎng)度大于 64 時(shí)，此時(shí)此索引位置上的所有數(shù)據(jù)改為使用紅黑樹(shù)存儲(chǔ)。
③補(bǔ)充：將鏈表轉(zhuǎn)換成紅黑樹(shù)前會(huì)判斷，即便閾值大于 8，但是數(shù)組長(zhǎng)度小于 64，此時(shí)并不會(huì)將鏈表變?yōu)榧t黑樹(shù)，而是選擇逬行數(shù)組擴(kuò)容。
④每個(gè)Node節(jié)點(diǎn)存儲(chǔ)著用來(lái)定位數(shù)據(jù)索引位置的hash值，K鍵，V值以及指向鏈表下一個(gè)節(jié)點(diǎn)的Node<K,V> next節(jié)點(diǎn)組成。
⑤Node是HashMap的內(nèi)部類，實(shí)現(xiàn)了Map.Entry接口，本質(zhì)是一個(gè)鍵值對(duì)。
⑥這樣做的目的是因?yàn)閿?shù)組比較小，盡量避開(kāi)紅黑樹(shù)結(jié)構(gòu)，這種情況下變?yōu)榧t黑樹(shù)結(jié)構(gòu)，反而會(huì)降低效率，因?yàn)榧t黑樹(shù)需要逬行左旋，右旋，變色這些操作來(lái)保持平衡。同時(shí)數(shù)組長(zhǎng)度小于64時(shí)，搜索時(shí)間相對(duì)要快些。所以結(jié)上所述為了提高性能和減少搜索時(shí)間，底層閾值大于8并且數(shù)組長(zhǎng)度大于64時(shí)，鏈表才轉(zhuǎn)換為紅黑樹(shù)。

重要的參數(shù)

①容量(Capacity)和負(fù)載因子(Load factor）
②初始容量：容量是哈希表中桶的個(gè)數(shù)，初始容量是創(chuàng)建哈希表時(shí)的容量。
③負(fù)載因子：負(fù)載因子是衡量哈希表在自動(dòng)增加容量之前允許其達(dá)到多滿的指標(biāo)。 默認(rèn)0.75
④threshold：threshold表示所能容納的鍵值對(duì)的臨界值。計(jì)算公式為 數(shù)組長(zhǎng)度 * 負(fù)載因子。
⑤size：size是hashmap中實(shí)際存在的鍵值對(duì)數(shù)量。
⑥modCount：用來(lái)記錄hashmap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)。

put函數(shù)的實(shí)現(xiàn)

大致思路：

對(duì)key的hashCode()做hash，然后再計(jì)算index;
如果沒(méi)碰撞直接放到bucket里；
如果碰撞了，以鏈表的形式存在buckets后；
如果碰撞導(dǎo)致鏈表過(guò)長(zhǎng)(大于等于 TREEIFY_THRESHOLD )就把鏈表轉(zhuǎn)換成紅黑樹(shù)；
如果節(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)
如果bucket滿了(超過(guò) load factor*current capacity )，就要resize(調(diào)整大小)。

get函數(shù)的實(shí)現(xiàn)

大致思路：

• bucket里的第一個(gè)節(jié)點(diǎn)，直接命中；
• 如果有沖突，則通過(guò)key.equals(k)去查找對(duì)應(yīng)的entry若為樹(shù)，則在樹(shù)中通過(guò)key.equals(k)查找，O(logn)；若為鏈表，則在鏈表中通過(guò)key.equals(k)查找，O(n)。

hash函數(shù)的實(shí)現(xiàn)

//高16bit不變，低16bit和高16bit做了一個(gè)異或
static final int hash(Object key) {
?? ?int h;
?? ?return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

獲取HashMap的元素時(shí)，基本分兩步：

• 1.首先根據(jù)hashCode()做hash，然后確定bucket的index；
• 2.如果bucket的節(jié)點(diǎn)的key不是我們需要的，則通過(guò)keys.equals()在鏈表(紅黑樹(shù))中找。

RESIZE的實(shí)現(xiàn)

當(dāng)put時(shí)，如果發(fā)現(xiàn)目前的bucket占用程度已經(jīng)超過(guò)了Load Factor所希望的比例，那么就會(huì)發(fā)生resize。

在resize的過(guò)程，簡(jiǎn)單的說(shuō)就是把bucket擴(kuò)充為2倍，之后重
新計(jì)算index，把節(jié)點(diǎn)再放到新的bucket中。元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置。省去了重新計(jì)算hash值的時(shí)間，把之前的沖突的節(jié)點(diǎn)分散到新的bucket了

什么時(shí)候會(huì)使用HashMap？他有什么特點(diǎn)？

是基于Map接口的實(shí)現(xiàn)，存儲(chǔ)鍵值對(duì)時(shí)，它可以接收null的鍵值，是非同步的，HashMap存儲(chǔ)著Entry(hash, key, value, next)對(duì)象。
** 你知道HashMap的工作原理嗎？**
通過(guò)hash的方法，通過(guò)put和get存儲(chǔ)和獲取對(duì)象。存儲(chǔ)對(duì)象時(shí)，我們將K/V傳給put方法時(shí)，它調(diào)用hashCode計(jì)算hash從而得到bucket位置，進(jìn)一步存儲(chǔ)，HashMapJava集合——HashMap會(huì)根據(jù)當(dāng)前bucket的占用情況自動(dòng)調(diào)整容量(超過(guò) Load Facotr 則resize為原來(lái)的2倍)。獲取對(duì)象時(shí)，我們將K傳給get，它調(diào)用hashCode計(jì)算hash從而得到bucket位置，并進(jìn)一步調(diào)用equals()方法確定鍵值對(duì)。如果發(fā)生碰撞的時(shí)候，Hashmap通過(guò)鏈表將產(chǎn)生碰撞沖突的元素組織起來(lái)，在Java 8中，如果一個(gè)bucket中碰撞沖突的元素超過(guò)某個(gè)限制(默認(rèn)是8)，則使用紅黑樹(shù)來(lái)替換鏈表，從而提高速度。

你知道get和put的原理嗎？equals()和hashCode()的都有什么作用？

通過(guò)對(duì)key的hashCode()進(jìn)行hashing，并計(jì)算下標(biāo)( (n-1) & hash )，從而獲得buckets的位置。如果產(chǎn)生碰撞，則利用key.equals()方法去鏈表或樹(shù)中去查找對(duì)應(yīng)的節(jié)點(diǎn)。

hash的實(shí)現(xiàn)，為什么要這樣實(shí)現(xiàn)？

在Java 1.8的實(shí)現(xiàn)中，是通過(guò)hashCode()的高16位異或低16位實(shí)現(xiàn)的： (h =k.hashCode()) ^ (h >>> 16) ，主要是從速度、功效、質(zhì)量來(lái)考慮的，這么做可以在bucket的n比較小的時(shí)候，也能保證考慮到高低bit都參與到hash的計(jì)算中，同時(shí)不會(huì)有太大的開(kāi)銷。

如果HashMap的大小超過(guò)了負(fù)載因子( load factor )定義的容量，怎么辦？

如果超過(guò)了負(fù)載因子(默認(rèn)0.75)，則會(huì)重新resize一個(gè)原來(lái)長(zhǎng)度兩倍的HashMap，并且重新調(diào)用hash方法。

到此這篇關(guān)于Java集合-HashMap的文章就介紹到這了,更多相關(guān)Java集合HashMap內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論