面試需要了解的HashMap

java面試中，HashMap集合的面試基本是都會問到的。

哈希表（hash table）
也叫散列表，是一種非常重要的數據結構，應用場景及其豐富，許多緩存技術（比如memcached）的核心其實就是在內存中維護一張大的哈希表。

Map實現類

Java為數據結構中的映射定義了一個接口Map，主要有四個常用的實現類，分別是HashMap、Hashtable、LinkedHashMap和TreeMap。

針對這4個實現類做個簡單的說明：

(1) HashMap：它根據鍵的hashCode值存儲數據，大多數情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。 HashMap最多隻允許一條記錄的鍵為null，允許多條記錄的鍵值為null。HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導致數據的不一致。如果需要滿足線程安全，通常使用ConcurrentHashMap代替。

(2) Hashtable：Hashtable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，並且是線程安全的(方法上使用悲觀鎖synchronized)，任一時間只有一個線程能寫Hashtable，併發性不如ConcurrentHashMap，因為ConcurrentHashMap引入了分段鎖。Hashtable不建議使用，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換。

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

(4) TreeMap：TreeMap實現SortedMap接口，能夠把它保存的記錄根據鍵排序，默認是按鍵值的升序排序。如果使用排序的映射，建議使用TreeMap。在使用TreeMap時，key必須實現Comparable接口或者在構造TreeMap傳入自定義的Comparator，否則會拋出ClassCastException類型的異常。

存儲結構：jdk1.7是數組+鏈表，jdk1.8是數組+鏈表+紅黑樹。

hashmap底層結構

鏈表主要為了解決哈希衝突(也叫哈希碰撞)而存在的。主要是因為使用hashmap存儲數據的時候，兩個不同的元素(鍵值)，通過哈希函數得出的實際存儲地址相同。哈希衝突的解決方案有多種：開放定址法（發生衝突，繼續尋找下一塊未被佔用的存儲地址），再散列函數法，鏈地址法，而HashMap就是採用了鏈地址法。

JDK 1.8 對 HashMap 進行了比較大的優化，底層實現由之前的 “數組+鏈表” 改為 “數組+鏈表+紅黑樹”，當鏈表節點較少時仍然是以鏈表存在，當鏈表節點較多時（等於8，將會調用內部的treeifyBin方法）轉為紅黑樹。

JDK 1.8數組使用了Node，它實現了Map.Entry接口，本質是就是一個映射(鍵值對)。

初始化幾個重要的參數：

<code>int threshold;             // 所能容納的key-value對極限 
final float loadFactor;    // 負載因子
int modCount;  //修改的次數，用於fail-fast容錯
int size; //數組大小/<code>

Node[] table的初始化數組大小(length )默認值是16，負載因子(loadFactor)默認值是0.75，threshold是HashMap所能容納的最大數據量的Node(鍵值對)個數。threshold = length * loadFactor。得出負載因子越大，所能容納的鍵值對個數就越多。

put描述過程(查看源碼更清晰)

1、判斷數組是否為空，為空進行初始化，不為空，計算 k 的 hash 值，通過(n - 1) & hash計算應當存放在數組中的下標 index。

2、查看 table[index] 是否存在數據，沒有數據就構造一個Node節點存放在 table[index] 中。存在數據，說明發生了hash衝突(存在二個節點key的hash值一樣), 繼續判斷key是否相等，相等，用新的value替換原數據(onlyIfAbsent為false)，如果不相等，判斷當前節點類型是不是樹型節點，如果是樹型節點，創造樹型節點插入紅黑樹中；

3、如果不是樹型節點，創建普通Node加入鏈表中；判斷鏈表長度是否大於 8，大於的話鏈表轉換為紅黑樹；

4、插入完成之後判斷當前節點數是否大於閾值，如果大於開始擴容為原數組的二倍

主要代碼實現：

<code>public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
 
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    // 1.校驗table是否為空或者length等於0，如果是則調用resize方法進行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2.通過hash值計算索引位置，將該索引位置的頭節點賦值給p，如果p為空則直接在該索引位置新增一個節點即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // table表該索引位置不為空，則進行查找
        Node e; K k;
        // 3.判斷p節點的key和hash值是否跟傳入的相等，如果相等, 則p節點即為要查找的目標節點，將p節點賦值給e節點
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4.判斷p節點是否為TreeNode, 如果是則調用紅黑樹的putTreeVal方法查找目標節點
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 5.走到這代表p節點為普通鏈表節點，則調用普通的鏈表方法進行查找，使用binCount統計鏈表的節點數
            for (int binCount = 0; ; ++binCount) {
                // 6.如果p的next節點為空時，則代表找不到目標節點，則新增一個節點並插入鏈表尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 7.校驗節點數是否超過8個，如果超過則調用treeifyBin方法將鏈表節點轉為紅黑樹節點，
                    // 減一是因為循環是從p節點的下一個節點開始的
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 8.如果e節點存在hash值和key值都與傳入的相同，則e節點即為目標節點，跳出循環
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;  // 將p指向下一個節點
            }
        }
        // 9.如果e節點不為空，則代表目標節點存在，使用傳入的value覆蓋該節點的value，並返回oldValue
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 用於LinkedHashMap
            return oldValue;
        }
    }
    ++modCount;
    // 10.如果插入節點後節點數超過閾值，則調用resize方法進行擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);  // 用於LinkedHashMap
    return null;
}/<code> 

resize擴容機制

兩個重要屬性：

<code>Capacity：HashMap當前長度。
LoadFactor：負載因子，默認值0.75f。/<code>

主要兩個步驟：

1、創建一個新的Entry空數組，長度是原數組的2倍。

2、遍歷原Entry數組，把所有的Entry重新Hash到新數組。

為啥要重新Hash！！！臥槽這個問題！有點知識盲區呀！有沒有很懵逼！直接複製過去不香麼

這裡我們回想下計算index的公式：index = HashCode（Key） & （Length - 1），原來長度（Length）是8你位運算出來的值是2 ，新的長度是16你位運算出來的值明顯不一樣了。

代碼全部貼出來著實有點噁心，就分幾個步驟說了：

一、擴容：如果超過了數組的最大容量，那麼就直接將閾值設置為整數最大值，然後如果沒有超過，那就擴容為原來的2倍。

<code>if (oldCap > 0) {
      if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
      }
      else if ((newCap = oldCap < 
< 1) < MAXIMUM_CAPACITY &&
          oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; 
}/<code>

二、設置閾值：如果閾值(oldThr)已經初始化過了，新閾值(newCap)直接使用舊的閾值。如果沒有初始化，那就初始化一個新的數組容量和新的閾值。最後為當前的容量閾值賦值。

<code>//第二部分：設置閾值
else if (oldThr > 0)
      newCap = oldThr;
else {    // 沒有初始化閾值那就初始化一個默認的容量和閾值
      newCap = DEFAULT_INITIAL_CAPACITY;
      newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
      float ft = (float)newCap * loadFactor;
      newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
}
//為當前的容量閾值賦值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;/<code>

三、複製數組到新數組(這個代碼就不貼了，大家有興趣自己去研究下)