HashMap在Java中是如何運作的

你們中的大多數人都會同意HashMap，今天是採訪中最喜歡討論的話題。有時我會與同事進行類似的討論，這確實很有幫助。下面我就和大家進行這樣的討論。 我假設如果您對 HashMap 的內部結構和工作原理感興趣，那麼您已經熟悉HashMap的基礎知識，因此我將跳過這一部分。但如果您對此不熟悉，我建議您訪問Java Docs網站。在我們繼續之前，我強烈建議您查看我的上一篇文章：在 Java 中使用 hashCode 和 equals 方法。 本文內容：

1. 唯一可能的答案。
2. 什麼是哈希。
3. 關於班級的一些情況Entry。
4. .是什麼意思put()？
5. 該方法如何運作get()。
6. 筆記

唯一可能的答案

如果有人讓我解釋一下“ HashMap 是如何運作的？” ”，我簡單回答：“根據Hashing的原理。” 簡單得不能再簡單了。要理解這一點並獲得擴展答案，您需要確保您了解哈希的基礎知識。正確的？

什麼是哈希

最簡單形式的雜湊是一種在將任何公式/演算法應用於其屬性後將任何變數/物件轉換為唯一程式碼的方法。真正的雜湊函數必須遵循以下規則：無論何時，雜湊函數應用於相同或相等的物件時都必須傳回相同的雜湊程式碼。換句話說，兩個相同的物件必須依序返回相同的哈希碼。 您可以在這裡閱讀更多相關資訊： Working with hashCode and equals method in Java

關於入門級的一些知識

根據定義，映射是「成對儲存值和鍵的物件」。很簡單，對吧？那麼，HashMap 中一定存在某種機制來儲存成對的 Values 和 Keys 嗎？答 - 是的。HashMap有一個內部類Entry，如下所示：

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

當然，該類別Entry有一個作為屬性儲存的鍵和值。鍵被標記為final，我們也看到兩個附加欄位：next和hash。隨著文章的進展，我們將嘗試理解這些欄位的用途。

Java put() 方法的作用是什麼？

在我們深入研究該方法的實作之前put()，了解類別的實例Entry儲存在陣列中非常重要。HashMap 類別將該變數定義為：

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

現在來看看該方法的實作程式碼put()：

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
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;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

讓我們一步一步來弄清楚：

• 首先，我們檢查密鑰是否存在。如果鍵不存在 ( null)，則該值將放置在表中的位置 0 處，因為該值的雜湊碼為null, это – всегда 0。


• 下一步，使用呼叫 方法取得的金鑰的雜湊碼來計算雜湊值hashCode()。此散列值用於計算物件在陣列中放置的位置Entry。JDK設計者假設寫得不好的函數hashCode()可能會傳回過高或過低的雜湊值。為了解決這個問題，他們引入了另一個hash()函數，將一個物件的雜湊值傳入其中，使雜湊值與陣列的大小相符。


• 現在呼叫該函數indexFor(hash, table.length)來計算放置物件的確切位置Entry。


• 這是主要部分開始的地方。現在，根據我們知道兩個不相等的物件可以具有相等的雜湊碼，我們提出一個問題：兩個不同的物件會被放置在 [bucket] 陣列中的相同位置嗎？答案是LinkedList。如果您還記得的話，該類別Entry有一個屬性“ next”。該屬性始終指向鏈中的下一個物件。這正是行為LinkedList。

因此，物件Entry以 形式儲存LinkedList。當一個物件Entry被放置在特定的位置時，HashMap 會檢查該位置是否已經有一個條目。如果沒有條目，則將物件放置在該位置。然而，如果該位置已經有一個對象，則檢查下一個屬性。如果它返回null並且當前物件Entry成為LinkedList. 如果下一個變數不存在null，則對下一個變數重複該過程，直到找到為止null。如果我們放置另一個具有不同值但具有與之前相同的鍵的物件會怎麼樣？從邏輯上講，這應該會導致舊值被替換。這是怎麼發生的？一般來說，確定一個物件的位置後Entry，在遍歷LinkedList到計算出的位置的同時，HashMap會呼叫每個物件的關鍵compare方法Entry。所有這些Entry物件LinkedList可能具有相似的雜湊碼，但該方法equals()將檢查真正的相似性。這只會替換Entry. 因此，HashMap保證了所有鍵的唯一性。

Java get() 方法如何運作？

現在我們已經了解了鍵值對是如何儲存在HashMap. 下一個大問題是：當物件從 HashMap 傳遞到方法時會發生什麼get()？一個物體的價值是如何決定的？我們應該已經知道答案了，因為方法中決定鍵唯一性的方式與put()方法應用的邏輯相同get()。一旦HashMap它確定了作為參數傳入的物件的鍵，它就會簡單地傳回對應的值Entry。如果沒有找到匹配項，則方法get()將傳回null。我們來看一下程式碼：

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

上面的程式碼與put()到目前為止的方法類似if (e.hash == hash && ((k = e.key) == key || key.equals(k)))，之後只是傳回物件的值。

筆記

• 要儲存在物件中的資料結構Entry是一個具有名稱table和類型的陣列Entry。
• 數組中的每個單獨位置稱為儲存桶，因為它可以包含LinkedList物件的第一個元素Entry。
• hashCode()需要密鑰來計算物件的位置Entry。
• equals()key用來檢查map( map)中key的唯一性。
• hashCode()和equals()Values 不用於方法get()和set()中HashMap。
• 具有值的鍵的雜湊碼null始終為0。並且這樣的物件Entry將始終儲存在數組的零位置。

我希望我在這篇文章中正確地表達了我的想法。如果您發現錯誤或有疑問，請在評論中留下。 快樂學習！