HashMap是Java程序員使用頻率最高的用于映射(鍵值對)處理的數(shù)據(jù)類型。

Java為數(shù)據(jù)結(jié)構(gòu)中的映射定義了一個接口java.util.Map，此接口主要有四個常用的實現(xiàn)類，分別是HashMap、Hashtable、LinkedHashMap和TreeMap（還有ConcurrentHashMap），類繼承關(guān)系如下圖所示：

HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。

LinkedHashMap是HashMap的一個子類，保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的，也可以在構(gòu)造時帶參數(shù)，按照訪問次序排序。

TreeMap實現(xiàn)SortedMap接口，能夠把它保存的記錄根據(jù)鍵排序，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器，當(dāng)用Iterator遍歷TreeMap時，得到的記錄是排過序的。如果使用排序的映射，建議使用TreeMap。在使用TreeMap時，key必須實現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator，否則會在運行時拋出java.lang.ClassCastException類型的異常。

Hashtable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，并且是線程安全的，任一時間只有一個線程能寫Hashtable

從結(jié)構(gòu)實現(xiàn)來講，HashMap是:數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現(xiàn)的，如下如所示。

HashMap數(shù)據(jù)底層具體存儲的是什么？這樣的存儲方式有什么優(yōu)點呢？

從源碼可知，HashMap類中有一個非常重要的字段，就是Node[]table，即哈希桶數(shù)組。

Node是HashMap的一個內(nèi)部類，實現(xiàn)了Map.Entry接口，本質(zhì)是就是一個映射(鍵值對)，除了K，V，還包含hash和next。

HashMap就是使用哈希表來存儲的。哈希表為解決沖突，采用鏈地址法來解決問題，鏈地址法，簡單來說，就是數(shù)組加鏈表的結(jié)合。在每個數(shù)組元素上都一個鏈表結(jié)構(gòu)，當(dāng)數(shù)據(jù)被Hash后，得到數(shù)組下標(biāo)，把數(shù)據(jù)放在對應(yīng)下標(biāo)元素的鏈表上。

如果哈希桶數(shù)組很大，即使較差的Hash算法也會比較分散，如果哈希桶數(shù)組數(shù)組很小，即使好的Hash算法也會出現(xiàn)較多碰撞，所以就需要在空間成本和時間成本之間權(quán)衡，其實就是在根據(jù)實際情況確定哈希桶數(shù)組的大小，并在此基礎(chǔ)上設(shè)計好的hash算法減少Hash碰撞。那么通過什么方式來控制map使得Hash碰撞的概率又小，哈希桶數(shù)組（Node[]table）占用空間又少呢？答案就是好的Hash算法和擴(kuò)容機制。

在理解Hash和擴(kuò)容流程之前，我們得先了解下HashMap的幾個字段。從HashMap的默認(rèn)構(gòu)造函數(shù)源碼可知，構(gòu)造函數(shù)就是對下面幾個字段進(jìn)行初始化，源碼如下：

int threshold; // 所能容納的key-value對極限,超過這個數(shù)目就重新resize(擴(kuò)容)
final float loadFactor; // 負(fù)載因子,默認(rèn)的負(fù)載因子0.75是對空間和時間效率的一個平衡選擇，建議大家不要修改
int modCount; //記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)
int size;　　//實際存在的鍵值對數(shù)量

在HashMap中，哈希桶數(shù)組table的長度length大小必須為2的n次方.

這里存在一個問題，即使負(fù)載因子和Hash算法設(shè)計的再合理，也免不了會出現(xiàn)拉鏈過長的情況，一旦出現(xiàn)拉鏈過長，則會嚴(yán)重影響HashMap的性能。于是，在JDK1.8版本中，對數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化，引入了紅黑樹。而當(dāng)鏈表長度太長（默認(rèn)超過8）時，鏈表就轉(zhuǎn)換為紅黑樹，利用紅黑樹快速增刪改查的特點提高HashMap的性能，其中會用到紅黑樹的插入、刪除、查找等算法。

HashMap的內(nèi)部功能實現(xiàn)很多，本文主要從：

1.根據(jù)key獲取哈希桶數(shù)組索引位置

2.put方法的詳細(xì)執(zhí)行

3.擴(kuò)容過程三個具有代表性的點深入展開講解。

確定哈希桶數(shù)組索引位置

不管增加、刪除、查找鍵值對，定位到哈希桶數(shù)組的位置都是很關(guān)鍵的第一步。前面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當(dāng)然希望這個HashMap里面的元素位置盡量分布均勻些，盡量使得每個位置上的元素數(shù)量只有一個，那么當(dāng)我們用hash算法求得這個位置的時候，馬上就可以知道對應(yīng)位置的元素就是我們要的，不用遍歷鏈表，大大優(yōu)化了查詢的效率。

HashMap的Hash算法本質(zhì)上就是三步：取key的hashCode值、高位運算、取模運算。

分析HashMap的put方法

擴(kuò)容機制

擴(kuò)容(resize)就是重新計算容量，向HashMap對象里不停的添加元素，而HashMap對象內(nèi)部的數(shù)組無法裝載更多的元素時，對象就需要擴(kuò)大數(shù)組的長度，以便能裝入更多的元素。

這里就是使用一個容量更大的數(shù)組來代替已有的容量小的數(shù)組，transfer()方法將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里。

HashMap中，如果key經(jīng)過hash算法得出的數(shù)組索引位置全部不相同，即Hash算法非常好，那樣的話，getKey方法的時間復(fù)雜度就是O(1)，如果Hash算法技術(shù)的結(jié)果碰撞非常多，假如Hash算極其差，所有的Hash算法結(jié)果得出的索引位置一樣，那樣所有的鍵值對都集中到一個桶中，或者在一個鏈表中，或者在一個紅黑樹中，時間復(fù)雜度分別為O(n)和O(lgn)。

小結(jié)

1.擴(kuò)容是一個特別耗性能的操作，所以當(dāng)程序員在使用HashMap的時候，估算map的大小，初始化的時候給一個大致的數(shù)值，避免map進(jìn)行頻繁的擴(kuò)容。

2.負(fù)載因子是可以修改的，也可以大于1，但是建議不要輕易修改，除非情況非常特殊。

3.HashMap是線程不安全的，不要在并發(fā)的環(huán)境中同時操作HashMap，建議使用ConcurrentHashMap。

4.JDK1.8引入紅黑樹大程度優(yōu)化了HashMap的性能。

以上就是動力節(jié)點小編介紹的"HashMap的底層結(jié)構(gòu)和原理"，希望對大家有幫助，想了解更多可查看HashMap底層實現(xiàn)原理。動力節(jié)點在線學(xué)習(xí)教程，針對沒有任何Java基礎(chǔ)的讀者學(xué)習(xí),讓你從入門到精通,主要介紹了一些Java基礎(chǔ)的核心知識，讓同學(xué)們更好更方便的學(xué)習(xí)和了解Java編程，感興趣的同學(xué)可以關(guān)注一下。