在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源碼分析——基本概念
