淺析 HashMap

4年前 (2019-12-03) Yosheng 程式設計 0評論 已收錄 904℃

筆記對原始碼解讀的理解以及面試經常問到的問題。

HashMap的資料結構

資料結構中有陣列和連結串列來實現對資料的儲存,但這兩者基本上是兩個極端。

陣列

陣列儲存區間是連續的,佔用記憶體嚴重,故空間複雜的很大。但陣列的二分查詢時間複雜度小,為O(1);陣列的特點是:定址容易,插入和刪除困難

連結串列

連結串列儲存區間離散,佔用記憶體比較寬鬆,故空間複雜度很小,但時間複雜度很大,達O(N)。連結串列的特點是:定址困難,插入和刪除容易

雜湊表

那麼能不能綜合兩者的特性,做出一種定址容易,插入刪除也容易的資料結構?答案是肯定的。雜湊表((Hash table)既滿足了資料的查詢方便,同時不佔用太多的內容空間,使用也十分方便。

雜湊表有多種不同的實現方法,接下來解釋的是最常用的一種方法—— 拉鍊法,可以理解為“連結串列的陣列” ,如圖:


從上圖可以理解為 Hashmap 中存放數據的Entry透過%運算得到最後放入陣列的格子中,比如hash為16%16得0則直接放到[0]中,不過這樣的計算效率太低,後面會接著說原始碼上針對這部分做了哪些改進,接著是每個Entry中都帶著next節點指向下個Entry形成單向連結串列。

原始碼分析

上述轉自: HashMap源码分析

探討 Hashmap 存取

既然是線性陣列,為什麼能隨機存取?這裡HashMap用了一個小演算法,大致是這樣實現:

put

疑問:如果兩個key通過hash%Entry[].length得到的index相同,會不會有覆蓋的危險?

這裡HashMap裡面用到鏈式資料結構的一個概念。上面我們提到過Entry類裡面有一個next屬性,作用是指向下一個Entry。打個比方, 第一個鍵值對A進來,通過計算其key的hash得到的index=0,記做:Entry[0] = A。一會後又進來一個鍵值對B,通過計算其index也等於0,現在怎麼辦?HashMap會這樣做:B.next = A,Entry[0] = B,如果又進來C,index也等於0,那麼C.next = B,Entry[0] = C;這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性連結在一起。所以疑問不用擔心。也就是說陣列中儲存的是最後插入的元素。到這裡為止,HashMap的大致實現,我們應該已經清楚了。

當然HashMap裡面也包含一些優化方面的實現,這裡也說一下。比如:Entry[]的長度一定後,隨著map裡面資料的越來越長,這樣同一個index的鏈就會很長,會不會影響效能?HashMap裡面設定一個因子,隨著map的size越來越大,Entry[]會以一定的規則加長長度。

get

null key的存取

null key總是存放在Entry[]陣列的第一個元素。

確定陣列index:hashcode % table.length取模

HashMap存取時,都需要計算當前key應該對應Entry[]陣列哪個元素,即計算陣列下標;演算法如下:

按位取並,作用上相當於取模mod或者取餘%。
這意味著陣列下標相同,並不表示hashCode相同。

table初始大小

注意 table初始大小并不是构造函数中的initialCapacity!!而是 >= initialCapacity的2的n次幂!!!!

解決hash衝突的辦法

  1. 開放定址法(線性探測再雜湊,二次探測再雜湊,偽隨機探測再雜湊)
  2. 再雜湊法
  3. 鏈地址法
  4. 建立一個公共溢位區

Java中hashmap的解決辦法就是採用的鏈地址法。

再散列rehash过程

當雜湊表的容量超過預設容量時,必須調整table的大小。當容量已經達到最大可能值時,那麼該方法就將容量調整到Integer.MAX_VALUE返回,這時,需要建立一張新表,將原表的對映到新表中。

常見問題

如果兩個鍵的hashcode相同,你如何獲取值物件?

當我們呼叫get()方法,HashMap會使用鍵物件的hashcode找到bucket位置,然後獲取值物件。找到bucket位置之後,會呼叫keys.equals()方法去找到連結串列中正確的節點,最終找到要找的值物件。

如果HashMap的大小超過了負載因子(load factor)定義的容量,怎麼辦?

hashMap預設的負載因子大小為0.75,也就是說,當一個map填滿了75%的bucket時候,和其它集合類(如ArrayList等)一樣,將會建立原來HashMap大小的兩倍的bucket陣列,來重新調整map的大小,並將原來的物件放入新的bucket陣列中。這個過程叫作rehashing,因為它呼叫hash方法找到新的bucket位置。

當重新調整HashMap大小的時候,確實存在條件競爭,因為如果兩個執行緒都發現HashMap需要重新調整大小了,它們會同時試著調整大小。在調整大小的過程中,儲存在連結串列中的元素的次序會反過來,因為移動到新的bucket位置的時候,HashMap並不會將元素放在連結串列的尾部,而是放在頭部,這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了,那麼就死迴圈了。

為什麼String, Interger這樣的wrapper類適合作為鍵?

String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了,而且String最為常用。因為String是不可變的,也是final的,而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的,因為為了要計算hashCode(),就要防止鍵值改變,如果鍵值在放入時和獲取時返回不同的hashcode的話,那麼就不能從HashMap中找到你想要的物件。不可變性還有其他的優點如執行緒安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的,那麼請這麼做吧。因為獲取物件的時候要用到equals()和hashCode()方法,那麼鍵物件正確的重寫這兩個方法是非常重要的。如果兩個不相等的物件返回不同的hashcode的話,那麼碰撞的機率就會小些,這樣就能提高HashMap的效能。

我們可以使用自定義的物件作為鍵嗎?

你可能使用任何物件作為鍵,只要它遵守了equals()和hashCode()方法的定義規則,並且當物件插入到Map中之後將不會再改變了。如果這個自定義物件時不可變的,那麼它已經滿足了作為鍵的條件,因為當它建立之後就已經不能改變了。

我們可以使用CocurrentHashMap來代替Hashtable嗎?

Hashtable是synchronized的,但是ConcurrentHashMap同步效能更好,因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable,但是HashTable提供更強的執行緒安全性。

為什麼需要使用Hashcode?

Java中的集合(Collection)有兩類,一類是List,再有一類是Set。前者集合內的元素是有序的,元素可以重複;後者元素無序,但元素不可重複。那麼這裡就有一個比較嚴重的問題了:要想保證元素不重複,可兩個元素是否重複應該依據什麼來判斷呢?這就是 Object.equals方法了。但是,如果每增加一個元素就檢查一次,那麼當元素很多時,後新增到集合中的元素比較的次數就非常多了。也就是說,如果集合中現在已經有1000個元素,那麼第1001個元素加入集合時,它就要呼叫1000次equals方法。這顯然會大大降低效率。

於是,Java採用了雜湊表的原理。雜湊演算法也稱為雜湊演算法,是將資料依特定演算法直接指定到一個地址上。可以這樣簡單理解,hashCode方法實際上返回的就是物件儲存位置的映像。

這樣一來,當集合要新增新的元素時,先呼叫這個元素的hashCode方法,就能定位到它應該放置的儲存位置。如果這個位置上沒有元素,它就可以直接儲存在這個位置上,不用再進行任何比較了;如果這個位置上已經有元素了,就呼叫它的equals方法與新元素進行比較,相同的話就不存了,不相同就表示發生衝突了,散列表對於衝突有具體的解決辦法,但最終還會將新元素儲存在適當的位置。這樣一來,實際呼叫equals方法的次數就大大降低了,幾乎只需要一兩次。

博主

擅長使用 C# 和 Java 開發項目,全棧開發工程師,前端主要使用 Vue 其次 Angular ,目前正在學習分布式架構,運維研發兼具,平時愛好鑽研技術並應用於實務當中,常駐於上海。

相關推薦

相逢就是有緣,留下足跡吧!