Java基础 HashMap实现原理及方法
1、什么是HashMap？
????? ? HashMap通常提起他，我們想到的就是鍵值對方式存儲(chǔ)（key-value型式），可以接收null鍵值和null值?；贛ap接口的非同步實(shí)現(xiàn)（也就是線程不安全），并不保證映射的順序，特別不保證這個(gè)順序恒久不變。
????????? ? 下圖是HashMap的源碼，可以看到它繼承自AbstractMap，實(shí)現(xiàn)Map，Cloneable，Serializable接口。其一些默認(rèn)值都一一列出：
????????? ? 其中，modCount這個(gè)屬性值是記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化（指的是內(nèi)部結(jié)構(gòu)，相同的key,put()一個(gè)value這種覆蓋原來的值不屬于結(jié)構(gòu)變化）的次數(shù)，主要用于迭代的快速失敗。
????????? ? threshold來判斷HashMap的最大容量,threshold = (int)(capacity * loadFactor)；
????????? ? loadFactor負(fù)載因子：散列表的實(shí)際元素?cái)?shù)目/散列表的容量。
??????????其衡量的是一個(gè)散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高（裝東西越滿），使用鏈表法?的散列 表空間利用越充分，查找時(shí)間則變長效率降低；越小則結(jié)論與越大相反。
???????????Entry為HashMap的靜態(tài)內(nèi)部類，從上面可以看出Entry為承載key-value的值，并且默認(rèn)table為Entry數(shù)組。下面看一下Entry的源碼：
????? ? put時(shí)如果key傳入為null,那么value一定會(huì)為null，無論value輸入什么.并且map.put()/get()的返回值是value的類型，并且當(dāng)存入空的時(shí)候?yàn)閔ashmap中數(shù)組第一位。下面是對應(yīng)的小栗子：
1、
Map<String, String> map2 = new HashMap<String,String>();
String r2 = map2.put(null, null);
System.out.println("r2 "+r2);
String r3 = map2.get(null);
System.out.println("r3 "+r3);
String r4 = map2.put(null, "32");
System.out.println("r4 "+r4);
????????????輸出 結(jié)果：r2 null
??????????????????????????????r3 null
??????????????????????????????r4 null
2、
3、從此可以看出hashmap的hash方法如果key為空則默認(rèn)0，否則key取hashcode異或運(yùn)算h無符號(hào)右移16位
2、HashMap的數(shù)據(jù)結(jié)構(gòu)是什么樣的呢？
????? ? jdk的1.8之前的版本和1.8及之后的版本HashMap的數(shù)據(jù)結(jié)構(gòu)出現(xiàn)了一點(diǎn)變化。我們這里主要介紹1.8之前的數(shù)據(jù)結(jié)構(gòu)。主要是數(shù)組+鏈表的結(jié)構(gòu)，上面給出的屬性源碼也可以看出HashMap是這樣的數(shù)據(jù)結(jié)構(gòu)（table數(shù)組，Entry類為一個(gè)鏈表的節(jié)點(diǎn)來存儲(chǔ)Key-value），也叫拉鏈法（鏈表數(shù)組）。
????? ? 在1.8之后HashMap的數(shù)據(jù)結(jié)構(gòu)出現(xiàn)了改變，變成數(shù)組+鏈表+紅黑樹，默認(rèn)值增加了樹的相關(guān)默認(rèn)值，Entry類改成Node但是類里面內(nèi)容沒有改變。
????????????并且增添了TreeNode節(jié)點(diǎn)，繼承自LinkedHashMap,LinkedHashMap則繼承自HashMap。下面是TreeNode內(nèi)容：
?????????????紅黑樹是一種自平衡二叉查找樹。它的統(tǒng)計(jì)性能要好于平衡二叉樹（AVL樹）。這種樹結(jié)構(gòu)從根節(jié)點(diǎn)開始，左子節(jié)點(diǎn)小于它，右子節(jié)點(diǎn)大于它。每個(gè)節(jié)點(diǎn)都符合這個(gè)特性，所以易于查找，是一種很好的數(shù)據(jù)結(jié)構(gòu)。但是它有一個(gè)問題，就是容易偏向某一側(cè)，這樣就像一個(gè)鏈表結(jié)構(gòu)了，失去了樹結(jié)構(gòu)的優(yōu)點(diǎn)，查找時(shí)間會(huì)變壞。（這里就詳細(xì)講解這個(gè)結(jié)構(gòu)了以后會(huì)開一個(gè)數(shù)據(jù)結(jié)構(gòu)的專欄）
????? ?閱讀源碼可以看出樹比鏈表占了更多的空間。8后，決定如何使用這兩種數(shù)據(jù)結(jié)構(gòu)呢？?
? ??????? ?1、如果一個(gè)內(nèi)部表的索引超過8個(gè)節(jié)點(diǎn)，鏈表會(huì)轉(zhuǎn)化為紅黑樹?
???????????2、 如果內(nèi)部表的索引少于6個(gè)節(jié)點(diǎn)，樹會(huì)變回鏈表
? ? ? ? ? 當(dāng)鏈表元素個(gè)數(shù)大于等于8時(shí)，鏈表轉(zhuǎn)換成樹結(jié)構(gòu)；若桶中鏈表元素個(gè)數(shù)小于等于6時(shí)，樹結(jié)構(gòu)還原成鏈表。因?yàn)榧t黑樹的平均查找長度是log(n)，長度為8的時(shí)候，平均查找長度為3，如果繼續(xù)使用鏈表，平均查找長度為8/2=4，這才有轉(zhuǎn)換為樹的必要。鏈表長度如果是小于等于6，6/2=3，雖然速度也很快的，但是轉(zhuǎn)化為樹結(jié)構(gòu)和生成樹的時(shí)間并不會(huì)太短。還有選擇6和8，中間有個(gè)差值7可以有效防止鏈表和樹頻繁轉(zhuǎn)換。假設(shè)一下，如果設(shè)計(jì)成鏈表個(gè)數(shù)超過8則鏈表轉(zhuǎn)換成樹結(jié)構(gòu)，鏈表個(gè)數(shù)小于8則樹結(jié)構(gòu)轉(zhuǎn)換成鏈表，如果一個(gè)HashMap不停的插入、刪除元素，鏈表個(gè)數(shù)在8左右徘徊，就會(huì)頻繁的發(fā)生樹轉(zhuǎn)鏈表、鏈表轉(zhuǎn)樹，效率會(huì)很低。
3、HashMap的工作原理
????????? ? 它的原理就是Hashing原理。在上一部分我們講到了HashMap的數(shù)組結(jié)構(gòu)，每添加(put())或是獲取(get())都是向每個(gè)數(shù)組位（array[i]）對應(yīng)為一個(gè)bucket里的Entry中添加鍵值對。而通過hashCode()得出一個(gè)hash值來算出bucket(水桶)的位置來進(jìn)行存取（這里的運(yùn)算都是位運(yùn)算）。
4、HashMap的存取
? 1、存入主要是put()方法：? ??????????????
????????? ? 可以從上面源碼看出在put時(shí)，根據(jù)hash值來確定存放數(shù)組的索引位置。如果該位置上已經(jīng)存放了Entry那么，那么將會(huì)以鏈表的形式存放鍵值對，原來的Entry放在next進(jìn)行鏈接，及新加入的放鏈頭，原來的放鏈尾。如果該位置上沒有Entry則直接存放到對應(yīng)的數(shù)組索引的位置上。
?2、取出get()方法：
????? ? 從源碼上可以看出get()也是先算取key的hash值，然后找到hash值對應(yīng)的索引，看是否有鏈表，若有則看是否和鏈表中Entry的key是否相等，相等則equals()取value值。實(shí)際上就是將key-value看成一個(gè)整體Entry，來用hashCode()來查找hash值，如果有鏈表就判斷鏈表，沒有鏈表就直接取對應(yīng)的數(shù)組索引。
?3、擴(kuò)容resize()(rehash)方法：
5、HashMap的一些問題思考
1、什么時(shí)候會(huì)出現(xiàn)擴(kuò)容呢？
????
????? ? 源碼上addEntry是size大于threshold時(shí)開始調(diào)用resize()方法。也就是HashMap中，數(shù)組元素超過了數(shù)組閥值的時(shí)候就重新擴(kuò)容，以降低實(shí)際的負(fù)載因子。(threshold>capacity*loadfactor)默認(rèn)的的負(fù)載因子 0.75是對空間和時(shí)間效率的一個(gè)平衡選擇。當(dāng)容量超出此最大容量時(shí)， resize后的HashMap 容量是原容量的兩倍。
2、HashMap容量一定為2的冪呢？
????????? ? 首先，我們希望元素存放的更均勻，最理想的效果是每個(gè)bucket中存放一個(gè)Entry（key-value）。這樣查詢的時(shí)候效率高，不需要遍歷鏈表，也不需要equals去比較鏈表中的key的內(nèi)容。而且，這樣空間利用率最大，時(shí)間復(fù)雜度最優(yōu)。因?yàn)镠ashMap的底層數(shù)組的長度為2^n次方，不同的key算得的index的相同幾率較小，數(shù)組上分布就比較均勻，也就是碰撞幾率小，相對查詢時(shí)效率會(huì)高。
????????????假設(shè)：數(shù)組長度為32時(shí)，即為2的n次方時(shí)，2n-1得到的二進(jìn)制數(shù)的每個(gè)位上的值都為1，這使得在低位上&時(shí)，得到的和原h(huán)ash的低位相同，加之hash(int h)方法對key的hashCode的進(jìn)一步優(yōu)化，加入了高位計(jì)算，就使得只有相同的hash值的兩個(gè)值才會(huì)被放到數(shù)組中的同一個(gè)位置上形成鏈表。
3、Hash沖突（碰撞）及解決Hash沖突的方法？????????
??????????? ?hash沖突就是當(dāng)hash值相同,此時(shí)他們確定的索引位置相同，這時(shí)他們的key如果不相同，則為hash沖突。
????????? ? 解決hash沖突的辦法：
????????????????? ? 通常有：1、開放定址法 （基本思想是通過一個(gè)探測算法，當(dāng)某個(gè)槽位已經(jīng)被占據(jù)的情況下?lián)璨檎蚁乱粋€(gè)可以使用的槽位）。?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2、再哈希法（基本思想是同事構(gòu)造多個(gè)哈希函數(shù)，當(dāng)函數(shù)1沖突時(shí)，再用下一個(gè)方法計(jì)算，直到?jīng)_突不再產(chǎn)生）。這種方法不已長生聚焦，但增加計(jì)算時(shí)間。? ??????????????????????????????????????? ?? ??
?
??????????????????????????????????3、鏈地址法（基本思想是將相同的hash值的對象組成一個(gè)成為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的這個(gè)hash值中）。適用于經(jīng)常插入和刪除。
??????????????????????????????????4、建立公共溢出區(qū)（將哈希表分為基本表和溢出表兩部分，凡是發(fā)生沖突的都放在溢出表中）。
????????????? ? Java.until.HashMap就是采用鏈表法的方式。當(dāng)發(fā)生碰撞，對象將會(huì)存儲(chǔ)在LinkedList的下一結(jié)點(diǎn)中。HashMap在每個(gè)LinkedList節(jié)點(diǎn)中存儲(chǔ)鍵值對對象。
4、重新調(diào)整HashMap大小存在的問題?
????? ????HashMap數(shù)組擴(kuò)容后很消耗性能：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其出現(xiàn)在新數(shù)組中的位置，并存儲(chǔ)進(jìn)去。
?????????在多線程下，HashMap擴(kuò)容后可能會(huì)產(chǎn)生條件競爭（race condition）。如果兩個(gè)線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小，他們會(huì)同時(shí)試著調(diào)整大小，在調(diào)整大小的過程中，存儲(chǔ)在LinkedList中的元素次序會(huì)反過來，因?yàn)橐苿?dòng)到新的bucket位置的時(shí)候Hashmap并不會(huì)將元素放在LinkedList的尾部，而是放在頭部，這是為了避免尾部遍歷（tail traversing）。如果條件競爭產(chǎn)生，就會(huì)出現(xiàn)死循環(huán)。
5、Fail-First機(jī)制?
???java.util.HashMap 不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了 hashmap，那么將拋出 ConcurrentModificationException，這就是所謂 fail-fast 策略。?
? ? ? ?在迭代過程中，判斷 modCount 跟 expectedModCount 是否相等，如果不相等就表示已經(jīng)有其他線程修改了 Map，則會(huì)拋出異常，下圖是源代碼：?
? 解決辦法：
????????1、在遍歷過程中所有涉及到改變modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList，這樣就可以解決。但是不推薦，因?yàn)樵鰟h造成的同步鎖可能會(huì)阻塞遍歷操作。? ? ? ? ??
????????2、使用CopyOnWriteArrayList來替換ArrayList。推薦使用該方案。
6、為什么String, Interger這樣的wrapper類適合作為鍵？
????????? ?因?yàn)樗麄冇蒮inal修飾，使用不可變類就能保證hashCode是不變的，而且重寫了equals和hashcode方法，避免了鍵值對改寫。如果兩個(gè)不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會(huì)小些，提高HashMap性能。
????????
總結(jié)
以上是生活随笔為你收集整理的Java基础 HashMap实现原理及方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java基础 ArrayList和Li
- 下一篇： org.dom4j.DocumentEx