手寫HashMap

在Java中，HashMap是一種散列表，它存儲鍵值對，並可以通過鍵進行快速檢索。HashMap同樣也是我們日常開發中使用非常廣泛的數據結構之一，因此，了解HashMap的工作原理及手動實現HashMap是我們開發Java應用程序的必備技能之一。本文將會從多個方面對手寫HashMap進行詳細闡述，幫助讀者全面了解HashMap的運作原理及具體實現。

一、HashMap的概述

HashMap是一個散列表，它是Java Collection Framework中的一部分。HashMap以鍵值對(Key-Value Pairs)的形式存儲數據，Key可以通過hashCode()方法被哈希為一個整數，並被哈希表作為索引來保存數據的地址

HashMap的作用就是能夠在O(1)的時間複雜度內實現增刪改查。其中，增加操作put()，刪除操作remove()，獲取操作get()，都可以通過鍵直接進行訪問，極大的提高了我們的開發效率。

二、HashMap的實現原理

HashMap的實現原理主要基於哈希表，每個元素都以Key-Value的形式保存在一個桶(bucket)中。當進行查找操作時，首先根據Key哈希為一個整數，然後根據這個整數映射到桶中，從而找到Key所在的位置。

一、哈希函數

哈希函數是HashMap中的一個重要概念，哈希函數將傳入的Key轉換為一個哈希碼(hashCode)，通過哈希碼在底層數組中進行查找。哈希函數映射的哈希碼越分布越均勻，則衝突的概率也就越小，HashMap的效率也就越高。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

我們可以看到，hashCode()函數返回一個int類型的哈希碼，這個哈希碼由Java提供的一個特定的公式生成，該公式的目的是讓生成的哈希碼分布得越均勻越好。

二、哈希衝突的解決方法

當不同的Key通過哈希函數產生的哈希碼相同時，就會發生哈希衝突。哈希衝突時，需要使用鏈表或紅黑樹等數據結構來解決，這也是HashMap為什麼能夠在時間複雜度為O(1)內實現高效增刪改查的原因。

HashMap中鏈表的長度閾值為8，如果同一個桶內鏈表長度超過了8，則該鏈表會轉換為紅黑樹，以提高查找效率。如果刪除元素後，鏈表長度小於等於6，則將紅黑樹轉換為鏈表。

三、手寫HashMap的實現

為了直觀地展示HashMap的工作原理，我們接下來將手動實現一個簡單的HashMap。

一、初始化HashMap

我們首先定義一個簡單的HashMap類，它包含一個Node數組和一個長度變量size：

public class MyHashMap {
    private Node[] arr;
    private int size;
}

在構造函數中，我們需要對Node數組進行初始化，這裡我們設置數組大小為10：

public MyHashMap() {
    arr = new Node[10];
}

二、實現put方法

put方法是向HashMap中添加Key-Value對的方法。我們需要通過Key的哈希值來確定該元素在Node數組中的位置，並且，當哈希衝突時，需要使用鏈表將其保存。put方法的實現過程如下：

public void put(int key, int value) {
    int index = key % arr.length;

    if (arr[index] == null) {
        arr[index] = new Node(key, value);
        size++;
    } else {
        Node node = arr[index];

        while (node.next != null) {
            if (node.next.key == key) {
                node.next.value = value;
                return;
            }
            node = node.next;
        }

        if (node.key == key) {
            node.value = value;
        } else {
            node.next = new Node(key, value);
            size++;
        }
    }
}

可以看到，我們首先通過Key計算出其哈希值，然後用哈希值來確定該key在Node數組中的位置。如果該位置為空，則直接在該位置插入一個新的Node，如果該位置不為空，則需要遍歷鏈表來查找該Key，如果找到，則更新其Value值，否則，在該鏈表尾部添加一個新的Node節點。

三、實現get方法

get方法是獲取HashMap中指定Key對應的Value值的方法。與put方法類似，get方法也需要通過Key的哈希值來確定該元素在Node數組中的位置。get方法的實現過程如下：

public int get(int key) {
    int index = key % arr.length;
    Node node = arr[index];

    while (node != null) {
        if (node.key == key) {
            return node.value;
        }
        node = node.next;
    }

    return -1;
}

可以看到，我們通過Key計算出其哈希值，然後用哈希值來確定該key在Node數組中的位置。如果該位置為空，則該Key不存在於HashMap中，返回-1；否則，遍歷鏈表來查找該Key，如果找到，則返回對應的Value值。

四、HashMap的使用

手寫的MyHashMap雖然不如Java原生的HashMap強大，但是其原理和簡潔的代碼十分直觀，值得用於學習和理解HashMap的工作原理。下面我們來看一下如何使用Java原生的HashMap:

HashMap<String, String> map = new HashMap<>();
map.put("Key1", "Value1");
map.put("Key2", "Value2);

String value1 = map.get("Key1");
String value2 = map.get("Key2");

如上述代碼所示，我們可以輕鬆地使用Java原生的HashMap進行操作，並可以在一次代碼調用中實現快速地增刪改查。

總結

本文以手寫HashMap為中心，詳細介紹了HashMap的工作原理及具體實現。HashMap作為一個重要的數據結構，能夠在Java開發中發揮重要作用。如果不僅限於Java開發，類似HashMap的數據結構在其他領域同樣具有重要的意義。了解HashMap以及其他相關數據結構的工作原理及實現，將有助於我們更好地理解算法原理，提高開發效率。