【hashmap】HashMap原理及線程不安全詳解|哈希表原理

目錄

HashMap和HashTable差別(HashTable線程安全)

HashTable

HashMap

ConcurrentHashMap (已經放棄)

HashMap原理

1、put方法原理

 2、get方法原理

HashMap 擴容(resize)

HashMap的高并發問題(線程不安全)

哈希表原理：

HashMap和HashTable差別(HashTable線程安全)

HashTable

底層數組+連結清單實作，無論key還是value都不能為null，線程安全，實作線程安全的方式是在修改資料時鎖住整個HashTable，效率低，ConcurrentHashMap做了相關優化

初始size為11，擴容：newsize = oldsize*2+1

計算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

HashMap

底層數組+連結清單實作，可以存儲null鍵和null值，線程不安全

初始size為16，擴容：newsize = oldsize*2，size一定為2的n次幂

擴容針對整個Map，每次擴容時，原來數組中的元素依次重新計算存放位置，并重新插入

插入元素後才判斷該不該擴容，有可能無效擴容(插入後如果擴容，如果沒有再次插入，就會産生無效擴容)

當Map中元素總數超過Entry數組的75%，觸發擴容操作，為了減少連結清單長度，元素配置設定更均勻

計算index方法：index = hash & (tab.length – 1)

HashMap的初始值還要考慮加載因子:

哈希沖突：若幹Key的哈希值按數組大小取模後，如果落在同一個數組下标上，将組成一條Entry鍊，對Key的查找需要周遊Entry鍊上的每個元素執行equals()比較。

加載因子：為了降低哈希沖突的機率，預設當HashMap中的鍵值對達到數組大小的75%時，即會觸發擴容。是以，如果預估容量是100，即需要設定100/0.75＝134的數組大小。

空間換時間：如果希望加快Key查找的時間，還可以進一步降低加載因子，加大初始大小，以降低哈希沖突的機率。

ConcurrentHashMap (已經放棄)

底層采用分段的數組+連結清單實作，線程安全

通過把整個Map分為N個Segment，可以提供相同的線程安全，但是效率提升N倍，預設提升16倍。(讀操作不加鎖，由于HashEntry的value變量是 volatile的，也能保證讀取到最新的值。)

Hashtable的synchronized是針對整張Hash表的，即每次鎖住整張表讓線程獨占，ConcurrentHashMap允許多個修改操作并發進行，其關鍵在于使用了鎖分離技術

有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢後，又按順序釋放所有段的鎖

擴容：段内擴容(段内元素超過該段對應Entry數組長度的75%觸發擴容，不會對整個Map進行擴容)，插入前檢測需不需要擴容，有效避免無效擴容

HashMap原理

(更通俗的解釋：https://zhuanlan.zhihu.com/p/79507868)

HashMap的資料結構：

HashMap的資料結構為 數組+(連結清單或紅黑樹)，上圖

HashMap是一個用于存儲Key-Value鍵值對的集合，每一個鍵值對也叫做Entry。這些個鍵值對(Entry)分散存儲在一個數組當中，數組初始化長度為16，數組中的每一個元素初始值都是null，這個數組就是HashMap的主幹。

1、put方法原理(存儲過程)

當調用hashMap.put("apple", 0) ，插入一個Key為“apple"的元素。這時候我們需要利用一個哈希函數來确定Entry的插入位置(index)：

index =  Hash(“apple”)-----Hash中哈希函數計算出hashcode，再用取模(hashcode/數組長度)等方法得到index

假定最後計算出的index是2，那麼結果如下：

但是，因為HashMap的長度是有限的，當插入的Entry越來越多時，再完美的Hash函數也難免會出現index沖突的情況。比如下面這樣：

HashMap數組的每一個元素不止是一個Entry對象，也是一個連結清單的頭節點。每一個Entry對象通過Next指針指向它的下一個Entry節點。當新來的Entry映射到沖突的數組位置時，隻需要插入到對應的連結清單即可：

需要注意的是，新來的Entry節點插傳入連結表時，使用的是“頭插法”。 原因時HashMap的設計者認為後插入的元素被get的幾率更大。

 2、get方法原理

使用Get方法根據Key來查找Value的時候，發生了什麼呢？

首先會把輸入的Key做一次Hash映射，得到對應的index：

index =  Hash(“apple”)

由于剛才所說的Hash沖突，同一個位置有可能比對到多個Entry，這時候就需要順着對應連結清單的頭節點，一個一個向下來查找。假設我們要查找的Key是“apple”：

第一步，我們檢視的是頭節點Entry6，Entry6的Key是banana，顯然不是我們要找的結果。

第二步，我們檢視的是Next節點Entry1，Entry1的Key是apple，正是我們要找的結果。

之是以把Entry6放在頭節點，是因為HashMap的發明者認為，後插入的Entry被查找的可能性更大。

HashMap 擴容(resize)

HashMap的預設初始長度時16，并且每次自動擴充或者手動初始化時，長度必須時2的幂。

原因：

在于HashMap的數組下标算法，當put一個值時，會首先計算出hash code，根據hash code決定放在數組的位置，考慮效率問題并沒有采用取模的方式，而是采用按位與的方式

下面我們以“book"的Key來示範整個過程：

1.計算book的hashcode，結果為十進制的3029737，二進制的101110001110101110 1001。

2.假定HashMap長度是預設的16，計算Length-1的結果為十進制的15，二進制的1111。

3.把以上兩個結果做與運算，101110001110101110 1001 & 1111 = 1001，十進制是9，是以 index=9。

可以說，Hash算法最終得到的index結果，完全取決于Key的Hashcode值的最後幾位。

在這種情況下，如果數字的長度不是2的幂，會發生以下結果：

假設HashMap的長度是10，重複剛才的運算步驟：

單獨看這個結果，表面上并沒有問題。我們再來嘗試一個新的HashCode  101110001110101110 1011 ：

讓我們再換一個HashCode 101110001110101110 1111 試試  ：

雖然HashCode的倒數第二第三位從0變成了1，但是運算的結果都是1001。也就是說，當HashMap長度為10的時候，有些index結果的出現幾率會更大，而有些index結果永遠不會出現(比如0111)！ 這樣，顯然不符合Hash算法均勻分布的原則。 反觀長度16或者其他2的幂，Length-1的值是所有二進制位全為1，這種情況下，index的結果等同于HashCode後幾位的值。隻要輸入的HashCode本身分布均勻，Hash算法的結果就是均勻的。

HashMap的高并發問題(線程不安全)

HashMap是線程不安全的，原因就在于HashMap的rehash。rehash是HashMap擴容過程種的一個步驟。 HashMap的容量是有限的。

當經過多次元素插入，使得HashMap達到一定飽和度時，Key映射位置發生沖突的幾率會逐漸提高。 這時候，HashMap需要擴充它的長度，也就是進行Resize。 影響發生Resize的因素有兩個：

1.Capacity

HashMap的目前長度。上一期曾經說過，HashMap的長度是2的幂。

2.LoadFactor

HashMap負載因子，預設值為0.75f。

衡量HashMap是否進行Resize的條件如下：

HashMap.Size   >=  Capacity * LoadFactor

HashMap的擴容主要分為兩步：

1.擴容

建立一個新的Entry空數組，長度是原數組的2倍

2.ReHash

周遊原Entry數組，把所有的Entry重新Hash到新數組。為什麼要重新Hash呢？因為長度擴大以後，Hash的規則也随之改變。

讓我們回顧一下Hash公式：

index =  HashCode(Key) &  (Length - 1)

當原數組長度為8時，Hash運算是和111B做與運算；新數組長度為16，Hash運算是和1111B做與運算。Hash結果顯然不同。

ReHash的Java代碼如下：

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
           

以上過程單線程下不會出現問題，但是當兩個線程同時觸發resize的時候就有可能出現問題

假設一個HashMap已經到了Resize的臨界點。此時有兩個線程A和B，在同一時刻對HashMap進行Put操作：

此時達到Resize條件，兩個線程各自進行Rezie的第一步，也就是擴容：

這時候，兩個線程都走到了ReHash的步驟。讓我們回顧一下ReHash的代碼：

假如此時線程B周遊到Entry3對象，剛執行完紅框裡的這行代碼，線程就被挂起。對于線程B來說：

e = Entry3

next = Entry2

這時候線程A暢通無阻地進行着Rehash，當ReHash完成後，結果如下(圖中的e和next，代表線程B的兩個引用)：

直到這一步，看起來沒什麼毛病。接下來線程B恢複，繼續執行屬于它自己的ReHash。線程B剛才的狀态是：

e = Entry3

next = Entry2

當執行到上面這一行時，顯然 i = 3，因為剛才線程A對于Entry3的hash結果也是3。

我們繼續執行到這兩行，Entry3放入了線程B的數組下标為3的位置，并且e指向了Entry2。此時e和next的指向如下：

e = Entry2

next = Entry2

整體情況如圖所示：

接着是新一輪循環，又執行到紅框内的代碼行：

e = Entry2

next = Entry3

整體情況如圖所示：

接下來執行下面的三行，用頭插法把Entry2插入到了線程B的數組的頭結點：

整體情況如圖所示：

第三次循環開始，又執行到紅框的代碼：

e = Entry3

next = Entry3.next = null

最後一步，當我們執行下面這一行的時候，見證奇迹的時刻來臨了：

newTable[i] = Entry2

e = Entry3

Entry2.next = Entry3

Entry3.next = Entry2

連結清單出現了環形！

整體情況如圖所示：

此時，問題還沒有直接産生。當調用Get查找一個不存在的Key，而這個Key的Hash結果恰好等于3的時候，由于位置3帶有環形連結清單，是以程式将會進入死循環！

原文：https://my.oschina.net/muziH/blog/1596801

解釋2：https://coolshell.cn/articles/9606.html

哈希表原理：

https://www.cnblogs.com/time-read/p/10716403.html