Java-100天知識進階-HashMap如何在Java中工作-知識鋪

知識鋪：致力於打造輕知識點，持續更新每次的知識點較少，閱讀不累。不佔太多時間，不停地來喚醒你記憶深處的知識點。

一、認識HashMap

Java中的HashMap雜湊儲存。

1。1 是一種資料結構，它允許我們儲存物件並在我們知道key的情況下在恆定時間O（1）中檢索它。

1。2 在雜湊中，雜湊函式用於連結HashMap中的鍵和值。透過呼叫HashMap的put（key，value）方法儲存物件，並透過呼叫get（key）方法檢索物件。當我們呼叫put方法時，呼叫key物件的hashcode（）方法，以便map的hash函式可以找到儲存value物件的位置，這實際上是內部陣列的索引，稱為索引表。

1。3 HashMap在內部以Map。Entry物件的形式儲存對映，該物件包含鍵和值物件。如果要檢索物件，請呼叫get（）方法並再次傳遞key物件。這一次，key物件生成相同的hashCode。這裡需要注意的是，如果key是自定義變數，需要實現hashCode 和equalsequals方法。一般使用的是String作為可以，這是由於String實現了自己的hashCode 和方法，只有這樣保證計算出來的索引最終會在同一個桶位置。

1。4 HashMap的內部陣列是固定大小的，並且如果你繼續儲存物件，在某些時候hash函式將為兩個不同的鍵返回相同的索引位置，這在HashMap中稱為碰撞。在這種情況下，在該桶位置處形成連結串列，並且將新Entry儲存為下一節點。

1。5 從此連結串列中檢索物件，我們需要額外檢查以搜尋正確的值，這是透過equals（）方法完成的。由於每個節點都包含一個Entry，HashMap使用equals（）保持比較Entry的key物件和傳遞的key，當它返回true時，Map返回相應的值。

1。6 搜尋內聯列表是O（n）操作，因此在最壞的情況下，雜湊衝突將對映減少到連結串列。最近在Java 8中透過將連結串列替換為樹以在O（logN）時間內搜尋來解決此問題。

二、Hashtable和HashMap之間的區別

2。1 HashMap 特點

HashMap 允許 null作為key ，執行緒不安全，查詢key時間複雜度 O（1）

2。2 HashMap 的 put 具體操作

HashMap實現呼叫hashCode方法在Key物件上，將返回的hashcode應用到自己的雜湊函式中，找到用於儲存Entry物件的儲存桶位置，檢測hashCode碰撞，然後繼續在該桶的位置維護一個連結串列，將該value對應的Entry物件進行儲存下一個節點上。

2。3 HashMap 的 hashCode碰撞

不同的key進行hashcode計算後，然後進行索引定位的時候，容易發生碰撞。這是由於我們的hashMap中的桶個數是一定的，計算的code值進行長度取模的時候，落到同一個索引桶中。

如圖：get方法如何在Java中的HashMap中工作

a。先計算出 key 的hashcode對應的索引桶位置

b。索引桶找到後，在遍歷連結串列，進行key，value比較

2。4 為什麼String，Integer和其他包裝類被認為是好的鍵？

String ，Integer 和其他包裝類是HashMap 鍵的自然候選者，String 也是最常用的鍵，因為String是不可變的和final的，並且會覆蓋equals 和hashcode（）方法。其他包裝類也共享類似的屬性。不可變性是必需的，以防止用於計算hashCode（）的欄位發生變化，因為如果key物件在插入和檢索期間返回不同的hashCode，則無法從HashMap 獲取物件。不可變性是最好的。

2。5 可以在HashMap中使用任何自定義物件作為鍵

Java HashMap中使用任何Object 作為鍵，前提是它覆蓋equals和hashCode方法，並且一旦將物件插入Map，其hashCode就不應該變化。

2。6 使用ConcurrentHashMap代替Hashtable

Hashtable 是同步的，但是ConcurrentHashMap 只通過鎖定分級桶來提供更好的併發性。ConcurrentHashMap 肯定是作為Hashtable 引入的，可以代替它使用，但Hashtable 提供比ConcurrentHashMap更強的執行緒安全性。

三、總結HashMap

3。1 HashMap的工作原理是雜湊，我們有put（）和get（）方法來儲存和檢索來自HashMap的物件。當我們將key和value傳遞給put（）方法儲存在HashMap上時，它使用key物件hashcode（）透過對該雜湊值來計算索引位置。檢索它時使用key物件equals方法來找出與該key關聯的正確key值對和返回值物件。HashMap在發生衝突時使用連結串列，物件將儲存在連結串列的下一個節點中。此外，HashMap以Map。Entry物件的形式在鍵列表的每個節點中儲存鍵元組和值元組。

3。2 HashMap的hashcode碰撞，它們將儲存在同一個儲存桶中。

3。3 如何在HashMap中處理null鍵？由於equals（）和hashCode（）用於儲存和檢索值，因此在null鍵的情況下它是如何工作的？

null鍵是在HashMap中專門處理的，putForNullKey（V值）和getForNullKey（）有兩種不同的方法。空鍵始終對映到索引0。為了在兩個最常用的操作（get和put）中執行，這個空key被拆分為單獨的方法，但在其他操作中包含條件。簡而言之，在HashMap中使用null鍵時，不使用equals（）和hashcode（）方法。

如圖：