HashMap 簡介

HashMap是一個基于哈希表實現的無序的key-value容器，它鍵和值允許設置為 null，同時它是線程不安全的。

HashMap 底層實現

•  在jdk 1.7中HashMap是以數組+鏈表的實現的
•  在jdk1.8開始引入紅黑樹，HashMap底層變成了數組+鏈表+紅黑樹實現

紅黑樹簡介

紅黑樹是一種特殊的平衡二叉樹，它有如下的特征：

•  節點是紅色或黑色
•  根節點是黑色的
•  所有葉子都是黑色。（葉子是NULL節點）
•  每個紅色節點的兩個子節點都是黑色的（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）
•  從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

所以紅黑樹的時間復雜度為: O(lgn)。

jdk1.8：數組+鏈表+紅黑樹

HashMap的底層首先是一個數組，元素存放的數組索引值就是由該元素的哈希值（key-value中key的哈希值）確定的，這就可能產生一種特殊情況——不同的key哈希值相同。

在這樣的情況下，于是引入鏈表，如果key的哈希值相同，在數組的該索引中存放一個鏈表，這個鏈表就包含了所有key的哈希值相同的value值，這就解決了哈希沖突的問題。

但是如果發生大量哈希值相同的特殊情況，導致鏈表很長，就會嚴重影響HashMap的性能，因為鏈表的查詢效率需要遍歷所有節點。于是在jdk1.8引入了紅黑樹，當鏈表的長度大于8，且HashMap的容量大于64的時候，就會將鏈表轉化為紅黑樹。 

// jdk1.8  
// HashMap#putVal  
// binCount 是該鏈表的長度計數器，當鏈表長度大于等于8時，執行樹化方法  
// TREEIFY_THRESHOLD = 8  
if (binCount >= TREEIFY_THRESHOLD - 1)  
    treeifyBin(tab, hash);  
// HashMap#treeifyBin      
final void treeifyBin(Node<K,V>[] tab, int hash) {  
    int n, index; Node<K,V> e;  
    // MIN_TREEIFY_CAPACITY=64  
    // 若 HashMap 的大小小于64，僅擴容，不樹化  
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  
        resize();  
    else if ((e = tab[index = (n - 1) & hash]) != null) {  
        TreeNode<K,V> hd = null, tl = null;  
        do { 
             TreeNode<K,V> p = replacementTreeNode(e, null);  
            if (tl == null)  
                hd = p; 
             else {  
                p.prev = tl; 
                 tl.next = p;  
            }  
            tl = p;  
        } while ((ee = e.next) != null);  
        if ((tab[index] = hd) != null)  
            hd.treeify(tab);  
    }  
} 

加載因子為什么是0.75

所謂的加載因子，也叫擴容因子或者負載因子，它是用來進行擴容判斷的。

假設加載因子是0.5，HashMap初始化容量是16，當HashMap中有16 * 0.5=8個元素時，HashMap就會進行擴容操作。

而HashMap中加載因子為0.75，是考慮到了性能和容量的平衡。

由加載因子的定義，可以知道它的取值范圍是(0, 1]。

•  如果加載因子過小，那么擴容門檻低，擴容頻繁，這雖然能使元素存儲得更稀疏，有效避免了哈希沖突發生，同時操作性能較高，但是會占用更多的空間。
•  如果加載因子過大，那么擴容門檻高，擴容不頻繁，雖然占用的空間降低了，但是這會導致元素存儲密集，發生哈希沖突的概率大大提高，從而導致存儲元素的數據結構更加復雜（用于解決哈希沖突），最終導致操作性能降低。
•  還有一個因素是為了提升擴容效率。因為HashMap的容量（size屬性，構造函數中的initialCapacity變量）有一個要求：它一定是2的冪。所以加載因子選擇了0.75就可以保證它與容量的乘積為整數。 

// 構造函數  
public HashMap(int initialCapacity, float loadFactor) {  
    // ……  
    this.loadFactor = loadFactor;// 加載因子  
    this.threshold = tableSizeFor(initialCapacity);  
}  
/**  
 * Returns a power of two size for the given target capacity.返回2的冪  
 * MAXIMUM_CAPACITY = 1 << 30  
 */  
static final int tableSizeFor(int cap) {  
    int n = cap - 1;  
    n |= n >>> 1;  
    n |= n >>> 2; 
    n |= n >>> 4;  
    n |= n >>> 8;  
    n |= n >>> 16;  
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;  
} 

HashMap 的容量為什么是2的 n 次冪

HashMap的默認初始容量是16，而每次擴容是擴容為原來的2倍。這里的16和2倍就保證了HashMap的容量是2的n次冪，那么這樣設計的原因是什么呢？

原因一：與運算高效

與運算&，基于二進制數值，同時為1結果為1，否則就是0。如1&1=1,1&0=0,0&0=0。使用與運算的原因就是對于計算機來說，與運算十分高效。

原因二：有利于元素充分散列，減少 Hash 碰撞

在給HashMap添加元素的putVal函數中，有這樣一段代碼： 

// n為容量，hash為該元素的hash值  
if ((p = tab[i = (n - 1) & hash]) == null)  
    tab[i] = newNode(hash, key, value, null); 

它會在添加元素時，通過i = (n - 1) & hash計算該元素在HashMap中的位置。

當 HashMap 的容量為 2 的 n 次冪時，他的二進制值是100000……（n個0），所以n-1的值就是011111……（n個1），這樣的話(n - 1) & hash的值才能夠充分散列。

舉個例子，假設容量為16，現在有哈希值為1111，1110，1011，1001四種將被添加，它們與n-1(15的二進制=01111)的哈希值分別為1111、1110、1110、1011，都不相同。

而假設容量不為2的n次冪，假設為10，那么它與上述四個哈希值進行與運算的結果分別是：0101、0100、0001、0001。

可以看到后兩個值發生了碰撞，從中可以看出，非2的n次冪會加大哈希碰撞的概率。所以 HashMap 的容量設置為2的n次冪有利于元素的充分散列。

參考：HashMap初始容量為什么是2的n次冪及擴容為什么是2倍的形式

HashMap 是如何導致死循環的

HashMap會導致死循環是在jdk1.7中，由于擴容時的操作是使用頭插法，在多線程的環境下可能產生循環鏈表，由此導致了死循環。在jdk1.8中改為使用尾插法，避免了該死循環的情況。