HashMap：密室、魔法與碰撞

讓我們將 HashMap 想像成一座有秘密房間（桶）的城堡，每個房間前面都有魔法門 - 哈希函數。這個神奇的機制是如何運作的？當兩個神奇的實體在同一個地方碰撞時會發生什麼？讓我們深入了解 HashMap 的秘密世界。首先我們來看看HashMap是由什麼組成。

HashMap 的基本組成部分

table數組：此數組是主要的資料儲存。每個數組單元（或儲存桶）都包含一個唯一的索引，其中可以儲存值鏈，甚至在元素數量較多的情況下儲存二元樹。

LoadFactor：LoadFactor指定HashMap在擴充之前可以填多少。預設負載因子為0.75，在節省記憶體和存取速度之間取得平衡。當 HashMap 已滿 75% 時，它會將表的大小加倍並重新分配元素以保持效率。

閾值：閾值是HashMap決定擴表的點。計算公式為（容量 * 負載係數）。例如，如果容量為 16，loadFactor 為 0.75，則閾值將為 12。當 HashMap 達到 12 個元素時，它會增加其大小。

大小追蹤 HashMap 中目前鍵值對的數量。

HashMap 中的每個鍵值對都儲存在稱為 Node 的結構中，其中包含：

金鑰 - 金鑰對的金鑰，
value—該對的值，
hash - 基於 hashCode() 鍵計算的雜湊值，
next - 發生衝突時指向鏈中下一個元素的連結。

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;
    }

    ....
}

每個節點在發生碰撞時都會連接到同一個儲存桶中的下一個節點，從而建立一個鍊錶。如果儲存桶中累積了超過 8 個元素，這些清單會自動變成平衡二元樹。

雜湊函數：鑰匙如何找到它們的房間

想像一下，HashMap 是一座有許多房間的巨大城堡。每個房間都有一個唯一的號碼，但是鑰匙要如何決定要去哪個房間呢？這就是雜湊函數的任務，雜湊函數是一個神奇的工具，可以幫助確定特定密鑰將被放置在哪個桶（房間）中。

當我們新增一個鍵時，putVal 方法會呼叫該鍵的 hashCode() 方法來建立一個雜湊值，然後將其細化為均勻分佈在各個儲存桶中。
索引計算：HashMap使用公式 int index = hashCode & (length- 1) 計算表數組中指向bucket的索引。

這裡的hashCode是key透過雜湊函數接收到的唯一程式碼。然後我們對 length - 1 進行位元與運算。這相當於計算雜湊碼除以桶數的餘數，從而確定桶數組中的索引。

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

因此，每個鍵都經過雜湊函數並最終到達自己唯一的房間，其索引是使用按位 AND 計算的。

碰撞檢查：如果桶子為空，則新增新的鍵值對。如果不匹配，putVal 檢查鍵是否匹配：

符合 * — 值已更新。
*不匹配 - 發生衝突 - 進一步了解它們。

碰撞：相互開放的秘密房間

如果兩把鑰匙最終位於同一個房間（多把鑰匙通往一個桶子）會發生什麼事？在 HashMap 中，這稱為衝突。這是當兩個鍵具有相同的雜湊碼並試圖進入同一個儲存桶時。這什麼時候可以實現？例如，我們錯誤地覆蓋了哈希碼。

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;
    }

    ....
}

在此範例中，KeyWithSameHash 類別有一個重寫的 hashCode() 方法，該方法為所有實例傳回相同的值，導致所有鍵最終位於表數組的同一單元格中：

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

對於所有鍵，hashCode() 值為 42，因此每次新增鍵時，表中的儲存桶索引都會相同。

但是鑰匙並沒有撞到頭，而是打開了額外的門，將房間變成了通往新房間的神奇走廊。這些新房間本質上是解決碰撞的方法。

鍊錶：當具有相同雜湊碼的兩個鍵最終位於同一個儲存桶中時，HashMap 會在該儲存桶中建立一個鍊錶。鍵繼續儲存在此清單中，如有必要，會使用 equals() 方法進行檢查以確保鍵確實相同。

紅黑樹：當一個桶子裡的碰撞次數變得太高（走廊變得太長）時，HashMap將其轉換為紅黑樹。這有助於加快搜尋速度並防止重負載下速度變慢。

equals() 和 hashCode() 如何運作

為了使 HashMap 魔法正常工作，具有相同值的兩個相同鍵返回相同的雜湊碼，並且使用 equals() 方法進行正確比較非常重要。這就像一個咒語，可以檢查兩個物件是否相同，即使它們可能以不同的方式表示。

hashCode()：每個物件必須有自己唯一的雜湊碼。這使得HashMap能夠有效率地找到需要放置key的bucket。
equals()：如果兩個物件具有相同的雜湊碼，則 equals() 方法檢查物件是否實際上相同。
如果不存在此檢查，HashMap 可能會混淆兩個不同的鍵，從而導致不正確的程式行為。

結論

HashMap 的世界是一個神奇的世界，散列函數和碰撞幫助鑰匙找到它們的房間並保持城堡的秩序。由於雜湊函數，每個鍵都有自己的通往唯一索引的路徑。當兩個鑰匙在同一個桶中碰撞時，魔法會繼續發揮作用，以鍊錶或紅黑樹的形式打開新的門來找到正確的路徑。

因此，由於hashCode()、equals() 和神奇的碰撞走廊，HashMap 仍然是Java 開發人員武器庫中最強大的工具之一，即使在最混亂的情況下也能保證效率和準確性。

以上是HashMap：密室、魔法與碰撞的詳細內容。更多資訊請關注PHP中文網其他相關文章！