1.hashing(哈希法)的概念

散列法(Hashing)是一種將字符組成的字符串轉(zhuǎn)換為固定長(zhǎng)度(一般是更短長(zhǎng)度)的數(shù)值或索引值的方法，稱為散列法，也叫哈希法。由于通過(guò)更短的哈希值比用原始值進(jìn)行數(shù)據(jù)庫(kù)搜索更快，這種方法一般用來(lái)在數(shù)據(jù)庫(kù)中建立索引并進(jìn)行搜索，同時(shí)還用在各種解密算法中。

對(duì)比：Hashtable、HashMap、TreeMap

Hashtable是早期Java類庫(kù)提供的一個(gè)哈希表實(shí)現(xiàn)，本身是同步的，不支持null鍵和值，由于同步導(dǎo)致的性能開(kāi)銷，所以已經(jīng)很少被推薦使用。

HashMap與HashTable主要區(qū)別在于HashMap不是同步的，支持null鍵和值等。通常情況下，HashMap進(jìn)行put或者get操作，可以達(dá)到常數(shù)時(shí)間的性能，所以它是絕大部分利用鍵值對(duì)存取場(chǎng)景的首選。

TreeMap則是基于紅黑樹(shù)的一種提供順序訪問(wèn)的Map，和HashMap不同，它的get、put、remove之類操作都是O(log(n))的時(shí)間復(fù)雜度，具體順序可以由指定的Comparator來(lái)決定，或者根據(jù)鍵的自然順序來(lái)判斷。

2.HashMap概念和底層結(jié)構(gòu)

HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。HashMap儲(chǔ)存的是鍵值對(duì)，HashMap很快。此類不保證映射的順序，特別是它不保證該順序恒久不變。

HashMap內(nèi)部結(jié)構(gòu)：可以看作是數(shù)組和鏈表結(jié)合組成的復(fù)合結(jié)構(gòu)，數(shù)組被分為一個(gè)個(gè)桶（bucket），每個(gè)桶存儲(chǔ)有一個(gè)或多個(gè)Entry對(duì)象，每個(gè)Entry對(duì)象包含三部分key（鍵）、value（值），next(指向下一個(gè)Entry），通過(guò)哈希值決定了Entry對(duì)象在這個(gè)數(shù)組的尋址；哈希值相同的Entry對(duì)象（鍵值對(duì)），則以鏈表形式存儲(chǔ)。如果鏈表大小超過(guò)樹(shù)形轉(zhuǎn)換的閾值（TREEIFY_THRESHOLD=8），鏈表就會(huì)被改造為樹(shù)形結(jié)構(gòu)。

hashMap的結(jié)構(gòu)示意圖如下：

查詢時(shí)間復(fù)雜度：HashMap的本質(zhì)可以認(rèn)為是一個(gè)數(shù)組，數(shù)組的每個(gè)索引被稱為桶，每個(gè)桶里放著一個(gè)單鏈表，一個(gè)節(jié)點(diǎn)連著一個(gè)節(jié)點(diǎn)。很明顯通過(guò)下標(biāo)來(lái)檢索數(shù)組元素時(shí)間復(fù)雜度為O(1)，而且遍歷鏈表的時(shí)間復(fù)雜度是O(n)，所以在鏈表長(zhǎng)度盡可能短的前提下，HashMap的查詢復(fù)雜度接近O(1)

數(shù)組：存儲(chǔ)區(qū)間連續(xù)，占用內(nèi)存嚴(yán)重，尋址容易，插入刪除困難；

鏈表：存儲(chǔ)區(qū)間離散，占用內(nèi)存比較寬松，尋址困難，插入刪除容易；

Hashmap綜合應(yīng)用了這兩種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了尋址容易，插入刪除也容易。

3.HashMap的工作原理

HashMap的工作原理：HashMap是基于散列法（又稱哈希法）的原理，使用put(key,value)存儲(chǔ)對(duì)象到HashMap中，使用get(key)從HashMap中獲取對(duì)象。當(dāng)我們給put()方法傳遞鍵和值時(shí)，我們先對(duì)鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket（桶）位置來(lái)儲(chǔ)存Entry對(duì)象。HashMap是在bucket中儲(chǔ)存鍵對(duì)象和值對(duì)象，作為Map.Entry。并不是僅僅只在bucket中存儲(chǔ)值。

HashMap具體的存取過(guò)程：

put存值的方法，過(guò)程如下：

• 判斷鍵值對(duì)數(shù)組table<i>是否為空或?yàn)閚ull，否則執(zhí)行resize()進(jìn)行擴(kuò)容；
• 根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果table<i>==null，直接新建節(jié)點(diǎn)添加，轉(zhuǎn)向⑥，如果table<i>不為空，轉(zhuǎn)向③；
• 判斷table<i>的首個(gè)元素是否和key一樣，如果相同直接覆蓋value，否則轉(zhuǎn)向④，這里的相同指的是hashCode以及equals；
• 判斷table<i>是否為treeNode，即table<i>是否是紅黑樹(shù)，如果是紅黑樹(shù)，則直接在樹(shù)中插入鍵值對(duì)，否則轉(zhuǎn)向⑤；
• 遍歷table<i>，判斷鏈表長(zhǎng)度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹(shù)，在紅黑樹(shù)中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作；遍歷過(guò)程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；
• 插入成功后，判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了最大容量threshold，如果超過(guò)，進(jìn)行擴(kuò)容。

get取值的方法，過(guò)程如下:

• 指定key通過(guò)hash函數(shù)得到key的hash值int hash=key.hashCode();
• 調(diào)用內(nèi)部方法getNode()，得到桶號(hào)(一般為hash值對(duì)桶數(shù)求模)int index=hash%Entry[].length；jdk1.6版本后使用位運(yùn)算替代模運(yùn)算，int index=hash&(Entry[].length-1）;
• 比較桶的內(nèi)部元素是否與key相等，若都不相等，則沒(méi)有找到。相等，則取出相等記錄的value。
• 如果得到key所在的桶的頭結(jié)點(diǎn)恰好是紅黑樹(shù)節(jié)點(diǎn)，就調(diào)用紅黑樹(shù)節(jié)點(diǎn)的getTreeNode()方法，否則就遍歷鏈表節(jié)點(diǎn)。getTreeNode方法使通過(guò)調(diào)用樹(shù)形節(jié)點(diǎn)的find()方法進(jìn)行查找。由于之前添加時(shí)已經(jīng)保證這個(gè)樹(shù)是有序的，因此查找時(shí)基本就是折半查找，效率很高。
• 如果對(duì)比節(jié)點(diǎn)的哈希值和要查找的哈希值相等，就會(huì)判斷key是否相等，相等就直接返回；不相等就從子樹(shù)中遞歸查找。

4.如何重新調(diào)整HashMap的大小

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

HashMap的擴(kuò)容閾值（threshold=capacity*loadFactor容量范圍是16~2的30次方），就是通過(guò)它和size進(jìn)行比較來(lái)判斷是否需要擴(kuò)容。默認(rèn)的負(fù)載因子大小為0.75，也就是說(shuō)，當(dāng)一個(gè)map填滿了75%的bucket時(shí)候，將會(huì)創(chuàng)建原來(lái)HashMap大小的兩倍的bucket數(shù)組（jdk1.6，但不超過(guò)最大容量），來(lái)重新調(diào)整map的大小，并將原來(lái)的對(duì)象放入新的bucket數(shù)組中。這個(gè)過(guò)程叫作rehashing，因?yàn)樗{(diào)用hash方法找到新的bucket位置。

5.解決hash沖突的常見(jiàn)方法

針對(duì)哈希表直接定址可能存在hash沖突，舉一個(gè)簡(jiǎn)單的例子，例如：

• 第一個(gè)鍵值對(duì)A進(jìn)來(lái)，通過(guò)計(jì)算其key的hash得到的index=0。記做:Entry[0]=A。
• 第二個(gè)鍵值對(duì)B，通過(guò)計(jì)算其index也等于0，HashMap會(huì)將B.next=A,Entry[0]=B,
• 第三個(gè)鍵值對(duì)C，通過(guò)計(jì)算其index也等于0，那么C.next=B,Entry[0]=C；

這樣我們發(fā)現(xiàn)index=0的地方事實(shí)上存取了A,B,C三個(gè)鍵值對(duì),它們通過(guò)next這個(gè)屬性鏈接在一起。對(duì)于不同的元素，可能計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了hash沖突，那要解決沖突，又有哪些方法呢？具體如下：

• 鏈地址法：將哈希表的每個(gè)單元作為鏈表的頭結(jié)點(diǎn)，所有哈希地址為i的元素構(gòu)成一個(gè)同義詞鏈表。即發(fā)生沖突時(shí)就把該關(guān)鍵字鏈在以該單元為頭結(jié)點(diǎn)的鏈表的尾部。
• 開(kāi)放定址法：即發(fā)生沖突時(shí)，去尋找下一個(gè)空的哈希地址。只要哈希表足夠大，總能找到空的哈希地址。
• 再哈希法：即發(fā)生沖突時(shí)，由其他的函數(shù)再計(jì)算一次哈希值。
• 建立公共溢出區(qū)：將哈希表分為基本表和溢出表，發(fā)生沖突時(shí)，將沖突的元素放入溢出表。

6.HashMap采用哪種方法解決沖突的呢？

HashMap就是使用鏈地址法來(lái)解決沖突的（jdk8中采用平衡樹(shù)來(lái)替代鏈表存儲(chǔ)沖突的元素，但hash()方法原理相同）。當(dāng)兩個(gè)對(duì)象的hashcode相同時(shí)，它們的bucket位置相同，碰撞就會(huì)發(fā)生。此時(shí)，可以將put進(jìn)來(lái)的K-V對(duì)象插入到鏈表的尾部。對(duì)于儲(chǔ)存在同一個(gè)bucket位置的鏈表對(duì)象，可通過(guò)鍵對(duì)象的equals()方法用來(lái)找到鍵值對(duì)。

以上就是動(dòng)力節(jié)點(diǎn)小編介紹的"HashMap原理的深入了解"，希望對(duì)大家有幫助，想了解更多可查看Java基礎(chǔ)教程，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為您服務(wù)。