java中HashMap當插入位置不為空的時候JDK是怎么處理

Java中HashMap當插入位置不為空的時候JDK是怎么處理

在Java中，HashMap是一種非常常用的數據結構，它基于哈希表實現，允許存儲鍵值對，并且提供了快速的查找、插入和刪除操作。HashMap的核心思想是通過哈希函數將鍵映射到數組的某個位置，然后在該位置存儲對應的值。然而，由于哈希函數的性質，不同的鍵可能會被映射到同一個位置，這種情況稱為哈希沖突。本文將詳細探討在Java中，當插入位置不為空時，JDK是如何處理這種情況的。

1. HashMap的基本結構

在深入討論如何處理插入位置不為空的情況之前，我們首先需要了解HashMap的基本結構。

HashMap內部維護了一個數組，數組的每個元素是一個Node對象（在JDK 8之前是Entry對象），Node對象包含了鍵、值以及指向下一個Node的指針（用于處理哈希沖突）。這個數組通常被稱為桶數組（bucket array），數組的每個位置被稱為桶（bucket）。

transient Node<K,V>[] table;

Node類的定義如下：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    // 其他方法省略
}

2. 插入操作的基本流程

當我們向HashMap中插入一個鍵值對時，HashMap會執行以下步驟：

1. 計算哈希值：首先，HashMap會通過鍵的hashCode()方法計算出一個哈希值。
2. 確定桶的位置：通過哈希值與數組長度取模運算，確定鍵值對應該存儲在數組的哪個位置。
3. 插入鍵值對：如果該位置為空，則直接插入；如果該位置不為空，則需要處理哈希沖突。

3. 處理插入位置不為空的情況

當插入位置不為空時，意味著該位置已經存在一個或多個Node對象。此時，HashMap需要處理哈希沖突。JDK 8之前和JDK 8及之后的版本在處理哈希沖突時有所不同。

3.1 JDK 8之前的處理方式

在JDK 8之前，HashMap采用鏈表法來處理哈希沖突。具體步驟如下：

1. 遍歷鏈表：從該位置的第一個Node開始，遍歷鏈表，檢查是否有Node的鍵與待插入的鍵相同。
2. 更新值：如果找到相同的鍵，則更新該Node的值。
3. 插入新節點：如果沒有找到相同的鍵，則在鏈表的末尾插入一個新的Node。

for (Entry<K,V> 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;
        return oldValue;
    }
}

3.2 JDK 8及之后的處理方式

在JDK 8及之后的版本中，HashMap在處理哈希沖突時引入了紅黑樹的概念。當鏈表長度超過一定閾值（默認為8）時，鏈表會轉換為紅黑樹，以提高查找效率。具體步驟如下：

1. 遍歷鏈表或紅黑樹：從該位置的第一個Node開始，遍歷鏈表或紅黑樹，檢查是否有Node的鍵與待插入的鍵相同。
2. 更新值：如果找到相同的鍵，則更新該Node的值。
3. 插入新節點：如果沒有找到相同的鍵，則在鏈表或紅黑樹中插入一個新的Node。
4. 鏈表轉紅黑樹：如果鏈表長度超過閾值（默認為8），則將鏈表轉換為紅黑樹。

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

3.3 紅黑樹的優勢

紅黑樹是一種自平衡的二叉查找樹，它的查找、插入和刪除操作的時間復雜度為O(log n)。相比于鏈表，紅黑樹在處理大量數據時具有更高的效率。因此，當鏈表長度超過一定閾值時，HashMap會將鏈表轉換為紅黑樹，以提高性能。

4. 總結

在Java中，HashMap通過哈希表實現快速的鍵值對存儲和查找。當插入位置不為空時，HashMap會根據JDK版本的不同，采用鏈表法或紅黑樹法來處理哈希沖突。JDK 8之前的版本使用鏈表法，而JDK 8及之后的版本在鏈表長度超過閾值時，會將鏈表轉換為紅黑樹，以提高查找效率。

通過這種方式，HashMap能夠在大多數情況下保持較高的性能，即使在哈希沖突較多的情況下，也能通過紅黑樹來保證操作的效率。