HashMap 是儲存和獲取資料的簡單而強大的方法。但是有多少開發人員知道HashMap在內部的工作原理？

內部儲存

JAVA HashMap類實現介面地圖。(K,V)。此介面的主要方法是：

• V 放 （K 鍵， V 值）
• V 獲取（物件金鑰）
• V 刪除（物件金鑰）
• 布林包含鑰匙（物件金鑰）

Hash資料使用內部類來儲存資料：入口+lt;K，V=。此條目是一個簡單的鍵值對，具有兩個額外的資料：

• 引用另一個條目，以便HashMap可以儲存條目，如單鏈接列表
• 表示金鑰的Hash值的Hash值。此hash值儲存以避免每次HashMap需要時計算雜湊值。

為了高效工作，內部陣列的大小需要為 2 的功率，讓我們看看原因。

想象一下陣列大小為 17，面罩值將是 16（大小 -1）。16的二進位制表示為0.。。010000，因此對於任何雜湊值H，由位向公式”H和16″生成的指數將是16或0。這意味著大小 17 的陣列將僅用於 2 個儲存桶：索引 0 的陣列和索引 16 的儲存桶，效率不是很高。。。

但是，如果你現在採取的大小是2像16的力量，位數公式是”H和15″。15的二進位制表示為0.。。001111，因此索引公式可以輸出 0 到 15 的值，並充分利用大小 16 的陣列。例如：

• 如果H=952，其二進位制表示為0.01110111000，相關指數為0.。01000 = 8
• 如果H=1576其二進位制表示為0.011000101000，則相關指數為0.。01000 = 8
• 如果H=12356146，其二進位制表示為0.0101111001000101010001000110010，相關指數為0.。。。00010 = 2
• 如果H=59843，其二進位制表示為0.01110100111000011，相關指數為0.。。。00011 = 3

自動調整尺寸

獲得索引後，函式（獲取、放置或刪除）訪問/重複關聯的連結列表，以檢視給定金鑰是否有現有條目。如果不進行修改，此機制可能導致效能問題，因為該功能需要透過整個列表進行重複，以檢視條目是否存在。想象一下，內部陣列的大小是預設值 （16），您需要儲存 200 萬個值。在最佳情況下，每個連結列表的大小為 125，000 條目（2/16 百萬）。因此，每個獲取（），刪除（）和放（）將導致125 000迭代/操作。為了避免這種情況，HashMap 能夠增加其內部陣列，以便保留非常短的連結列表。

建立HashMap時，您可以使用以下構造函件指定初始大小和載入因子：

public HashMap(int initialCapacity, float loadFactor)

如果您沒有指定引數，預設初始容量為 16，預設負載因子為 0.75。初始容量表示連結列表的內部陣列的大小。

每次在地圖中新增新的鍵/值時，功能都會檢查是否需要增加內部陣列的容量。為此，地圖儲存了 2 個數據：

• 地圖的大小：它表示雜湊對映中的條目數。每次新增或刪除條目時，此值都會更新。
• 閾值：它等於（內部陣列的容量）*載入因子，並在內部陣列的每次調整後重新整理

在新增新條目之前，放（…）檢查大小>閾值，如果是該閾值，則重新建立具有雙倍大小的新陣列。由於新陣列的大小發生了變化，索引函式（返回位向操作”雜湊（鍵）和（大小OfArray-1）”會發生變化。因此，陣列的調整將多建立兩倍的儲存桶（即連結列表），並將所有現有條目重新分配到儲存桶中（舊條目和新建立的條目）。

此調整操作的目的是減少連結列表的大小，以便放置（）、刪除（）和獲取（）方法的時間成本保持在較低水平。鍵具有相同雜湊的所有條目在調整大小後將保持在同一儲存桶中。但是，轉換後，之前在同一儲存桶中具有不同雜湊鍵的 2 個條目可能不在同一儲存桶中。

執行緒安全

如果你已經知道HashMap，你知道這不是執行緒安全，但為什麼？例如，想象一下，您有一個僅將新資料放入地圖的”作家”執行緒和一個讀取地圖資料的讀者執行緒，為什麼它不能工作？

因為在自動調整機制期間，如果執行緒試圖放置或獲取物件，則地圖可能會使用舊索引值，並且找不到條目中的新儲存桶。

最壞的情況是，2個執行緒同時放置資料，2個呼叫同時調整地圖大小。由於兩個執行緒同時修改連結的列表，地圖最終可能會在其連結列表中以內環結束。如果您嘗試使用內迴圈在列表中獲取資料，則獲取（）永遠不會結束。

Hash表實施是防止這種情況的執行緒安全實現。但是，由於所有 CRUD 方法都是同步的，此實現速度非常緩慢。例如，如果執行緒 1 呼叫獲得（鍵 1）、執行緒 2 呼叫獲取（鍵 2）和執行緒 3 呼叫獲取（鍵 3），則一次只能獲得一個執行緒值，而其中 3 個執行緒可以同時訪問資料。

自 JAVA 5：併發哈什圖以來，執行緒安全HashMap的更智慧實現存在。只有儲存桶是同步的，因此，如果多重執行緒並不意味著訪問同一儲存桶或調整內部陣列大小，則可以同時獲取（）、刪除（）或放置（）資料。最好在多讀應用程式中使用此實現。

下面是Java的具體例子。我在地圖中放置了 2 個鍵值對，修改了第一個金鑰，然後嘗試獲取 2 個值。只有第二個值從地圖返回，第一個值在Hash對映中”丟失”：

public class MutableKeyTest {
 
    public static void main(String[] args) {
 
        class MyKey {
            Integer i;
 
            public void setI(Integer i) {
                this.i = i;
            }
 
            public MyKey(Integer i) {
                this.i = i;
            }
 
            @Override
            public int hashCode() {
                return i;
            }
 
            @Override
            public boolean equals(Object obj) {
                if (obj instanceof MyKey) {
                    return i.equals(((MyKey) obj).i);
                } else
                    return false;
            }
 
        }
 
        Map<MyKey, String> myMap = new HashMap<>();
        MyKey key1 = new MyKey(1);
        MyKey key2 = new MyKey(2);
 
        myMap.put(key1, "test " + 1);
        myMap.put(key2, "test " + 2);
 
        // modifying key1
        key1.setI(3);
 
        String test1 = myMap.get(key1);
        String test2 = myMap.get(key2);
 
        System.out.println("test1= " + test1 + " test2=" + test2);
 
    }
 
}

爪哇 8

在 JAVA 8 中，雜湊圖的內部表示發生了很大變化。事實上，JAVA 7 中的實現需要 1k 行程式碼，而 JAVA 8 中的實現需要 2k 行。我以前說過的大部分都是正確的，除了連結的條目列表。在 JAVA8 中，您仍然有一個陣列，但它現在儲存的節點包含與條目完全相同的資訊，因此也是連結列表：

以下是 JAVA 8 中節點實現的一部分：

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

那麼跟 Java 7 有什麼大區別呢？

節點可以擴充套件到樹節點。TreeNode 是一種紅黑樹結構，儲存更多資訊，以便它可以在 O（日誌）中新增、刪除或獲取元素。

僅供參考，這裡是儲存在樹節內的資料的詳盡列表

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    final int hash; 
    final K key; 
    V value;
    Node<K,V> next; 
    Entry<K,V> before, after;
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;

效能問題

傾斜的HashMapvs平衡的HashMap

在最佳情況下，獲取（）和放置（）方法在時間複雜性方面具有 O（1） 成本。但是，如果你不照顧鍵的雜湊功能，你可能會結束非常緩慢的放（）和接聽電話。放（）和獲取的良好效能取決於將資料重新劃分到內部陣列（儲存桶）的不同索引中。如果您的金鑰的雜湊函式設計不當，則會進行偏斜重新劃分（無論內部陣列的容量有多大）。所有使用最大連結條目列表的放置（）和獲取（）的速度將很慢，因為它們需要對整個列表進行重複。在最壞的情況下（如果大多數資料都在同一儲存桶中），則最終可能會具有 O （n） 時間複雜性。 下面是一個視覺示例。第一張圖片顯示了一個傾斜的HashMap，第二張圖片是平衡的HashMap。

public class Test {
 
    public static void main(String[] args) {
 
        class MyKey {
            Integer i;
            public MyKey(Integer i){
                this.i =i;
            }
 
            @Override
            public int hashCode() {
                return 1;
            }
 
            @Override
            public boolean equals(Object obj) {
            …
            }
 
        }
        Date begin = new Date();
        Map <MyKey,String> myMap= new HashMap<>(2_500_000,1);
        for (int i=0;i<2_000_000;i++){
            myMap.put( new MyKey(i), "test "+i);
        }
 
        Date end = new Date();
        System.out.println("Duration (ms) "+ (end.getTime()-begin.getTime()));
    }
}

結論

對於簡單的使用案例，您不需要知道 HashMaps 的工作原理，因為您看不到 O （1） 和 O（n） 或 O（日誌（n））操作之間的區別。但是，理解最常用的資料結構之一的底層 mecanism 總是更好。此外，對於 java 開發人員的位置，這是一個典型的面試問題。

d大家實踐過程中遇到任何問題可以在評論區留言噢