深入理解Java HashMap實現原理

一、HashMap簡介

HashMap是Java集合框架的一部分，它提供了一種存儲鍵值對的方式。它是一種基於哈希表的實現，可以提供快速的插入、查找和刪除操作。

所有的集合類都實現了Map接口，而HashMap就是Map接口的一個基本實現。在HashMap中，每個鍵對應一個值。

二、HashMap數據結構

HashMap由數組和鏈表結構組成。具體來說，它由Entry對象數組和LinkedList對象組成。

Entry是HashMap的一個內部類，它存儲了鍵值對。每個Entry對象包含了一個鍵對象和一個值對象。LinkedList則是Java提供的標準鏈表實現，它用於解決哈希衝突的問題。

    static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;
        int hash;
    }

三、哈希衝突解決方法

當哈希表中出現相同的哈希值時，需要解決衝突。HashMap使用鏈表法解決哈希衝突的問題。

當多個Entry對象的哈希值相等時，它們會被組織成一個鏈表結構，鏈表中的每個元素都包含引用到下一個元素的指針。這樣，當發生哈希衝突時，新的Entry對象可以插入到鏈表中，而不會覆蓋原來的Entry對象。

四、HashMap擴容機制

HashMap的擴容機制是在數組大小超過了負載因子*當前數組大小時觸發。負載因子默認為0.75，也就是說當數組中的元素達到了數組大小的0.75倍時，就觸發擴容。

擴容的過程中，會新創建一個Entry對象數組，並將原數組中的所有元素重新分佈到新數組中。這個過程的時間複雜度是O(N)，需要遍歷原數組中的所有元素。因此，較大的初始容量和較小的負載因子可以減少擴容的次數，提高HashMap的效率。

    final Entry[] resize() {
        ...
        Entry[] newTab = new Entry[newCap];
        ...
        // Re-hash the contents of the old table into the new table
        for (int j = 0; j < oldCap; ++j) {
            Entry e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else {
                    // 重新分配每個Entry對象的next指向
                    Entry loHead = null, loTail = null;
                    Entry hiHead = null, hiTail = null;
                    Entry next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    ...
                }
            }
        }
        return newTab;
    }

五、HashMap實現原理總結

HashMap通過兩個基本的數據結構——數組和鏈表來實現快速存儲、查找和刪除操作。在存儲鍵值對時，HashMap會根據鍵對象的hashCode值將其映射到數組中的一個位置。當出現哈希衝突時，多個Entry對象會組織為一個鏈表以便於存儲和查找。在擴容時，HashMap會重新分配原有Entry對象到新的數組中，同時重新分佈每個Entry對象的next指向。

哈希表的查找速度非常快，但是它會浪費一定的空間。因為哈希表的大小是預先分配的，因此如果哈希表中的元素比較少時也需要佔用一定的空間。調整哈希表的大小可以解決這個問題。