Java中的HashMap

什么是HashMap？

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

對(duì)比其他Map中put()方法

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

1. HashMap的put方法：

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

2. TreeMap的put方法：

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

3. LinkedHashMap的put方法：

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

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

HashMap中put()方法使用示例

以下是一個(gè)簡(jiǎn)單的Java代碼示例，展示了如何使用HashMap的put方法：

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

HashMap中put()源碼解析

手繪流程圖

實(shí)現(xiàn)原理

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

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

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

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

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

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

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

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

設(shè)計(jì)put()的意義

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

總結(jié)

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