在JDK1.8後,對HashMap源碼進行了更改,引入了紅黑樹。在這之前,HashMap實際上就是就是數組+鏈表的結構,由於HashMap是一張哈希表,其會產生哈希衝突,為瞭解決哈希衝突,HashMap採用了開鏈法,即對於用對象hashCode值計算哈希表數組下表時,當出現相同情況時,會在相同的地方 ...
在JDK1.8後,對HashMap源碼進行了更改,引入了紅黑樹。
在這之前,HashMap實際上就是就是數組+鏈表的結構,由於HashMap是一張哈希表,其會產生哈希衝突,為瞭解決哈希衝突,HashMap採用了開鏈法,即對於用對象hashCode值計算哈希表數組下表時,當出現相同情況時,會在相同的地方追加形成鏈表的形式。對於分佈均勻的情況下,僅僅是一個一維數組,查詢時時間複雜度為O(1),當分佈不均勻的時候,在有的地方會形成鏈表,極端情況下完全退化成一個鏈表,查詢時就需要遍歷整個鏈表,時間複雜度就為O(n),極為耗時。
在引入紅黑樹後,當滿足一定條件時,鏈表就會轉換成一棵紅黑樹。紅黑樹是一種AVL樹(自平衡查找二叉樹),相比於鏈表,其查找時的時間複雜度還是很優秀的(O(logn))!
先瞭解一下HashMap的模型:
其中的Node結點存放我們的鍵值對<K, V>;
首先,我們先瞭解HashMap給出的幾個重要指標:
1 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 預設的初始化容量大小為16 2 static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap最大容量1G 3 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 預設負載因數值0.75,用於擴容時的計算 4 static final int TREEIFY_THRESHOLD = 8; // 樹的閾值,當鏈表長度大於等於8時,由鏈表轉換成紅黑樹 5 static final int UNTREEIFY_THRESHOLD = 6; // 鏈表的閾值,暫時不清楚 6 static final int MIN_TREEIFY_CAPACITY = 64; // 最小樹容量64
以上就是幾個基本指標,其規定了在以後操作中的界限!
其中Node<K, V>是一個內部類,封裝了這個結點的所有信息,有如下幾個成員
1 final int hash; 2 final K key; 3 V value; 4 Node<K,V> next;
key和value不必多說,其中的hash是利用key對象的hashCode計算得到的,具有唯一性:
1 static final int hash(Object key) { 2 int h; 3 // 可以看到hash是根據對象的hashCode值來計算 4 // hashCode是一個int值,有32位 5 // 最後改變的是其低16位 6 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 7 }
其中的next就是為瞭解決哈希衝突,當產生哈希衝突時,next就可以指向一張鏈表,或者一棵黑樹!
接下來是幾個重要的成員:
1 transient Node<K,V>[] table; // 這就是真正的HashMap,一張哈希表,實際上就是由Node結點組成的一維數組 2 transient int size; // 記錄table中真正有效的結點個數,也就是鍵值對的個數 3 int threshold; // 用來記錄當前容量下,最適合存放多少鍵值對(容量*負載因數) 4 final float loadFactor; // 負載因數,若在構造方法沒有特別設置,都是預設0.75 5 transient int modCount; // 用來記錄操作數
看到這,我們先不急著往下進行,先仔細分析下這些成員之間的關係:
table:真正開闢的空間,其length就是真正的容量大小
size: 真正使用的空間,總的鍵值對的個數
threshold:這個就比較有意思,其決定了是否需要進行擴容的操作,是一個閾值!
比如說,在初始化時,預設的容量是16,那麼table的length就是16,其threshold=容量×負載因數=16×0.75=12,這就代表著,當size大於12時,就會進行擴容(容量會×2,threshold會根據新容量重新計算)的操作!
這樣做的目的很明確,就是為了減少哈希衝突!有效元素的個數少於哈希表的總大小時,其產生哈希衝突的可能性一定是小於相等情況的!
綜上可知,在非極限情況下(容量=threshold=MAXIMUM_CAPACITY=2^30)時,threshold總是小於容量,size總是不大於threshold!
這一切的做法,都是為了能夠減少哈希衝突產生的可能性!
說到這裡還是不能往下進行,我們需要知道Node中的hash成員是如何與table中的下標產生對應關係的,以及哈希衝突是如何產生的:
首先是關於hash值和table下標的映射:
1 index = hash & (table.length - 1)
這是一個非常巧妙的運算,當table.length滿足二的整數冪時,就滿足:
hash & (table.length - 1) == hash % table.length
例如:2%8 = 2 即:
0000 0010 2
&
0000 0111 (8 - 1)
0000 0010
二的整數冪減一得到的二進位數,其有效位全是1,通過&可以直接得到符合條件的有效位的值!
其實就是取餘,用餘數作為table的下標,而位運算的速度是比其餘快的多,所以採用了這種方式!
所以這就是為什麼table的大小必須是二的整數冪,以及擴容時都是乘2!
哈希衝突的產生:
以初始table.length = 16為例
對於hash = 1, 和 hash = 17來說,其對於16取餘的結果都是1,那麼這兩個不同的hash值對應了同一個table的下標,這就產生了哈希衝突!
先將HashMap簡單介紹到這,後續我會繼續分析HashMap,若有錯誤或不足之處,還請指出!
我在CSDN也放了一篇【Java】HashMap源碼分析——基本概念