? ? ? ? 大家好，我是IT修真院北京分院第31期的學(xué)員郭计，一枚正直純潔善良的JAVA程序員椒振。今天給大家分享一下杠人，HashMap jdk1.8版 特性講解.
1.背景介紹
什么是HASHMAP?
HashMap是基于哈希表的Map接口的實(shí)現(xiàn),存儲的是鍵值對,并允許使用null鍵和null值.HashMap是非Synchronized,即是線程不安全的.如何要滿足線程安全可以使用ConcurrentHashMap.HashMap根據(jù)鍵的hashCode值存儲數(shù)據(jù),大多數(shù)情況下可以直接定位到它的值,因而具有很快的訪問速度,但遍歷順序是不確定的.
哈希表及MAP接口
哈希表(也叫散列表),是根據(jù)關(guān)鍵碼值(key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu).
也就是說,它通過把關(guān)鍵碼值(key value)映射到表中一個(gè)位置來訪問記錄,以加快查找的速度.這個(gè)映射函數(shù)叫做散列函數(shù),存放記錄的數(shù)組叫做散列表.
Map主要用于存儲鍵值對.Map的三個(gè)特點(diǎn):1,包含鍵值對;2,鍵唯一;3,鍵對應(yīng)的值唯一.Map還提供了3個(gè)集合視圖,分別是一組鍵值對,一組鍵,一組值.
MAP接口主要常用的實(shí)現(xiàn)類
Map接口主要有四個(gè)常用的實(shí)用類,分別是HashMap,Hashtable,LinkedHashMap和TreeMap.類繼承關(guān)系如下圖所示:
HASHTABLE
Hashtable是遺留類,很多映射的常用功能與HashMap類似,不同的是它繼承自Dictionary類,并且是線程安全的,任一時(shí)間只有一個(gè)線程能寫Hashtable.Hashtable不建議在新代碼中使用,不需要線程安全的場合可以用HashMap替換,需要線程安全的場合可以用ConcurrentHashMap替換.
哈希表及Map接口 哈希表(也叫散列表),是根據(jù)關(guān)鍵碼值(key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu). 也就是說,它通過把關(guān)鍵碼值(key value)映射到表中一個(gè)位置來訪問記錄,以加快查找的速度.這個(gè)映射函數(shù)叫做散列函數(shù),存放記錄的數(shù)組叫做散列表. Map主要用于存儲鍵值對.Map的三個(gè)特點(diǎn):1,包含鍵值對;2,鍵唯一;3,鍵對應(yīng)的值唯一.Map還提供了3個(gè)集合視圖,分別是一組鍵值對,一組鍵,一組值.
MAP接口主要常用的實(shí)現(xiàn)類
Map接口主要有四個(gè)常用的實(shí)用類,分別是HashMap,Hashtable,LinkedHashMap和TreeMap.類繼承關(guān)系如下圖所示:
HASHTABLE
Hashtable是遺留類,很多映射的常用功能與HashMap類似,不同的是它繼承自Dictionary類,并且是線程安全的,任一時(shí)間只有一個(gè)線程能寫Hashtable.Hashtable不建議在新代碼中使用,不需要線程安全的場合可以用HashMap替換,需要線程安全的場合可以用ConcurrentHashMap替換.
LINKEDHASHMAP
LinkedHashMap是HashMap的一個(gè)子類,保存了記錄的插入順序,在用Iterator遍歷LinkedHashMap時(shí),先得到的記錄肯定是先插入的,也可以在構(gòu)造時(shí)帶參數(shù),按照訪問次序排序.
Map接口主要常用的實(shí)現(xiàn)類 Map接口主要有四個(gè)常用的實(shí)用類,分別是HashMap,Hashtable,LinkedHashMap和TreeMap.類繼承關(guān)系如下圖所示:
HASHTABLE
Hashtable是遺留類,很多映射的常用功能與HashMap類似,不同的是它繼承自Dictionary類,并且是線程安全的,任一時(shí)間只有一個(gè)線程能寫Hashtable.Hashtable不建議在新代碼中使用,不需要線程安全的場合可以用HashMap替換,需要線程安全的場合可以用ConcurrentHashMap替換.
LINKEDHASHMAP
LinkedHashMap是HashMap的一個(gè)子類,保存了記錄的插入順序,在用Iterator遍歷LinkedHashMap時(shí),先得到的記錄肯定是先插入的,也可以在構(gòu)造時(shí)帶參數(shù),按照訪問次序排序.
TREEMAP
TreeMap實(shí)現(xiàn)SortedMap接口辑莫，能夠把它保存的記錄根據(jù)鍵排序各吨，默認(rèn)是按鍵值的升序排序袁铐，也可以指定排序的比較器剔桨，當(dāng)用Iterator遍歷TreeMap時(shí)，得到的記錄是排過序的瑰谜。如果使用排序的映射，建議使用TreeMap隐轩。在使用TreeMap時(shí)职车，key必須實(shí)現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator鹊杖，否則會在運(yùn)行時(shí)拋出java.lang.ClassCastException類型的異常仅淑。
Hashtable Hashtable是遺留類,很多映射的常用功能與HashMap類似,不同的是它繼承自Dictionary類,并且是線程安全的,任一時(shí)間只有一個(gè)線程能寫Hashtable.Hashtable不建議在新代碼中使用,不需要線程安全的場合可以用HashMap替換,需要線程安全的場合可以用ConcurrentHashMap替換.
2.知識剖析
JAVA 8系列之重新認(rèn)識HASHMAP
Java1.8對HashMap底層的實(shí)現(xiàn)進(jìn)行了優(yōu)化,例如紅黑樹的數(shù)據(jù)結(jié)構(gòu)和擴(kuò)容的優(yōu)化等,接下來我們將深入探討HashMap 的結(jié)構(gòu)實(shí)現(xiàn)和功能原理.
結(jié)構(gòu)實(shí)現(xiàn)
從結(jié)構(gòu)實(shí)現(xiàn)來講,HashMap是數(shù)組+鏈表+紅黑樹(JDK1.8增加了紅黑樹部分)實(shí)現(xiàn)的,如下圖所示.?
這里需要講明白兩個(gè)問題:數(shù)據(jù)底層具體存儲的是什么?這樣的存儲方法有什么優(yōu)點(diǎn)?
(1)HashMap類中有一個(gè)非常重要的字段,就是Node[]table,即哈希桶數(shù)組,明顯它是一個(gè)Node的數(shù)組.Node就是HashMap的一個(gè)內(nèi)部類,實(shí)現(xiàn)了Map.Entry接口,本質(zhì)就是一個(gè)映射(鍵值對).
(2)HashMap就是使用哈希表來存儲的.在上面已經(jīng)介紹了鍵值對是通過散列函數(shù)(哈希函數(shù))映射到哈希表的地址上的,而所有的散列函數(shù)都有如下一個(gè)基本特征:根據(jù)同一散列函數(shù)計(jì)算出來的散列值不同,那么輸入的信息肯定也不同.但是,根據(jù)同一散列函數(shù)計(jì)算出的散列值如果相同,輸入值不一定相同.
這句話的意思就是輸入不同的兩個(gè)值可能得到一樣的散列值.這種現(xiàn)象叫做碰撞.Java中HashMap為了解決沖突采用鏈表地址法.鏈表地址法:將哈希表的每個(gè)單元作為鏈表的頭結(jié)點(diǎn)涯竟，所有哈希地址為i的元素構(gòu)成一個(gè)同義詞鏈表庐船。即發(fā)生沖突時(shí)就把該關(guān)鍵字鏈在以該單元為頭結(jié)點(diǎn)的鏈表的尾部嘲更。
舉個(gè)例子,例如程序執(zhí)行下面的代碼:map.put("美團(tuán)","小小");系統(tǒng)將調(diào)用"美團(tuán)"這個(gè)key的hashCode()方法得到其hashCode 值（該方法適用于每個(gè)Java對象）赋朦，然后再通過Hash算法的后兩步運(yùn)算（高位運(yùn)算和取模運(yùn)算，下文有介紹）來定位該鍵值對的存儲位置壹将，有時(shí)兩個(gè)key會定位到相同的位置毛嫉，表示發(fā)生了Hash碰撞承粤。當(dāng)然Hash算法計(jì)算結(jié)果越分散均勻，Hash碰撞的概率就越小仙粱。如果哈希桶數(shù)組很大缰盏，即使較差的Hash算法也會比較分散，所以就需要在空間成本和時(shí)間成本之間權(quán)衡.那么通過什么方式來控制map使得Hash碰撞的概率又小负溪，哈希桶數(shù)組（Node[] table）占用空間又少呢济炎？答案就是好的Hash算法和擴(kuò)容機(jī)制须尚。
在理解Hash和擴(kuò)容流程之前耐床，我們得先了解下HashMap的幾個(gè)字段。從HashMap的默認(rèn)構(gòu)造函數(shù)源碼可知胯甩，構(gòu)造函數(shù)就是對下面幾個(gè)字段進(jìn)行初始化堪嫂，源碼如下： int threshold; // 所能容納的key-value對極限 final float loadFactor; // 負(fù)載因子 int modCount; int size;
首先皆串，Node[] table的初始化長度length(默認(rèn)值是16)，Loadfactor為負(fù)載因子(默認(rèn)值是0.75)怜森，threshold是HashMap所能容納的最大數(shù)據(jù)量的Node(鍵值對)個(gè)數(shù)谤牡。threshold = length * Load factor拓哟。也就是說断序，在數(shù)組定義好長度之后，負(fù)載因子越大漱凝，所能容納的鍵值對個(gè)數(shù)越多诸迟。結(jié)合負(fù)載因子的定義公式可知，threshold就是在此Load factor和length(數(shù)組長度)對應(yīng)下允許的最大元素?cái)?shù)目感论，超過這個(gè)數(shù)目 就重新resize(擴(kuò)容)紊册，擴(kuò)容后的HashMap容量是之前容量的兩倍。
舉個(gè)例子,例如程序執(zhí)行下面的代碼:map.put("美團(tuán)","小小");系統(tǒng)將調(diào)用"美團(tuán)"這個(gè)key的hashCode()方法得到其hashCode 值（該方法適用于每個(gè)Java對象）囊陡，然后再通過Hash算法的后兩步運(yùn)算（高位運(yùn)算和取模運(yùn)算芳绩，下文有介紹）來定位該鍵值對的存儲位置，有時(shí)兩個(gè)key會定位到相同的位置撞反，表示發(fā)生了Hash碰撞妥色。當(dāng)然Hash算法計(jì)算結(jié)果越分散均勻，Hash碰撞的概率就越小遏片。如果哈希桶數(shù)組很大嘹害，即使較差的Hash算法也會比較分散，所以就需要在空間成本和時(shí)間成本之間權(quán)衡.那么通過什么方式來控制map使得Hash碰撞的概率又小丁稀，哈希桶數(shù)組（Node[] table）占用空間又少呢吼拥？答案就是好的Hash算法和擴(kuò)容機(jī)制齿拂。
在理解Hash和擴(kuò)容流程之前菩暗，我們得先了解下HashMap的幾個(gè)字段。從HashMap的默認(rèn)構(gòu)造函數(shù)源碼可知授账，構(gòu)造函數(shù)就是對下面幾個(gè)字段進(jìn)行初始化，源碼如下： int threshold; // 所能容納的key-value對極限 final float loadFactor; // 負(fù)載因子 int modCount; int size;
首先惨驶，Node[] table的初始化長度length(默認(rèn)值是16)白热，Loadfactor為負(fù)載因子(默認(rèn)值是0.75)，threshold是HashMap所能容納的最大數(shù)據(jù)量的Node(鍵值對)個(gè)數(shù)粗卜。threshold = length * Load factor屋确。也就是說，在數(shù)組定義好長度之后续扔，負(fù)載因子越大攻臀，所能容納的鍵值對個(gè)數(shù)越多。結(jié)合負(fù)載因子的定義公式可知纱昧，threshold就是在此Load factor和length(數(shù)組長度)對應(yīng)下允許的最大元素?cái)?shù)目刨啸，超過這個(gè)數(shù)目 就重新resize(擴(kuò)容)，擴(kuò)容后的HashMap容量是之前容量的兩倍识脆。
默認(rèn)的負(fù)載因子0.75是對空間和時(shí)間效率的一個(gè)平衡選擇设联，建議大家不要修改善已，除非在時(shí)間和空間比較特殊的情況下，如果內(nèi)存空間很多而又對時(shí)間效率要求很高离例，可以降低負(fù)載因子Load factor的值换团；相反，如果內(nèi)存空間緊張而對時(shí)間效率要求不高宫蛆，可以增加負(fù)載因子loadFactor的值啥寇，這個(gè)值可以大于1。
size這個(gè)字段其實(shí)很好理解洒扎，就是HashMap中實(shí)際存在的鍵值對數(shù)量辑甜。modCount字段主要用來記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)，例如put新鍵值對袍冷，但是某個(gè)key對應(yīng)的value值被覆蓋不屬于結(jié)構(gòu)變化磷醋。在HashMap中，哈希桶數(shù)組table的長度length大小必須為2的n次方(一定是合數(shù))胡诗，HashMap采用這種非常規(guī)設(shè)計(jì)邓线，主要是為了在取模和擴(kuò)容時(shí)做優(yōu)化，同時(shí)為了減少沖突煌恢，HashMap定位哈希桶索引位置時(shí)骇陈，也加入了高位參與運(yùn)算的過程。
這里存在一個(gè)問題瑰抵，即使負(fù)載因子和Hash算法設(shè)計(jì)的再合理你雌，也免不了會出現(xiàn)拉鏈過長的情況，一旦出現(xiàn)拉鏈過長二汛，則會嚴(yán)重影響HashMap的性能婿崭。于是，在JDK1.8版本中肴颊，對數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化氓栈，引入了紅黑樹。而當(dāng)鏈表長度太長（默認(rèn)超過8）時(shí)婿着，鏈表就轉(zhuǎn)換為紅黑樹授瘦，利用紅黑樹快速增刪改查的特點(diǎn)提高HashMap的性能.
功能實(shí)現(xiàn)-方法
接下來我將結(jié)合HashCode的源碼來為大家講解以下三個(gè)具有代表性的功能點(diǎn):
1, 確定哈希桶數(shù)組索引位置; 2, 分析HashMap的put方法; 3,擴(kuò)容機(jī)制.
size這個(gè)字段其實(shí)很好理解，就是HashMap中實(shí)際存在的鍵值對數(shù)量竟宋。modCount字段主要用來記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)提完，例如put新鍵值對，但是某個(gè)key對應(yīng)的value值被覆蓋不屬于結(jié)構(gòu)變化袜硫。在HashMap中氯葬，哈希桶數(shù)組table的長度length大小必須為2的n次方(一定是合數(shù))，HashMap采用這種非常規(guī)設(shè)計(jì)婉陷，主要是為了在取模和擴(kuò)容時(shí)做優(yōu)化帚称，同時(shí)為了減少沖突官研，HashMap定位哈希桶索引位置時(shí)，也加入了高位參與運(yùn)算的過程闯睹。
這里存在一個(gè)問題戏羽，即使負(fù)載因子和Hash算法設(shè)計(jì)的再合理，也免不了會出現(xiàn)拉鏈過長的情況楼吃，一旦出現(xiàn)拉鏈過長始花，則會嚴(yán)重影響HashMap的性能。于是孩锡，在JDK1.8版本中酷宵，對數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化，引入了紅黑樹躬窜。而當(dāng)鏈表長度太長（默認(rèn)超過8）時(shí)浇垦，鏈表就轉(zhuǎn)換為紅黑樹，利用紅黑樹快速增刪改查的特點(diǎn)提高HashMap的性能.
3.編碼實(shí)戰(zhàn)
4.常見問題
一,為什么STRING, INTERGER這樣的WRAPPER類適合作為鍵荣挨？
String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了男韧，而且String最為常用。因?yàn)镾tring是不可變的默垄，也是final的此虑，而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個(gè)特點(diǎn)口锭。不可變性是必要的朦前，因?yàn)闉榱艘?jì)算hashCode()，就要防止鍵值改變讹弯，如果鍵值在放入時(shí)和獲取時(shí)返回不同的hashcode的話况既，那么就不能從HashMap中找到你想要的對象这溅。因?yàn)楂@取對象的時(shí)候要用到equals()和hashCode()方法组民，那么鍵對象正確的重寫這兩個(gè)方法是非常重要的。如果兩個(gè)不相等的對象返回不同的hashcode的話悲靴，那么碰撞的幾率就會小些臭胜，這樣就能提高HashMap的性能。
二,我們可以使用自定義的對象作為鍵嗎癞尚？
這是前一個(gè)問題的延伸耸三。當(dāng)然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規(guī)則浇揩，并且當(dāng)對象插入到Map中之后將不會再改變了仪壮。如果這個(gè)自定義對象時(shí)不可變的，那么它已經(jīng)滿足了作為鍵的條件胳徽，因?yàn)楫?dāng)它創(chuàng)建之后就已經(jīng)不能改變了积锅。
三,我們可以使用COCURRENTHASHMAP來代替HASHTABLE嗎爽彤？
這是另外一個(gè)很熱門的面試題，因?yàn)镃oncurrentHashMap越來越多人用了缚陷。我們知道Hashtable是synchronized的适篙，但是ConcurrentHashMap同步性能更好，因?yàn)樗鼉H僅根據(jù)同步級別對map的一部分進(jìn)行上鎖箫爷。ConcurrentHashMap當(dāng)然可以代替HashTable嚷节，但是HashTable提供更強(qiáng)的線程安全性。
5.參考文獻(xiàn)
https://blog.csdn.net/abcdad/article/details/64123291
https://zhuanlan.zhihu.com/p/21673805
https://blog.csdn.net/v_july_v/article/details/6105630
6.更多討論
.
