HashMap不完全解讀

HashMap的必知點

HashMap是無序且不安全的資料結構。
存儲結構是數組 + 連結清單 + 紅黑樹 (門檻值為8 如果連結清單長度>=8則會把連結清單變成紅黑樹 )，數組中存儲元素Entry，存儲元素的位置被稱為桶，每個bucket有且僅有一個元素并指定索引，以實作快速通路。
HashMap 是以key–value對的形式存儲的，key值是唯一的（可以為null），一個key隻能對應着一個value，但是value是可以重複的。
HashMap 如果再次添加相同的key值，它會覆寫key值所對應的内容，這也是與HashSet不同的一點，Set通過add添加相同的對象，不會再添加到Set中去。
HashMap 提供了get方法，通過key值取對應的value值，但是HashSet隻能通過疊代器Iterator來周遊資料，找對象。

HashMap的新特性

jdk8中添加了紅黑樹，當連結清單長度大于等于8的時候連結清單會變成紅黑樹
連結清單新節點插傳入連結表的順序不同（jdk7是插入頭結點，jdk8因為要把連結清單變為紅黑樹是以采用插入尾節點）
resize的邏輯修改（jdk7會出現死循環，jdk8不會）

HashMap為什麼引入紅黑樹

為了解決jdk1.8以前hash沖突所導緻的鍊化嚴重的問題，因為連結清單結構的查詢效率是非常低的（O(n)），樹結構的查詢效率會高一些。

重寫hashCode()和equals()方法

HashMap可以提供快速通路能力，即通過key可以查詢到相應的value,通過哈希函數可以決定鍵值對的位置，在理想狀況下（不出現hash沖突），查詢的時間複雜度為O(1),當出現hash沖突時，使用開散清單解決沖突，對應一個特定hash值的位置存儲的是一個連結清單頭，指向hash到同一個位置的多個鍵值對組成的連結清單。

HashMap的資料存儲

HashMap的資料是存在Node[] table數組(哈希桶)中的，它是一個Entry數組，Entry是HashMap的一個靜态内部類。Entry封裝了hash（定位數組索引位置）、key、value，next是指向連結清單的下一個Node節點。

Map及Map.Entry

Map.Entry是Map的一個内部接口。

Map.Entry的常用方法：

keySet()方法傳回值是Map中key值的集合
entrySet()的傳回值也是傳回一個Set集合，此集合的類型為Map.Entry。

HashMap的put方法

HashMap put方法存儲流程

引用美團技術團隊的圖檔：

①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；

②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接建立節點添加，轉向⑥，如果table[i]不為空，轉向③；

③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆寫value，否則轉向④，這裡的相同指的是hashCode以及equals；

④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；

⑤.周遊table[i]，判斷連結清單長度是否大于8，大于8的話把連結清單轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行連結清單的插入操作；周遊過程中若發現key已經存在直接覆寫value即可；

⑥.插入成功後，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。

HashMap解決hash沖突（碰撞）

不同的對象具有不同的hash值，當兩個不同的對象計算出的hash值相同時便産生了hash沖突,HashMap使用數組+連結清單(鍊位址法)解決hash沖突。

map.put("key1","value1");
map.put("key 2","value 2");
	...
map.put("hashCode n","value n");

複制

調用map的put方法進行資料存儲時，首先根據key計算其hashCode,然後進行取模運算和高位運算來确定value的存儲位置，在後期的調用put方法時不同的key計算得到的位置可能是一樣的，這時會産生hash碰撞。

HashMap擴容

HashMap的容量與擴容機制

在HashMap其中一個構造函數中，可以指定HashMap的初始容量和負載因子，這兩個變量關系到HashMap的擴容。

負載因子是一個和擴容機制有關的值，門檻值(threshold) = 負載因子(loadFactor) x 容量(capacity) ，負載因子是0.75這是時間和空間的權衡。負載因子越大，Hash沖突的可能性就更大，負載因子越小，相同的資料，HashMap擴容的次數就越多，需要的空間就越大。
門檻值則指定了HashMap的最大容量（容納key-value的極限值）。

擴容條件

比如說目前的預設容器容量是16，負載因子是0.75,16*0.75=12，也就是說，容器中超過12個元素的時候就會進行擴容操作。HashMap以2的整數次幂擴容。

明确參數

bin:bucket，數組中存儲Entry位置
MAXIMUM_CAPACITY：最大容量（2的30次幂，1073741824）
DEFAULT_LOAD_FACTOR：負載因子（預設0.75）
TREEIFY_THRESHOLD: 連結清單轉紅黑樹門檻值
DEFAULT_INITIAL_CAPACITY：預設初始容量（2的4次幂16）

1.This map usually acts as a binned (bucketed) hash table

2.static final int MAXIMUM_CAPACITY = 1 << 30;

3.static final float DEFAULT_LOAD_FACTOR = 0.75f;

4.static final int UNTREEIFY_THRESHOLD = 6;

5.static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

resize源碼：

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //如果目前長度大于最大容器長度（2的30次幂 1073741824則直接傳回該對象，1073741824是極限長容量
            //static final int MAXIMUM_CAPACITY = 1 << 30;
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果目前長度小于最大容量且小于預設容量16，對原資料進行2倍擴容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //計算resize上限
        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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // 把每個bucket都移動到擴容後的buckets中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //省略移動bucket部分代碼
                   		  ...
        }
        return newTab;
    }

複制

參考文獻：

美團技術網站：Java 8系列之重新認識HashMap