深入理解Java中HashMap的put方法

1、介紹

HashMap是Java中最常用的數據結構之一，它能以常數時間複雜度（平均情況）完成插入和查找操作。HashMap的實現基於哈希表，而其put方法便是向哈希表中添加元素的方法。本文將深入探討Java中HashMap的put方法，以及它底層的實現原理。

2、正文

一、put方法概述

put方法是HashMap中最基礎也是最常用的方法之一，它用於在HashMap中插入一個鍵值對。其函數簽名為：

public V put(K key, V value)

該方法的作用是，根據鍵值對中的鍵計算出哈希值，將鍵值對插入到相應的哈希表中。在插入之前，會判斷哈希表中是否有相同鍵的元素。如果有，則用新值替換舊值。否則，將新鍵值對添加到哈希表中，並返回空。

二、HashMap哈希表

HashMap的底層實現是哈希表。哈希表是一種通過哈希函數將鍵映射到某個位置進行查找的數據結構。哈希表的插入、查找、刪除均可以在常數時間內完成，具有相當高的性能。

HashMap中的哈希表由一些桶（table）組成，每個桶中存儲著一個鏈表。桶的個數可以通過構造函數或者resize方法指定。在 put 方法中，首先計算出鍵對應的哈希值，再根據哈希值計算出桶的下標，最後將鍵值對插入到相應的鏈表中。

// 核心代碼1. 計算哈希值
int hash = hash(key.hashCode());
// 核心代碼2. 計算桶的下標
int i = indexFor(hash, table.length);

// 將鍵值對插入到相應的鏈表中
for (Entry e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        // 如果在鏈表中找到相同鍵，則用新值替換舊值
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
    }
}
// 沒找到相同鍵，則新建節點，並插入到鏈表中
modCount++;
addEntry(hash, key, value, i);
return null;

三、哈希衝突

雖然哈希表具有很高的性能，但是當哈希函數計算出來的哈希值相同時，便會出現哈希衝突的情況。為了解決這個問題，Java中的HashMap使用了鏈表來存儲哈希值相同的元素。當插入新元素時，會先在鏈表中查找是否已經有相同鍵的元素。如果有，就用新值替換舊值。如果沒有，就將新鍵值對插入到鏈表的頭部。這樣，在查找元素時就可以通過遍歷鏈表來找到相應的元素。

然而當鏈表長度過長時，查詢性能會大大降低。當鏈表長度超過閾值（默認值為8），哈希表會將鏈錶轉換成紅黑樹，從而提高查詢性能。

四、性能和擴容

為了使哈希表能夠保持高效的查詢性能，需要在哈希表中保留一定的空間。當哈希表中元素的數量達到了負載因子（默認值為0.75）* 桶的數量時，哈希表會自動擴容到原來的兩倍大小。同時，所有舊的元素必須重新計算哈希值，並放入新的桶中。

因此，在設計HashMap時需要考慮負載因子和初始容量。如果負載因子設置過高，會導致哈希衝突較多，從而影響性能。如果初始容量設置太小，在插入大量元素時會頻繁地進行擴容，從而效率較低。

3、小結

HashMap是Java中常用的數據結構之一，尤其適用於需要高效插入、查詢、刪除的場景。HashMap的實現基於哈希表，而put方法則是實現哈希表插入元素的關鍵。在插入元素時需要計算哈希值、確定桶的下標、判斷是否存在相同鍵的元素、處理哈希衝突等多個過程。通過了解HashMap的底層實現原理，可以更好地理解其性能和使用方式。