HashMap
作為我們最常用的數(shù)據(jù)類型,當(dāng)然有必要了解一下他內(nèi)部是實(shí)現(xiàn)細(xì)節(jié)。相比于 JDK7 在JDK8 中引入了紅黑樹(shù)以及hash計(jì)算等方面的優(yōu)化,使得 JDK8 中的HashMap
效率要高于以往的所有版本,本文會(huì)詳細(xì)介紹相關(guān)的優(yōu)化,但是主要還是寫(xiě) JDK8 的源碼。
在海晏等地區(qū),都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局,加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力,以專注、極致的服務(wù)理念,為客戶提供做網(wǎng)站、成都做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作按需設(shè)計(jì)網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),營(yíng)銷型網(wǎng)站建設(shè),成都外貿(mào)網(wǎng)站建設(shè),海晏網(wǎng)站建設(shè)費(fèi)用合理。
public?class?HashMap<K,V>?extends?AbstractMap<K,V>??implements?Map<K,V>,?Cloneable,?Serializable?{}
可以看到HashMap
是完全基于Map
接口實(shí)現(xiàn)的,其中AbstractMap
是Map
接口的骨架實(shí)現(xiàn),提供了Map
接口的最小實(shí)現(xiàn)。HashMap
看名字也能猜到,他是基于哈希表實(shí)現(xiàn)的(數(shù)組+鏈表+紅黑樹(shù)):
public?HashMap(int?initialCapacity)public?HashMap()public?HashMap(Map<??extends?K,???extends?V>?m)public?HashMap(int?initialCapacity,?float?loadFactor)?{??if?(initialCapacity?<?0)????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+?initialCapacity);??if?(initialCapacity?>?MAXIMUM_CAPACITY) ????initialCapacity?=?MAXIMUM_CAPACITY;??if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+?loadFactor);??this.loadFactor?=?loadFactor;??this.threshold?=?tableSizeFor(initialCapacity); }
HashMap
一共有四個(gè)構(gòu)造函數(shù),其主要作用就是初始化loadFactor
和threshold
兩個(gè)參數(shù):
threshold:擴(kuò)容的閾值,當(dāng)放入的鍵值對(duì)大于這個(gè)閾值的時(shí)候,就會(huì)發(fā)生擴(kuò)容;
loadFactor:負(fù)載系數(shù),用于控制閾值的大小,即threshold = table.length * loadFactor
;默認(rèn)情況下負(fù)載系數(shù)等于0.75,當(dāng)它值越大時(shí):哈希桶空余的位置越少,空間利用率越高,同時(shí)哈希沖突也就越嚴(yán)重,效率也就越低;相反它值越小時(shí):空間利用率越低,效率越高;而0.75是對(duì)于空間和效率的一個(gè)平衡,通常情況下不建議修改;
但是對(duì)于上面構(gòu)造函數(shù)當(dāng)中this.threshold = tableSizeFor(initialCapacity);
,這里的閾值并沒(méi)有乘以負(fù)載系數(shù),是因?yàn)樵跇?gòu)造函數(shù)當(dāng)中哈希桶table[]
還沒(méi)有初始化,在往里put數(shù)據(jù)的時(shí)候才會(huì)初始化,而tableSizeFor
是為了得到大于等于initialCapacity
的最小的2的冪;
transient?Node<K,V>[]?table;????????????//?哈希桶transient?Set<Map.Entry<K,V>>?entrySet;?//?映射關(guān)系Set視圖transient?int?size;?????????????????????//?鍵值對(duì)的數(shù)量transient?int?modCount;?????????????????//?結(jié)構(gòu)修改次數(shù),用于實(shí)現(xiàn)fail-fast機(jī)制
哈希桶的結(jié)構(gòu)如下:
static?class?Node<K,V>?implements?Map.Entry<K,V>?{??final?int?hash;???????//?用于尋址,避免重復(fù)計(jì)算 ??final?K?key; ??V?value; ??Node<K,V>?next; ??...??public?final?int?hashCode()?{????return?Objects.hashCode(key)?^?Objects.hashCode(value); ??} }
其中Node<K,V> next
還有一個(gè)TreeNode
子類用于實(shí)現(xiàn)紅黑樹(shù),需要注意的是這里的hashCode()
所計(jì)算的hash值只用于在遍歷的時(shí)候獲取hash值,并非尋址所用hash;
既然是Hash表,那么最重要的肯定是尋址了,在HashMap
中采用的是除留余數(shù)法,即table[hash % length]
,但是在現(xiàn)代CPU中求余是最慢的操作,所以人們想到一種巧妙的方法來(lái)優(yōu)化它,即length為2的指數(shù)冪時(shí),hash % length = hash & (length-1)
,所以在構(gòu)造函數(shù)中需要使用tableSizeFor(int cap)
來(lái)調(diào)整初始容量;
/** ?*?Returns?a?power?of?two?size?for?the?given?target?capacity. ?*/static?final?int?tableSizeFor(int?cap)?{??int?n?=?cap?-?1; ??n?|=?n?>>>?1; ??n?|=?n?>>>?2; ??n?|=?n?>>>?4; ??n?|=?n?>>>?8; ??n?|=?n?>>>?16;??return?(n?<?0)???1?:?(n?>=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1; }
首先這里要明確:
2的冪的二進(jìn)制是,1后面全是0
有效位都是1的二進(jìn)制加1,就可以得到2的冪
以33為例,如圖:
因?yàn)閕nt是4個(gè)字節(jié)32位,所以最多只需要將高位的16位與低位的16位做或運(yùn)算就可以得到2的冪,而int n = cap - 1;
是為了避免cap本身就是2的冪的情況;這個(gè)算是真是厲害,看了很久才看明白,實(shí)在汗顏。
計(jì)算 hash
static?final?int?hash(Object?key)?{??int?h;??return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16); }
這里重新計(jì)算hash是因?yàn)樵?code>hash & (length-1)計(jì)算下標(biāo)的時(shí)候,實(shí)際只有hash的低位參與的運(yùn)算容易產(chǎn)生hash沖突,所以用異或是高位的16位也參與運(yùn)算,以減小hash沖突,要理解這里首先要明白,
& 操作之后只會(huì)保留下都是1的有效位
length-1(2的n次方-1)實(shí)際上就是n和1
& 操作之后hash所保留下來(lái)的也只有低位的n個(gè)有效位,所以實(shí)際只有hash的低位參與了運(yùn)算
具體如圖所示:
對(duì)于Map
而言最重要的當(dāng)然是Get
和Put
等操作了,所以下面將介紹與之相關(guān)的操作;
public?V?put(K?key,?V?value)?{??return?putVal(hash(key),?key,?value,?false,?true); }/** ?*?Implements?Map.put?and?related?methods?*?*?@param?hash?hash?for?key ?*?@param?key?the?key ?*?@param?value?the?value?to?put ?*?@param?onlyIfAbsent?if?true,?don't?change?existing?value ?*?@param?evict?if?false,?the?table?is?in?creation?mode. ?*?@return?previous?value,?or?null?if?none ?*/final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,?boolean?evict)?{ ??Node<K,V>[]?tab;?Node<K,V>?p;?int?n,?i;??//?如果沒(méi)有初始化哈希桶,就使用resize初始化 ??if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0) ????n?=?(tab?=?resize()).length;??//?如果hash對(duì)應(yīng)的哈希槽是空的,就直接放入 ??if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null) ????tab[i]?=?newNode(hash,?key,?value,?null);??else?{ ????Node<K,V>?e;?K?k;????//?如果已經(jīng)存在key,就替換舊值 ????if?(p.hash?==?hash?&&?((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k)))) ??????e?=?p;????//?如果已經(jīng)是樹(shù)節(jié)點(diǎn),就用putTreeVal遍歷樹(shù)賦值 ????else?if?(p?instanceof?TreeNode) ??????e?=?((TreeNode<K,V>)p).putTreeVal(this,?tab,?hash,?key,?value);????else?{??????//?遍歷鏈表 ??????for?(int?binCount?=?0;?;?++binCount)?{????????//?遍歷到最后一個(gè)節(jié)點(diǎn)也沒(méi)有找到,就新增一個(gè)節(jié)點(diǎn) ????????if?((e?=?p.next)?==?null)?{ ??????????p.next?=?newNode(hash,?key,?value,?null);??????????//?如果鏈表長(zhǎng)度大于8,則轉(zhuǎn)換為紅黑樹(shù) ??????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st ????????????treeifyBin(tab,?hash);??????????break; ????????}????????//?找到key對(duì)應(yīng)的節(jié)點(diǎn)則跳出遍歷 ????????if?(e.hash?==?hash?&&?((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))??????????break; ????????p?=?e; ??????} ????}????//?e是最后指向的節(jié)點(diǎn),如果不為空,說(shuō)明已經(jīng)存在key,則替換舊的value ????if?(e?!=?null)?{?//?existing?mapping?for?key ??????V?oldValue?=?e.value;??????if?(!onlyIfAbsent?||?oldValue?==?null) ????????e.value?=?value; ??????afterNodeAccess(e);??????return?oldValue; ????} ??}??//?新增節(jié)點(diǎn)時(shí)結(jié)構(gòu)改變modCount加1 ??++modCount;??if?(++size?>?threshold) ????resize(); ??afterNodeInsertion(evict);??return?null; }
具體過(guò)程如圖所示:
final?Node<K,V>[]?resize()?{ ??Node<K,V>[]?oldTab?=?table;??int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;??int?oldThr?=?threshold;??int?newCap,?newThr?=?0;??if?(oldCap?>?0)?{????//?如果hash桶已經(jīng)完成初始化,并且已達(dá)最大容量,則直接返回 ????if?(oldCap?>=?MAXIMUM_CAPACITY)?{ ??????threshold?=?Integer.MAX_VALUE;??????return?oldTab; ????}????//?如果擴(kuò)大2倍沒(méi)有超過(guò)最大容量,則擴(kuò)大兩倍 ????else?if?((newCap?=?oldCap?<<?1)?<?MAXIMUM_CAPACITY?&&?oldCap?>=?DEFAULT_INITIAL_CAPACITY) ??????newThr?=?oldThr?<<?1;?//?double?threshold ??}??//?如果threshold已經(jīng)初始化,則初始化容量為threshold ??else?if?(oldThr?>?0)??????//?initial?capacity?was?placed?in?threshold ????newCap?=?oldThr;??//?如果threshold和哈希桶都沒(méi)有初始化,則使用默認(rèn)值 ??else?{????????????????????//?zero?initial?threshold?signifies?using?defaults ????newCap?=?DEFAULT_INITIAL_CAPACITY; ????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY); ??}??//?重新計(jì)算threshold ??if?(newThr?==?0)?{????float?ft?=?(float)newCap?*?loadFactor; ????newThr?=?(newCap?<?MAXIMUM_CAPACITY?&&?ft?<?(float)MAXIMUM_CAPACITY???(int)ft?:?Integer.MAX_VALUE); ??} ??threshold?=?newThr;??@SuppressWarnings({"rawtypes","unchecked"}) ??Node<K,V>[]?newTab?=?(Node<K,V>[])new?Node[newCap]; ??table?=?newTab;??if?(oldTab?!=?null)?{????for?(int?j?=?0;?j?<?oldCap;?++j)?{ ??????Node<K,V>?e;??????if?((e?=?oldTab[j])?!=?null)?{ ????????oldTab[j]?=?null;????????//?如果只有一個(gè)節(jié)點(diǎn),則直接重新放置節(jié)點(diǎn) ????????if?(e.next?==?null) ??????????newTab[e.hash?&?(newCap?-?1)]?=?e;????????//?如果是樹(shù)節(jié)點(diǎn),則將紅黑樹(shù)拆分后,重新放置 ????????else?if?(e?instanceof?TreeNode) ??????????((TreeNode<K,V>)e).split(this,?newTab,?j,?oldCap);????????//?將鏈表拆分為原位置和高位置兩條鏈表 ????????else?{?//?preserve?order ??????????Node<K,V>?loHead?=?null,?loTail?=?null; ??????????Node<K,V>?hiHead?=?null,?hiTail?=?null; ??????????Node<K,V>?next;??????????do?{ ????????????next?=?e.next;????????????//?節(jié)點(diǎn)重新放置后在原位置 ????????????if?((e.hash?&?oldCap)?==?0)?{??????????????if?(loTail?==?null) ????????????????loHead?=?e;??????????????else ????????????????loTail.next?=?e; ??????????????loTail?=?e; ????????????}????????????//?節(jié)點(diǎn)重新放置后位置+oldCap ????????????else?{??????????????if?(hiTail?==?null) ????????????????hiHead?=?e;??????????????else ????????????????hiTail.next?=?e; ??????????????hiTail?=?e; ????????????} ??????????}?while?((e?=?next)?!=?null);??????????//?放置低位置鏈表 ??????????if?(loTail?!=?null)?{ ????????????loTail.next?=?null; ????????????newTab[j]?=?loHead; ??????????}??????????//?放置高位置鏈表 ??????????if?(hiTail?!=?null)?{ ????????????hiTail.next?=?null; ????????????newTab[j?+?oldCap]?=?hiHead; ??????????} ????????} ??????} ????} ??}??return?newTab }
上面的擴(kuò)容過(guò)程需要注意的是,因?yàn)楣M伴L(zhǎng)度總是2的冪,所以在擴(kuò)大兩倍之后原來(lái)的節(jié)點(diǎn)只可能在原位置或者原位置+oldCap,具體判斷是通過(guò)(e.hash & oldCap) == 0
實(shí)現(xiàn)的;
之前將了 & 操作只保留了都是1的有效位
oldCap 是2的n次方,實(shí)際也就是在n+1的位置為1,其余地方為0
因?yàn)閿U(kuò)容是擴(kuò)大2倍,實(shí)際上也就是在hash上取了 n+1位,那么就只需要判斷多取的第n+1位是否為0
如圖所示:
public?V?get(Object?key)?{ ??Node<K,V>?e;??return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value; }final?Node<K,V>?getNode(int?hash,?Object?key)?{ ??Node<K,V>[]?tab;?Node<K,V>?first,?e;?int?n;?K?k;??if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&?(first?=?tab[(n?-?1)?&?hash])?!=?null)?{????if?(first.hash?==?hash?&&?//?always?check?first?node ??????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))??????return?first;????if?((e?=?first.next)?!=?null)?{??????if?(first?instanceof?TreeNode)????????return?((TreeNode<K,V>)first).getTreeNode(hash,?key);??????do?{????????if?(e.hash?==?hash?&& ??????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))??????????return?e; ??????}?while?((e?=?e.next)?!=?null); ????} ??}??return?null; }
相較于其他方法get方法就要簡(jiǎn)單很多了,只是用hash取到對(duì)應(yīng)的hash槽,在依次遍歷即可。
public?Object?clone()?{ ??HashMap<K,V>?result;??try?{ ????result?=?(HashMap<K,V>)super.clone(); ??}?catch?(CloneNotSupportedException?e)?{????//?this?shouldn't?happen,?since?we?are?Cloneable ????throw?new?InternalError(e); ??} ??result.reinitialize(); ??result.putMapEntries(this,?false);??return?result; }
對(duì)于clone
方法這里有一個(gè)需要注意的地方,result.putMapEntries(this, false)
,這里在put節(jié)點(diǎn)的時(shí)候是用的this,所以這只是淺復(fù)制,會(huì)影響原map,所以在使用的時(shí)候需要注意一下;
至于其他方法還有很多,但大致思路都是一致的,大家可以在看一下源碼。
Number Of Records | Java 5 | Java 6 | Java 7 | Java 8 |
---|---|---|---|---|
10,000 | 4 ms | 3 ms | 4 ms | 2 ms |
100,000 | 7 ms | 6 ms | 8 ms | 4 ms |
1,000,000 | 99 ms | 15 ms | 14 ms | 13 ms |
Number Of Records | Java 5 | Java 6 | Java 7 | Java 8 |
---|---|---|---|---|
10,000 | 197 ms | 154 ms | 132 ms | 15 ms |
100,000 | 30346 ms | 18967 ms | 19131 ms | 177 ms |
1,000,000 | 3716886 ms | 2518356 ms | 2902987 ms | 1226 ms |
10,000,000 | OOM | OOM | OOM | 5775 ms |
Number Of Records | Java 5 | Java 6 | Java 7 | Java 8 |
---|---|---|---|---|
10,000 | 17 ms | 12 ms | 13 ms | 10 ms |
100,000 | 45 ms | 31 ms | 34 ms | 46 ms |
1,000,000 | 384 ms | 72 ms | 66 ms | 82 ms |
10,000,000 | 4731 ms | 944 ms | 1024 ms | 99 ms |
Number Of Records | Java 5 | Java 6 | Java 7 | Java 8 |
---|---|---|---|---|
10,000 | 211 ms | 153 ms | 162 ms | 10 ms |
100,000 | 29759 ms | 17981 ms | 17653 ms | 93 ms |
1,000,000 | 3527633 ms | 2509506 ms | 2902987 ms | 333 ms |
10,000,000 | OOM | OOM | OOM | 3970 ms |
從以上對(duì)比可以看到 JDK8 的 HashMap 無(wú)論 hash 是否均勻效率都要好得多,這里面hash算法的改良功不可沒(méi),并且因?yàn)榧t黑樹(shù)的引入使得它在hash不均勻甚至在所有key的hash都相同的情況,任然表現(xiàn)良好。
擴(kuò)容需要重排所有節(jié)點(diǎn)特別損耗性能,所以估算map大小并給定一個(gè)合理的負(fù)載系數(shù),就顯得尤為重要了。
HashMap 是線程不安全的。
雖然 JDK8 中引入了紅黑樹(shù),將極端hash的情況影響降到了最小,但是從上面的對(duì)比還是可以看到,一個(gè)好的hash對(duì)性能的影響仍然十分重大,所以寫(xiě)一個(gè)好的hashCode()
也非常重要。
分享文章:JDK源碼分析(5)之HashMap相關(guān)
鏈接URL:http://jinyejixie.com/article8/ppjhop.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供ChatGPT、Google、網(wǎng)站營(yíng)銷、網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、微信小程序
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容