Java中的HashMap

什么是HashMap？

HashMap是Java中常用的數(shù)據(jù)結(jié)構(gòu)之一，它基于哈希表實現(xiàn)，提供了快速的鍵值對存取能力。在HashMap中，put方法是最常用的方法之一，用于將鍵值對存儲到HashMap中。本文將深入探究HashMap的put方法的實現(xiàn)原理，解析其內(nèi)部數(shù)據(jù)結(jié)構(gòu)和算法，并探討設計put方法的意義。

對比其他Map中put()方法

可以看一下博主的博客了解HashMap、TreeMap和LinkedHashMap三者的使用：Java-數(shù)據(jù)結(jié)構(gòu)（二）-Map：HashMap、TreeMap、LinkedHashMap
HashMap、TreeMap和LinkedHashMap都是Java中常用的Map實現(xiàn)類，它們在put方法的實現(xiàn)上有一些區(qū)別。

1. HashMap的put方法：

   • HashMap使用哈希表來存儲鍵值對，通過鍵的哈希碼和哈希函數(shù)來確定鍵值對在哈希表中的存儲位置。
   • 當發(fā)生哈希沖突時，HashMap使用鏈表或紅黑樹來解決沖突。
   • HashMap的put方法具有O(1)的平均時間復雜度。

2. TreeMap的put方法：

   • TreeMap使用紅黑樹來存儲鍵值對，根據(jù)鍵的自然順序或自定義比較器來進行排序。
   • 在插入鍵值對時，TreeMap會根據(jù)鍵的順序?qū)㈡I值對插入到相應的位置，以保持有序性。
   • TreeMap的put方法具有O(log n)的時間復雜度。

3. LinkedHashMap的put方法：

   • LinkedHashMap繼承自HashMap，底層仍然使用哈希表來存儲鍵值對。
   • LinkedHashMap在HashMap的基礎(chǔ)上，使用雙向鏈表來維護鍵值對的插入順序或訪問順序。
   • 在插入鍵值對時，LinkedHashMap會將鍵值對插入到鏈表的尾部，以保持插入順序或訪問順序。
   • LinkedHashMap的put方法具有O(1)的平均時間復雜度。

• HashMap的put方法使用哈希表來存儲鍵值對，適用于需要高效存儲和查找鍵值對的場景。
• TreeMap的put方法使用紅黑樹來存儲鍵值對，適用于需要有序存儲和查找鍵值對的場景。
• LinkedHashMap的put方法在HashMap的基礎(chǔ)上，使用雙向鏈表來維護插入順序或訪問順序，適用于需要保持插入順序或訪問順序的場景。

HashMap中put()方法使用示例

以下是一個簡單的Java代碼示例，展示了如何使用HashMap的put方法：

import java.util.HashMap;public class HashMapExample {public static void main(String[] args) {// 創(chuàng)建一個HashMap對象HashMap<String, Integer> hashMap = new HashMap<>();// 使用put方法添加鍵值對hashMap.put("apple", 1);hashMap.put("banana", 2);hashMap.put("cherry", 3);// 使用get方法獲取鍵對應的值int value = hashMap.get("banana");System.out.println("The value of 'banana' is: " + value);}
}

HashMap中put()源碼解析

手繪流程圖

實現(xiàn)原理

在Java中，HashMap的put方法的實現(xiàn)原理可以分為以下幾個步驟：

1.首先，根據(jù)鍵的哈希值計算出鍵的哈希碼。HashMap使用鍵的哈希碼來確定鍵值對在哈希表中的存儲位置。

2.接下來，通過哈希碼計算出鍵值對在哈希表中的索引位置。HashMap使用一個稱為“哈希函數(shù)”的算法來計算索引位置。常用的哈希函數(shù)是將哈希碼與哈希表的容量進行取模運算，得到索引位置。

3.如果該索引位置上沒有其他鍵值對，則直接將鍵值對存儲在該位置上。如果該索引位置上已經(jīng)存在其他鍵值對，則發(fā)生了“哈希沖突”。

4.當發(fā)生哈希沖突時，HashMap使用鏈表或紅黑樹來解決沖突。在JDK1.8之前，HashMap使用鏈表來解決沖突，即在沖突的索引位置上，將新的鍵值對插入到鏈表的尾部。而在JDK1.8及以后的版本中，當鏈表長度超過一定閾值時，HashMap會將鏈表轉(zhuǎn)換為紅黑樹，以提高查找效率。

5.最后，將鍵值對成功存儲在哈希表中，并返回先前關(guān)聯(lián)的值（如果存在）。如果該索引位置上已經(jīng)存在其他鍵值對，則需要遍歷鏈表或紅黑樹，找到對應的鍵值對，并更新其值。

通過以上步驟，HashMap的put方法成功將鍵值對存儲在哈希表中。需要注意的是，當哈希表的負載因子（即存儲的鍵值對數(shù)量與容量的比值）超過一定閾值時，HashMap會進行擴容操作，以保持哈希表的性能。

源碼探究（JDK 1.8）

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// table未初始化或者長度為0，進行擴容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// (n - 1) & hash 確定元素存放在哪個桶中，桶為空，新生成結(jié)點放入桶中(此時，這個結(jié)點是放在數(shù)組中)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 桶中已經(jīng)存在元素（處理hash沖突）else {Node<K,V> e; K k;//快速判斷第一個節(jié)點table[i]的key是否與插入的key一樣，若相同就直接使用插入的值p替換掉舊的值e。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 判斷插入的是否是紅黑樹節(jié)點else if (p instanceof TreeNode)// 放入樹中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 不是紅黑樹節(jié)點則說明為鏈表結(jié)點else {// 在鏈表最末插入結(jié)點for (int binCount = 0; ; ++binCount) {// 到達鏈表的尾部if ((e = p.next) == null) {// 在尾部插入新結(jié)點p.next = newNode(hash, key, value, null);// 結(jié)點數(shù)量達到閾值(默認為 8 )，執(zhí)行 treeifyBin 方法// 這個方法會根據(jù) HashMap 數(shù)組來決定是否轉(zhuǎn)換為紅黑樹。// 只有當數(shù)組長度大于或者等于 64 的情況下，才會執(zhí)行轉(zhuǎn)換紅黑樹操作，以減少搜索時間。否則，就是只是對數(shù)組擴容。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);// 跳出循環(huán)break;}// 判斷鏈表中結(jié)點的key值與插入的元素的key值是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等，跳出循環(huán)break;// 用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表p = e;}}// 表示在桶中找到key值、hash值與插入元素相等的結(jié)點if (e != null) {// 記錄e的valueV oldValue = e.value;// onlyIfAbsent為false或者舊值為nullif (!onlyIfAbsent || oldValue == null)//用新值替換舊值e.value = value;// 訪問后回調(diào)afterNodeAccess(e);// 返回舊值return oldValue;}}// 結(jié)構(gòu)性修改++modCount;// 實際大小大于閾值則擴容if (++size > threshold)resize();// 插入后回調(diào)afterNodeInsertion(evict);return null;
}

設計put()的意義

設計put方法的意義在于提供了一種簡單而高效的方式來存儲和查找鍵值對。HashMap的put方法具有O(1)的平均時間復雜度，即使在發(fā)生哈希沖突的情況下，通過鏈表或紅黑樹的處理，也能保持較快的查找性能。這使得HashMap成為了處理大量數(shù)據(jù)的理想選擇，尤其在需要頻繁進行鍵值對操作的場景下。

總結(jié)

本文深入探究了Java中HashMap的put方法的實現(xiàn)原理。通過了解其內(nèi)部數(shù)據(jù)結(jié)構(gòu)和算法，我們可以更好地理解和使用HashMap，在實際開發(fā)中更加高效地進行鍵值對的存儲和查找操作。同時，我們也探討了設計put方法的意義，以及提供了相關(guān)的Java代碼示例。希望本文對讀者有所幫助，讓大家對HashMap的put方法有更深入的理解。