1 一般資料結構及特點
2 HashMap基本屬性說明
3 HashMap 資料結構
- 3.1建構式
- 3.2 Node<k,v>分析
4 put程序分析
- 4.1 擴容方法resize()分析
- 4.2 put方法分析
5 關于HashMap
- 5.1 HashMap如何實作put、get操作時間復雜度為O(1)~O(n)?
- 5.2 HashMap什么時候從單節點轉成鏈表又是什么時候從鏈表轉成紅黑樹？
- 5.3 HashMap初始化時為什么要給自定義的初始容量？
- 5.4 HashMap如何保證容量始終是2的冪？
- 5.5 HashMap為何要保證容量始終是2的冪
- 5.6 HashMap計算hash值
  - 5.6.1 key的hash值>>>16，為什么要這樣做呢？
- 5.7 HashMap為什么是執行緒不安全的？
6 get 程序分析

特別：下文的“容量”、“陣列長度”，“capacity” 都是指底層陣列長度，即 table.length

1 一般資料結構及特點

陣列：占用連續記憶體的資料結構，查找容易[O(1)]，插入困難[O(n)]
鏈表：由一組指向（單向或者雙向）的節點連接的資料結構，記憶體不連續，查找困難，但插入洗掉容易
哈希表：插入洗掉查找都容易的資料結構
陣列下標是通過：（Node<K, V>[] 的容量-1）&（hash(key)）的出來的

本章要解決的問題：

HashMap的資料結構實作方式
HashMap是怎么做到為get、put操作提供穩定的時間復雜度的
HashMap什么時候從單節點轉成鏈表又是什么時候從鏈表轉成紅黑樹
HashMap初始化時為什么要給自定義的初始容量，
HashMap如何保證容量始終是2的冪
HashMap為何要保證容量始終是2的冪
HashMap的hash值如何計算
HashMap為什么是執行緒不安全的

2 HashMap基本屬性說明

常量部分：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認初始容量 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默認加載因子
static final int TREEIFY_THRESHOLD = 8;  //鏈表轉紅黑樹閾值
static final int UNTREEIFY_THRESHOLD = 6; //紅黑樹轉鏈表閾值
static final int MIN_TREEIFY_CAPACITY = 64;  //鏈表轉轉紅黑樹的陣列最小容量
transient int size; //HashMap的元素個數

default_initial_capacity：初始容量=16
maximum_capacity：最大容量=1<<30，
default_load_factor：負載因子=0.75，
threshold：下一個觸發擴容操作的閾值，threshold = capacity * load_factor，當元素數量(size值)超過閾值時觸發擴容，新容量是舊容量2倍，
treeify_threshold：鏈表轉紅黑樹時鏈表長度閾值=8
untreeify_threshold：紅黑樹轉鏈表閾值=6，紅黑樹節點小于6就會轉成鏈表，
Node<K, V> implements Map.Entry<K, V> ：HashMap存放資料的基本單位，里面存有hash值、key、value、next，
Node<K, V>[] table：存放Node節點的陣列，HashMap底層陣列，陣列元素可以為單節點Node、多節點鏈表、多節點紅黑樹，
size：成員變數，表示當前Map的鍵值對數量，在put、remove、clear操作，會修改該值，擴容也是通過閾值跟size進行比較決定

3 HashMap 資料結構

HashMap是一個Node型別的陣列，每個元素可以為單節點、鏈表、紅黑樹，
Java8之前，HashMap的資料結構如下：

陣列+鏈表：鏈表是為了解決hash沖突

Java8，HashMap的資料結構如下：
陣列+鏈表+紅黑樹

3.1建構式

Tips：

確定加載因子

根據初始容量引數重新計算擴容閾值（大于或等于初始容量且一定等于2的冪的那個數）
tableSizeFor(initialCapacity):確定擴容閾值：大于或等于初始容量且一定等于2的冪的那個數；比如cap=8則回傳8；cap=9則回傳16

原始碼分析如下：

//建構式一：無參建構式：加載因子（0.75）和初始容量（16）分別使用默認值
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//建構式二：
//指定初始容量，呼叫HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//建構式三：同時指定初始容量和加載因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;//初始容量不能超過最大容量：
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
    this.loadFactor = loadFactor;
    //  確定擴容閾值：大于或等于初始容量且一定等于2的冪的那個數；比如cap=8則回傳8；cap=9則回傳16
    this.threshold = tableSizeFor(initialCapacity);
}
//建構式三：創建一個跟引數有相同結構的map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

3.2 Node<k,v>分析

tips：一個簡單的K-V模型的資料體，提供對key value的set get操作
原始碼如下：

/**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = https://www.cnblogs.com/knowledgeispower/p/value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key +"=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value); // key value 的hash值再做異或運算
        }

        public final V setValue(V newValue) {
            V oldValue = https://www.cnblogs.com/knowledgeispower/p/value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

4 put程序分析

4.1 擴容方法resize()分析

HashMap的容量變化通常存在以下幾種情況：

空引數的建構式：實體化的HashMap默認內部陣列是null，即沒有實體化，第一次呼叫put方法時，則會開始第一次初始化擴容，長度為16，【懶加載】
有參建構式：用于指定容量，根據閾值計算方式【大于或等于初始容量且一定等于2的冪的那個數】，將這個數設定賦值給閾值，第一次呼叫put方法時，會將閾值賦值給容量（第一步），然后讓 閾值=負載因子X容量（第二步）
，（因此并不是我們手動指定了容量就一定不會觸發擴容，超過閾值后一樣會擴容！！）
如果不是第一次擴容，則容量變為原來的2倍，閾值也變為原來的2倍，（負載因子還是不變）
首次put時，先會觸發擴容（底層table初始化），然后存入資料，然后判斷是否需要擴容；不是首次put，則不再初始化，直接存入資料，然后再判斷是否需要擴容；

參看原始碼：

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//當前陣列
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //非首次put，擴容閾值變為原來2倍；容量變為原來的2倍
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;//達到最大值，不能擴容，回傳當前陣列
            }
            //陣列容量擴大為原來2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // 將擴容閾值變為原來2倍
        }
        
        //第一次 put 的時候，【對應使用 new HashMap(int initialCapacity) 初始化后】
        else if (oldThr > 0) 
            newCap = oldThr; //如果初始化Map時指定了初始容量，則陣列容量=擴容閾值（參照閾值的計算）
        
        //第一次 put 的時候 ，【對應使用 new HashMap() 初始化后】
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;//沒有指定初始容量，則陣列容量=默認初始容量
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//擴容閾值=加載因子*默認初始容量=12
        }

        //第一次put且有指定初始容量時 ：重新計算擴容閾值：新擴容閾值=加載因子*新陣列長度
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;

       //計算好容量初始化一個新的陣列
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //如果第一次put，這里就直接回傳newTab，擴容程序結束；
        table = newTab;
        if (oldTab != null) {
        // 開始遍歷原陣列，進行資料遷移，
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)//陣列當前位置不存在鏈表或者紅黑樹，則直接put到該位置
                        newTab[e.hash & (newCap - 1)] = e; //回傳單節點的Node陣列
                    else if (e instanceof TreeNode)
                        //紅黑樹
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { 
                        //鏈表
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

4.2 put方法分析

原始碼分析：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * @param hash：key的hash值
     * @param onlyIfAbsent  ：false表示key存在時，覆寫value
     * @param evict if false, the table is in creation mode.  待補充
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
           //第一次put，先執行陣列初始化操作
            n = (tab = resize()).length;
        //當前key對應的陣列下標沒有元素，則直接初始化新的Node到該陣列位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null); //注意此時Node沒有Next
        else {
        //當前key對應的陣列下標已經存在元素
            Node<K,V> e; K k;
            // 情況一：//該位置的元素跟新put進來的資料key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;    //注意這里是參考的賦值，因此后面e.value=https://www.cnblogs.com/knowledgeispower/p/value可以實作value覆寫
            //情況二：當前位置是紅黑樹結構
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                //情況三：當前位置是鏈表結構
                for (int binCount = 0; ; ++binCount) {
                    //遍歷到達鏈表末端
                    if ((e = p.next) == null) {
                        //創建新的Node并放在鏈表的末端
                        p.next = newNode(hash, key, value, null);
                        // treeify_threshold 為 8，所以，如果新插入的值是鏈表中的第 8 個，將鏈表轉換為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //在鏈表當前位置找到相同的key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break; //這里break，代碼后面統一對e進行value的覆寫處理
                    //此時既未遍歷到鏈表末端，也沒有發現key相等，則繼續鏈表遍歷
                    p = e;   //這個賦值，相當于鏈表的遍歷，尾部指向下一個節點的頭部，實作鏈表遍歷
                }
            }
            if (e != null) { // existing mapping for key  key相等時
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;  //新的value覆寫舊的value值
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
        //每次put操作完成后，size自增；
        //如果size超過閾值，則在put完成后，再次執行擴容
            resize();
        afterNodeInsertion(evict);//父類抽象方法的實作，HashMap不做任何實作
        return null;
    }

第一次put時擴容程序如下：

容量：C
加載因子：F
擴容閾值：T

------ 1、無參初始化：
F=0.75
C=0
T=0

------ 2、有參初始化：容量引數=7
F=0.75
C=0
T=tableSizeFor(7)=8  //1、2、4、8 ，，，大于7 所以取8

------ 3、第一次put && 無參初始化時
F=0.75
C=16（默認容量）
T=16*0.75=12

------ 4、第一次put && 有參初始化時
F=0.75
C=T=8 // 容量=閾值
T=8*0.75=6 // 閾值更新：容量*加載因子

5 關于HashMap

5.1 HashMap如何實作put、get操作時間復雜度為O(1)~O(n)?

首先，對于陣列的元素，如果知道index，那查找的復雜度就是O(1)級別
對于get操作，首先根據key計算出hash值，而這個hash值 執行操作hash&(n-1)就是它所在的index，在最好的情況下，該index只有一個節點且hash值與key的hash值相等，那么時間的復雜度就是O(1)，當該節點為鏈表或者紅黑樹時，時間復雜度會上升，但是由于HashMap的優化（鏈表長度、紅黑樹長度相對HashMap容量不會過長，過長會觸發resize操作），所以 最壞的情況也就是O(n) ,可能還會小于這個值，【鏈表的查詢時間復雜度是：O (n)，紅黑樹是 O(logN)，比O (n)更小】
對于put操作，我們知道，陣列插入元素的成本是高昂的，HashMap巧妙的 使用鏈表和紅黑樹代替了陣列插入元素需要移動后續元素的消耗，這樣在最好的情況下，插入一個元素，該index位置恰好沒有元素的話，時間復雜度就是O(1),當該位置有元素且為鏈表或者紅黑樹的情況下，時間復雜度會上升，但是最壞的情況下也就是O(n)，

5.2 HashMap什么時候從單節點轉成鏈表又是什么時候從鏈表轉成紅黑樹？

單節點轉鏈表：當計算出來的index處有元素，且元素是單節點時，則該節點變為鏈表；
鏈表轉紅黑樹有兩個條件：
1. 鏈表長度大于TREEIFY_THRESHOLD，默認閾值是8；
2. HashMap長度大于64

5.3 HashMap初始化時為什么要給自定義的初始容量？

不指定初始容量時，HashMap底層陣列的在第一次put值時，陣列長度為默認初始長度即16，加載因子為0.75，擴容閾值為16*0.75=12；當元素數量大于12時，底層陣列進行擴容，長度翻倍為32，擴容閾值翻倍為24，依次類推；
指定初始容量時，假設初始容量為C=1000，HashMap底層陣列的在第一次put值時，陣列長度初始化為 1024，擴容閾值為1024*0.75=768；當元素數量大于768時，底層陣列進行擴容，長度和閾值同時翻倍，
因此，當HashMap元素足夠多時，不指定初始容量要比指定初始容量進行更多次的擴容，擴容涉及陣列拷貝、鏈表或紅黑樹重建，消耗更多性能，
根據要使用的HashMap大小確定初始容量，這也不是說為了避免擴容初始容量給的越大越好，越大申請的記憶體就越大，如果你沒有這么多資料去存，又會造成hash值過于離散，增加查詢或修改的時間復雜度，

5.4 HashMap如何保證容量始終是2的冪？

HashMap使用方法tableSizeFor()來保證無論你給值是什么，回傳的一定是2的冪

/**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }

5.5 HashMap為何要保證容量始終是2的冪

HashMap在定位元素在陣列的index時，運算公式是 (n-1)&hash ,n為陣列的長度，如果容量始終是2的次冪，例如 0000 0000 0000 0000 0000 0000 1000 0000，則n-1的二進制形式為：0000 0000 0000 0000 0000 0000 0111 1111 ，低位區一定是1，在進行 (n-1)&hash，hash低位區的0、1特征能夠保留
因此，容量始終是2的冪，這樣 下標index值的取值范圍更廣，減少hash碰撞，

5.6 HashMap計算hash值

1、帶著疑問：
key的hashCode為什么右移16位后再進行異或運算？

2、關于 | & ^ 三種運算的特征說明：

^按位異或運算：位相同回傳0，不同回傳1；可推匯出：任何數跟0異或回傳任何數，任何數跟1異或回傳對應的取反

異或運算能更好的保留各部分的特征，如果采用邏輯與&運算計算出來的值會向0靠攏（00得0，01得0，11得1 因此0的概率2/3），采用邏輯或|運算計算出來的值會向1靠攏 (00得0，01得1，11得1，因此1的概率為2/3)

3、hash()原始碼：

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    //key.hashCode() ;hashCode是Object物件的一個native方法，由作業系統實作，跟記憶體地址存在某種映射關系

4、進入分析：

5.6.1 key的hash值>>>16，為什么要這樣做呢？

h值右移16后，高16位都為0，這樣h^(h>>>16)時，高16位的值不會有任何變化，但是低16位的值混雜了key的高16位的值，從而增加了hash值的復雜度，進一步減少了hash值一樣的概率，
計算陣列下標公式：(n-1)&hash，n-1的結果：高位趨于0；&運算的結果：高16位向0靠攏，hash的高位特征丟失
因此，如果我們不做hash值的移位和異或運算，那么在計算陣列index時將丟失高區特征

簡單點：

因為：(n-1)&hash中，hash的高位數將被陣列長度的二進制碼鎖屏蔽，為確保hash的高位盡可能利用，就先對hash值先右移16位，再跟原hash值進行異或運算，同時保留高位和低位特征，

陣列長度二進制碼屏蔽是什么意思？

陣列長度的資料型別int轉化為32位的二進制，因為長度值對比最大值（2的32位）總是比較小的，所以它的高位趨向0，與其他數進行&運算后，結果值的高位趨向0，那么其他數的高位特征就丟失了

下面用例子分析：

### 計算hash
hashCode：     					0000 0000 0101 0000 0000 0000 1111 1010
hashCode>>>16: 					0000 0000 0000 0000 0000 0000 0101 0000
hashCode^hashCode>>>16: 		0000 0000 0101 0000 0000 0000 0110 1010

hash=hashCode^hashCode>>>16 	0000 0000 0101 0000 0000 0000 0110 1010

### 計算index時：
(n-1) (假設n=16)            		0000 0000 0000 0000 0000 0000 0000 1111  
(n-1)&hash                  	0000 0000 0000 0000 0000 0000 0000 1010

仔細觀察上文不難發現，高16位很有可能會被陣列長度的二進制碼鎖屏蔽，
如果我們不做移位異或運算，那么在計算陣列index時將丟失高區特征

5.7 HashMap為什么是執行緒不安全的？

它沒有任何的鎖或者同步等多執行緒處理機制，無法控制并發下導致的執行緒沖突，
如果想要執行緒安全的使用基于hash表的map，可以使用ConcurrentHashMap，該實作get操作是無鎖的，put操作也是分段鎖，性能很好

6 get 程序分析

計算 key 的 hash 值，根據 hash 值找到對應陣列下標: hash & (length-1)
判斷陣列該位置處的元素是否剛好就是我們要找的，如果不是，走第三步
判斷該元素型別是否是 TreeNode，如果是，用紅黑樹的方法取資料，如果不是，走第四步
遍歷鏈表，直到找到相等(==或equals)的 key

參考資料：

[良許-HashMap原始碼實作分析]：https://www.cnblogs.com/yychuyu/p/13357218.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544170.html

標籤：Java

上一篇：Rpc-實作Zookeeper注冊中心

下一篇：關于靜態代碼塊和匿名代碼塊以及結構體在程式運行程序中的呼叫順序實驗（續）

2、HashMap原始碼分析