1.hashing(哈希法)的概念

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

對比：Hashtable、HashMap、TreeMap

Hashtable是早期Java類庫提供的一個哈希表實現，本身是同步的，不支持null鍵和值，由于同步導致的性能開銷，所以已經很少被推薦使用。

HashMap與HashTable主要區別在于HashMap不是同步的，支持null鍵和值等。通常情況下，HashMap進行put或者get操作，可以達到常數時間的性能，所以它是絕大部分利用鍵值對存取場景的首選。

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

2.HashMap概念和底層結構

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

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

hashMap的結構示意圖如下：

查詢時間復雜度：HashMap的本質可以認為是一個數組，數組的每個索引被稱為桶，每個桶里放著一個單鏈表，一個節點連著一個節點。很明顯通過下標來檢索數組元素時間復雜度為O(1)，而且遍歷鏈表的時間復雜度是O(n)，所以在鏈表長度盡可能短的前提下，HashMap的查詢復雜度接近O(1)

數組：存儲區間連續，占用內存嚴重，尋址容易，插入刪除困難；

鏈表：存儲區間離散，占用內存比較寬松，尋址困難，插入刪除容易；

Hashmap綜合應用了這兩種數據結構，實現了尋址容易，插入刪除也容易。

3.HashMap的工作原理

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

HashMap具體的存取過程：

put存值的方法，過程如下：

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

get取值的方法，過程如下:

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

4.如何重新調整HashMap的大小

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

HashMap的擴容閾值（threshold=capacity*loadFactor容量范圍是16~2的30次方），就是通過它和size進行比較來判斷是否需要擴容。默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，將會創建原來HashMap大小的兩倍的bucket數組（jdk1.6，但不超過最大容量），來重新調整map的大小，并將原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。

5.解決hash沖突的常見方法

針對哈希表直接定址可能存在hash沖突，舉一個簡單的例子，例如：

• 第一個鍵值對A進來，通過計算其key的hash得到的index=0。記做:Entry[0]=A。
• 第二個鍵值對B，通過計算其index也等于0，HashMap會將B.next=A,Entry[0]=B,
• 第三個鍵值對C，通過計算其index也等于0，那么C.next=B,Entry[0]=C；

這樣我們發現index=0的地方事實上存取了A,B,C三個鍵值對,它們通過next這個屬性鏈接在一起。對于不同的元素，可能計算出了相同的函數值，這樣就產生了hash沖突，那要解決沖突，又有哪些方法呢？具體如下：

• 鏈地址法：將哈希表的每個單元作為鏈表的頭結點，所有哈希地址為i的元素構成一個同義詞鏈表。即發生沖突時就把該關鍵字鏈在以該單元為頭結點的鏈表的尾部。
• 開放定址法：即發生沖突時，去尋找下一個空的哈希地址。只要哈希表足夠大，總能找到空的哈希地址。
• 再哈希法：即發生沖突時，由其他的函數再計算一次哈希值。
• 建立公共溢出區：將哈希表分為基本表和溢出表，發生沖突時，將沖突的元素放入溢出表。

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

HashMap就是使用鏈地址法來解決沖突的（jdk8中采用平衡樹來替代鏈表存儲沖突的元素，但hash()方法原理相同）。當兩個對象的hashcode相同時，它們的bucket位置相同，碰撞就會發生。此時，可以將put進來的K-V對象插入到鏈表的尾部。對于儲存在同一個bucket位置的鏈表對象，可通過鍵對象的equals()方法用來找到鍵值對。

以上就是動力節點小編介紹的"HashMap原理的深入了解"，希望對大家有幫助，想了解更多可查看Java基礎教程，如有疑問，請在線咨詢，有專業老師隨時為您服務。