HashMap奪命14問,你能堅持到第幾問?

語言: CN / TW / HK

關注公眾號:IT老哥,每天閱讀一篇乾貨文章,一年後你會發現一個不一樣的自己。

1. HashMap的底層資料結構是什麼?

在JDK1.7中和JDK1.8中有所區別:

在JDK1.7中,由”陣列+連結串列“組成,陣列是HashMap的主體,連結串列則是主要為了解決雜湊衝突而存在的。

在JDK1.8中,有“陣列+連結串列+紅黑樹”組成。當連結串列過長,則會嚴重影響HashMap的效能,紅黑樹搜尋時間複雜度是O(logn),而連結串列是O(n)。因此,JDK1.8對資料結構做了進一步的優化,引入了紅黑樹,連結串列和紅黑樹在達到一定條件會進行轉換:

  • 當連結串列超過8且陣列長度(資料總量)超過64才會轉為紅黑樹

  • 將連結串列轉換成紅黑樹前會判斷,如果當前陣列的長度小於64,那麼會選擇先進行陣列擴容,而不是轉換為紅黑樹,以減少搜尋時間。

圖片

2. 說一下HashMap的特點

  • hashmap存取是無序的

  • 鍵和值位置都可以是null,但是鍵位置只能是一個null

  • 鍵位置是唯一的,底層的資料結構是控制鍵的

  • jdk1.8前資料結構是:連結串列+陣列jdk1.8之後是:陣列+連結串列+紅黑樹

  • 閾值(邊界值)>8並且陣列長度大於64,才將連結串列轉換成紅黑樹,變成紅黑樹的目的是提高搜尋速度,高效查詢

3. 解決hash衝突的辦法有哪些?HashMap用的哪種?

解決Hash衝突方法有:開放定址法、再雜湊法、鏈地址法(HashMap中常見的拉鍊法)、簡歷公共溢位區。HashMap中採用的是鏈地址法。

  • 開放定址法也稱為再雜湊法,基本思想就是,如果p=H(key)出現衝突時,則以p為基礎,再次hash,p1=H(p),如果p1再次出現衝突,則以p1為基礎,以此類推,直到找到一個不衝突的雜湊地址pi。因此開放定址法所需要的hash表的長度要大於等於所需要存放的元素,而且因為存在再次hash,所以只能在刪除的節點上做標記,而不能真正刪除節點

  • 再雜湊法(雙重雜湊,多重雜湊),提供多個不同的hash函式,R1=H1(key1)發生衝突時,再計算R2=H2(key1),直到沒有衝突為止。這樣做雖然不易產生堆集,但增加了計算的時間。

  • 鏈地址法(拉鍊法),將雜湊值相同的元素構成一個同義詞的單鏈表,並將單鏈表的頭指標存放在雜湊表的第i個單元中,查詢、插入和刪除主要在同義詞連結串列中進行,連結串列法適用於經常進行插入和刪除的情況。

  • 建立公共溢位區,將雜湊表分為公共表和溢位表,當溢位發生時,將所有溢位資料統一放到溢位區

注意開放定址法和再雜湊法的區別是

  • 開放定址法只能使用同一種hash函式進行再次hash,再雜湊法可以呼叫多種不同的hash函式進行再次hash

4. 為什麼要在陣列長度大於64之後,連結串列才會進化為紅黑樹

在陣列比較小時如果出現紅黑樹結構,反而會降低效率,而紅黑樹需要進行左旋右旋,變色,這些操作來保持平衡,同時陣列長度小於64時,搜尋時間相對要快些,總之是為了加快搜索速度,提高效能

JDK1.8以前HashMap的實現是陣列+連結串列,即使雜湊函式取得再好,也很難達到元素百分百均勻分佈。當HashMap中有大量的元素都存放在同一個桶中時,這個桶下有一條長長的連結串列,此時HashMap就相當於單鏈表,假如單鏈表有n個元素,遍歷的時間複雜度就從O(1)退化成O(n),完全失去了它的優勢,為了解決此種情況,JDK1.8中引入了紅黑樹(查詢的時間複雜度為O(logn))來優化這種問題

5. 為什麼載入因子設定為0.75,初始化臨界值是12?

HashMap中的threshold是HashMap所能容納鍵值對的最大值。計算公式為length*LoadFactory。也就是說,在陣列定義好長度之後,負載因子越大,所能容納的鍵值對個數也越大

loadFactory越趨近於1,那麼陣列中存放的資料(entry也就越來越多),資料也就越密集,也就會有更多的連結串列長度處於更長的數值,我們的查詢效率就會越低,當我們新增資料,產生hash衝突的概率也會更高

預設的loadFactory是0.75,loadFactory越小,越趨近於0,陣列中個存放的資料(entry)也就越少,表現得更加稀疏

圖片

0.75是對空間和時間效率的一種平衡選擇

如果負載因子小一些比如是0.4,那麼初始長度16*0.4=6,陣列佔滿6個空間就進行擴容,很多空間可能元素很少甚至沒有元素,會造成大量的空間被浪費

如果負載因子大一些比如是0.9,這樣會導致擴容之前查詢元素的效率非常低

loadfactory設定為0.75是經過多重計算檢驗得到的可靠值,可以最大程度的減少rehash的次數,避免過多的效能消耗

6. 雜湊表底層採用何種演算法計算hash值?還有哪些演算法可以計算出hash值?

hashCode方法是Object中的方法,所有的類都可以對其進行使用,首先底層通過呼叫hashCode方法生成初始hash值h1,然後將h1無符號右移16位得到h2,之後將h1與h2進行按位異或(^)運算得到最終hash值h3,之後將h3與(length-1)進行按位與(&)運算得到hash表索引

其他可以計算出hash值的演算法有

  • 平方取中法

  • 取餘數

  • 偽隨機數法

7. 當兩個物件的hashCode相等時會怎樣

hashCode相等產生hash碰撞,hashCode相等會呼叫equals方法比較內容是否相等,內容如果相等則會進行覆蓋,內容如果不等則會連線到連結串列後方,連結串列長度超過8且陣列長度超過64,會轉變成紅黑樹節點

8. 何時發生雜湊碰撞和什麼是雜湊碰撞,如何解決雜湊碰撞?

只要兩個元素的key計算的hash碼值相同就會發生hash碰撞,jdk8之前使用連結串列解決雜湊碰撞,jdk8之後使用連結串列+紅黑樹解決雜湊碰撞

9. HashMap的put方法流程

以jdk8為例,簡要流程如下:

  1. 首先根據key的值計算hash值,找到該元素在陣列中儲存的下標

  2. 如果陣列是空的,則呼叫resize進行初始化;

  3. 如果沒有雜湊衝突直接放在對應的陣列下標裡

  4. 如果衝突了,且key已經存在,就覆蓋掉value

  5. 如果衝突後是連結串列結構,就判斷該連結串列是否大於8,如果大於8並且陣列容量小於64,就進行擴容;如果連結串列節點數量大於8並且陣列的容量大於64,則將這個結構轉換成紅黑樹;否則,連結串列插入鍵值對,若key存在,就覆蓋掉value

  6. 如果衝突後,發現該節點是紅黑樹,就將這個節點掛在樹上

圖片

10. HashMap的擴容方式

HashMap在容量超過負載因子所定義的容量之後,就會擴容。java裡的陣列是無法自己擴容的,將HashMap的大小擴大為原來陣列的兩倍

我們來看jdk1.8擴容的原始碼

```     final Node[] resize() {         //oldTab:引用擴容前的雜湊表         Node[] oldTab = table;         //oldCap:表示擴容前的table陣列的長度         int oldCap = (oldTab == null) ? 0 : oldTab.length;         //獲得舊雜湊表的擴容閾值         int oldThr = threshold;         //newCap:擴容之後table陣列大小         //newThr:擴容之後下次觸發擴容的條件         int newCap, newThr = 0;         //條件成立說明hashMap中的散列表已經初始化過了,是一次正常擴容         if (oldCap > 0) {             //判斷舊的容量是否大於等於最大容量,如果是,則無法擴容,並且設定擴容條件為int最大值,             //這種情況屬於非常少數的情況             if (oldCap >= MAXIMUM_CAPACITY) {                 threshold = Integer.MAX_VALUE;                 return oldTab;             }//設定newCap新容量為oldCap舊容量的二倍(<<1),並且<最大容量,而且>=16,則新閾值等於舊閾值的兩倍             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                      oldCap >= DEFAULT_INITIAL_CAPACITY)                 newThr = oldThr << 1; // double threshold         }         //如果oldCap=0並且邊界值大於0,說明散列表是null,但此時oldThr>0         //說明此時hashMap的建立是通過指定的構造方法建立的,新容量直接等於閾值         //1.new HashMap(intitCap,loadFactor)         //2.new HashMap(initCap)         //3.new HashMap(map)         else if (oldThr > 0) // initial capacity was placed in threshold             newCap = oldThr;         //這種情況下oldThr=0;oldCap=0,說明沒經過初始化,建立hashMap         //的時候是通過new HashMap()的方式建立的         else {               // zero initial threshold signifies using defaults             newCap = DEFAULT_INITIAL_CAPACITY;             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);         }         //newThr為0時,通過newCap和loadFactor計算出一個newThr         if (newThr == 0) {             //容量*0.75             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指向新建立的陣列         table = newTab;         //本次擴容之前table不為null         if (oldTab != null) {             //對陣列中的元素進行遍歷             for (int j = 0; j < oldCap; ++j) {                 //設定e為當前node節點                 Node e;                 //當前桶位資料不為空,但不能知道里面是單個元素,還是連結串列或紅黑樹,                 //e = oldTab[j],先用e記錄下當前元素                 if ((e = oldTab[j]) != null) {                     //將老陣列j桶位置為空,方便回收                     oldTab[j] = null;                     //如果e節點不存在下一個節點,說明e是單個元素,則直接放置在新陣列的桶位                     if (e.next == null)                         newTab[e.hash & (newCap - 1)] = e;                     //如果e是樹節點,證明該節點處於紅黑樹中                     else if (e instanceof TreeNode)                         ((TreeNode)e).split(this, newTab, j, oldCap);                     //e為連結串列節點,則對連結串列進行遍歷                     else { // preserve order                         //低位連結串列:存放在擴容之後的陣列的下標位置,與當前陣列下標位置一致                         //loHead:低位連結串列頭節點                         //loTail低位連結串列尾節點                         Node loHead = null, loTail = null;                         //高位連結串列,存放擴容之後的陣列的下標位置,=原索引+擴容之前陣列容量                         //hiHead:高位連結串列頭節點                         //hiTail:高位連結串列尾節點                         Node hiHead = null, hiTail = null;                         Node next;                         do {                             next = e.next;                             //oldCap為16:10000,與e.hsah做&運算可以得到高位為1還是0                             //高位為0,放在低位連結串列                             if ((e.hash & oldCap) == 0) {                                 if (loTail == null)                                     //loHead指向e                                     loHead = e;                                 else                                     loTail.next = e;                                 loTail = e;                             }                             //高位為1,放在高位連結串列                             else {                                 if (hiTail == null)                                     hiHead = e;                                 else                                     hiTail.next = e;                                 hiTail = e;                             }                         } while ((e = next) != null);                         //低位連結串列已成,將頭節點loHead指向在原位                         if (loTail != null) {                             loTail.next = null;                             newTab[j] = loHead;                         }                         //高位連結串列已成,將頭節點指向新索引                         if (hiTail != null) {                             hiTail.next = null;                             newTab[j + oldCap] = hiHead;                         }                     }                 }             }         }         return newTab;     }

```

擴容之後原位置的節點只有兩種調整

  • 保持原位置不動(新bit位為0時)

  • 雜湊原索引+擴容大小的位置去(新bit位為1時)

擴容之後元素的雜湊設定的非常巧妙,節省了計算hash值的時間,我們來看一 下具體的實現

圖片

當陣列長度從16到32,其實只是多了一個bit位的運算,我們只需要在意那個多出來的bit為是0還是1,是0的話索引不變,是1的話索引變為當前索引值+擴容的長度,比如5變成5+16=21

圖片

這樣的擴容方式不僅節省了重新計算hash的時間,而且保證了當前桶中的元素總數一定小於等於原來桶中的元素數量,避免了更嚴重的hash衝突,均勻的把之前衝突的節點分散到新的桶中去

11. 一般用什麼作為HashMap的key?

一般用Integer、String這種不可變類當HashMap當key

  • 因為String是不可變的,當建立字串時,它的hashcode被快取下來,不需要再次計算,相對於其他物件更快

  • 因為獲取物件的時候要用到equals()和hashCode()方法,那麼鍵物件正確的重寫這兩個方法是非常重要的,這些類很規範的重寫了hashCode()以及equals()方法

12. 為什麼Map桶中節點個數超過8才轉為紅黑樹?

8作為閾值作為HashMap的成員變數,在原始碼的註釋中並沒有說明閾值為什麼是8

在HashMap中有這樣一段註釋說明,我們繼續看

```  * Because TreeNodes are about twice the size of regular nodes, we  * use them only when bins contain enough nodes to warrant use  * (see TREEIFY_THRESHOLD). And when they become too small (due to  * removal or resizing) they are converted back to plain bins.  In  * usages with well-distributed user hashCodes, tree bins are  * rarely used.  Ideally, under random hashCodes, the frequency of  * nodes in bins follows a Poisson distribution  * (http://en.wikipedia.org/wiki/Poisson_distribution) with a  * parameter of about 0.5 on average for the default resizing  * threshold of 0.75, although with a large variance because of  * resizing granularity. Ignoring variance, the expected  * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /  * factorial(k)).

```

翻譯

``` 因為樹節點的大小大約是普通節點的兩倍,所以我們只在箱子包含足夠的節點時才使用樹節點(參見TREEIFY_THRESHOLD)。 當他們邊的太小(由於刪除或調整大小)時,就會被轉換回普通的桶,在使用分佈良好的hashcode時,很少使用樹箱。 理想情況下,在隨機雜湊碼下,箱子中節點的頻率服從泊松分佈 第一個值是:

* 0:    0.60653066  * 1:    0.30326533  * 2:    0.07581633  * 3:    0.01263606  * 4:    0.00157952  * 5:    0.00015795  * 6:    0.00001316  * 7:    0.00000094  * 8:    0.00000006  * more: less than 1 in ten million

```

樹節點佔用空間是普通Node的兩倍,如果連結串列節點不夠多卻轉換成紅黑樹,無疑會耗費大量的空間資源,並且在隨機hash演算法下的所有bin節點分佈頻率遵從泊松分佈,連結串列長度達到8的概率只有0.00000006,幾乎是不可能事件,所以8的計算是經過重重科學考量的

  • 從平均查詢長度來看,紅黑樹的平均查詢長度是logn,如果長度為8,則logn=3,而連結串列的平均查詢長度為n/4,長度為8時,n/2=4,所以閾值8能大大提高搜尋速度

  • 當長度為6時紅黑樹退化為連結串列是因為logn=log6約等於2.6,而n/2=6/2=3,兩者相差不大,而紅黑樹節點佔用更多的記憶體空間,所以此時轉換最為友好

13. HashMap為什麼執行緒不安全?

  • 多執行緒下擴容死迴圈。JDK1.7中的HashMap使用頭插法插入元素,在多執行緒的環境下,擴容的時候有可能導致環形連結串列的出現,形成死迴圈。因此JDK1.8使用尾插法插入元素,在擴容時會保持連結串列元素原本的順序,不會出現環形連結串列的問題

  • 多執行緒的put可能導致元素的丟失。多執行緒同時執行put操作,如果計算出來的索引位置是相同的,那會造成前一個key被後一個key覆蓋,從而導致元素的丟失。此問題在JDK1.7和JDK1.8中都存在

  • put和get併發時,可能導致get為null。執行緒1執行put時,因為元素個數超出threshold而導致rehash,執行緒2此時執行get,有可能導致這個問題,此問題在JDK1.7和JDK1.8中都存在

14. 計算hash值時為什麼要讓低16bit和高16bit進行異或處理

  • 我們計算索引需要將hashCode值與length-1進行按位與運算,如果陣列長度很小,比如16,這樣的值和hashCode做異或實際上只有hashCode值的後4位在進行運算,hash值是一個隨機值,而如果產生的hashCode值高位變化很大,而低位變化很小,那麼有很大概率造成雜湊衝突,所以我們為了使元素更好的雜湊,將hash值的高位也利用起來\

舉個例子

如果我們不對hashCode進行按位異或,直接將hash和length-1進行按位與運算就有可能出現以下的情況

圖片

如果下一次生成的hashCode值高位起伏很大,而低位幾乎沒有變化時,高位無法參與運算

圖片

可以看到,兩次計算出的hash相等,產生了hash衝突

所以無符號右移16位的目的是使高混亂度地區與地混亂度地區做一箇中和,提高低位的隨機性,減少雜湊衝突

文章中出現的關於面試題的錯誤請在評論區指出,我再進行改正優化。如果文章對你有所幫助,請給團長一個免費的贊吧,感謝大家。

圖片

關注公眾號:IT老哥,每天閱讀一篇乾貨文章,一年後你會發現一個不一樣的自己。