[譯]Java HashMap原理探究

bcjv0401 8年前發布 | 28K 次閱讀 Java 鏈表 Java開發

相信每個JAVA開發者都用過Map，特別是HashMap。HashMap是一個簡單但是強大的方式用于存儲和獲取數據。但是有多少人知道HashMap內部原理呢？前幾天，為了深入理解這個基礎數據結構，我閱讀了java.util.HashMap（先閱讀了Java7，然后看了Java8）中的大量的代碼。在這篇文章中，我將詳細解釋java.util.HashMap的執行過程，以及目前在Java 8中的新的執行方式，并且探討一下當使用HashMap時的性能、內存及已知的問題。

內部存儲

Java的HashMap類實現了接口Map<K,V>。這個接口的主要方法引入下：

1、V put(K key, V value)

2、V get(Object key)

3、V remove(Object key)

4、Boolean containsKey(Object key)

HashMap使用內部類Entry<K,V>來存儲數據。這個條目是一個具備兩個額外數據的鍵值對：

1、一個對其它Entry的引用，這樣HashMap就可以像單鏈表一樣存儲條目

2、一個哈希值展示了鍵的哈西值。存儲這個值目的在于避免每次HashMap需要這個值時進行重復計算。

下面時在Java 7中Entry的部分實現：

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

HashMap將數據存儲到多個條目的單線性鏈表中（也稱為桶或箱）。所有的列表注冊到一個Entry的數組中（Entry<K,V>[] array），這個數組磨人的長度時16.

上面的圖展示了一個存儲帶有空數組的HashMap實例的內部存儲情況。每個條目相互連接，形成了一個鏈表。

所有具有相同哈希值的鍵被放置到同一個鏈表（或稱為桶）中。具備不同哈希值的鍵用完后會放置到相同的桶中。

當開發者調用put(K key, V value)或者get(Object key)時，這些函數計算了這個條目應當在桶中的哪個位置（索引）。然后，函數迭代列表，找到與這個條目相同key的條目（使用了equals()對鍵進行比較）。

在get()，該函數返回與該條目關聯的值（如果條目存在）。

在put(K key, V value)中，如果條目存在，則函數使用新值進行覆蓋，否則就在單鏈表的頭部創建一個新條目（使用參數中的鍵值）。

Map生成桶（鏈表）索引分為以下三步：

1、首先取得鍵的hashcode

2、重新對hashcode生成哈希值，以此來避免不穩定的哈希函數會導致map將所有的數據放在了內部數組的相同索引位置（即相同的桶中）

3、接著取得重新哈希的值，使用數組的長度減一與之進行位與操作。這個操作確保索引的生成不會大于數組長度。你也可以把它看作一個被計算優化的模塊化函數。

下列在Java 7和Java 8中與索引相關的源碼：

// the "rehash" function in JAVA 7 that takes the hashcode of the key
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
// the "rehash" function in JAVA 8 that directly takes the key
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
// the function that returns the index from the rehashed hash
static int indexFor(int h, int length) {
    return h & (length-1);
}

為了能夠有效的工作，內部數組的大小必須時2的冪，下面讓我們一起看下為什么有這個要求。

假設數組的大小是17，那么掩碼值就需要是16（size-1）。代表16的二進制是0...010000，因此，對于任何哈希值H，使用按位與公式H AND 16計算得到的索引值要么是16要么是0.這就意味著長度為17的數組只能用于兩個桶：索引值為0和索引值為16的桶——這樣畢竟不是十分“高效”（譯者注：壓根就是浪費。）

但是，如果數組大小是2的冪，比如16，則按位與計算索引的公式變成了H AND 15。而15的二進制是0...001111，所以索引公式可以輸出從0到15的任意值，所以大小為16的數組就能被完全利用起來。比如：

>如果H=952，它的二進制表示為0...01110111000，分配給它索引就是0...01000=8

>如果H=1576，它的二進制表示為0...011000101000，分配給它索引就是0...01000=8

>如果H=12356146，它的二進制表示為0...0101111001000101000110010，分配給它索引就是0...00010=2

>如果H=59843，它的二進制表示為0...01110100111000011，分配給它的索引就是0...00011=3

以上體現出來的就是為什么數組大小是2的冪值。這項機制對開發者來說是透明的：如果開發者創建了一個大小為37的HashMap，則Map會自動將37*2=64作為內部數組的大小。

自動調整大小

獲得索引后，函數get(), put(), delete() 遍歷或者循環遍歷關聯的鏈表，看看給定鍵是否有值。在沒有修改的情況下，這種機制可能會造成性能問題，因為函數需要遍歷整個鏈表來檢查條目是否存在。想象一下，內部數組的大小是16，但是你需要存儲200萬個值。最理想的場景是每個鏈表均有125000個條目（2/16，單位：百萬）。所以，每個get(),put(),delete()會導致125000次遍歷操作。為了避免這種情況，HashMap有能力增加其內部數組數量，用來保持存儲的鏈表不至過長。

當你創建一個HashMap，你可以使用下面的構造函數指定initialCapacity（初始大小）和loadFactor（負載系數）：

public HashMap(int initialCapacity, float loadFactor)

如果你不指定上面的參數，則默認的initialCapacity=16，默認的loadFactor=0.75。initialCapacity表示了鏈表內部數組的大小。

每次使用函數put(...)向Map中添加新的鍵值對時，函數首先檢查是否需要擴充內部數組的大小。為了做到這一點，map存儲了兩個值： * map的尺寸：表示了HashMap中的條目數。每次添加或者移除條目時，這個值都會進行更新 * 閾值：閾值等于內部數組大小乘以負載系數，數值在每次內部數組重新分配大小之后刷新。

在添加新條目之前，put(...)會檢查如果數組大小大于閾值，則會創建一個具有兩倍大小的新數組。因為新數組大小已經改變，所以索引函數（按位與操作hash(key) AND (sizeOfArrya-1)）改變了。因此，調整數組大小為之前的2倍意味著可以存儲更多的桶（鏈表），接著重新把現有已存在的條目分配到桶中（這些桶有舊值也有新被創建的值）。

擴容操作的目標在于減少鏈表的大小，因此來保持get(),put()和delete()函數較低的時間花費。擴容后，所有key具有相同哈希值得條目會放置在相同的桶中，但是兩個具有不同哈希值的鍵的條目即使之前在相同的桶中，現在也不會被放置在相同的桶中了。

上圖展現了內部數組調整大小前后的情況。在擴容前，為了得到條目E，map需要遍歷鏈表中的5個元素，擴容后，相同的get()函數只需要遍歷鏈表中的兩個元素就可以得到條目E，擴容后get()比之前快了兩倍多！

注：HashMap僅提供增加內部數組的大小，不支持減少數組大小操作。

線程安全性

相信熟悉HashMap的開發者都了解，HashMap并不是線程安全的。但是為什么呢？想象一下你有一個寫線程講新值放入Map中，而另一個讀線程在Map中讀取數據，為什么不能正常工作呢？

因為如果碰上自動擴容，如果線程嘗試讀或者寫入對象，map可能會使用舊的索引，而不是找到條目應該在的新的桶。

最壞的場景是兩個線程同時向map中放置數據，然后兩put()操作都同時調用了Map的擴容方法。因為兩個線程在同一時間修改了鏈表，則Map很有可能在其內部鏈表之一中持續內部循環。如果你嘗試在一個具有內部循環的Map中取數據，那么你得get()永遠不會結束。

HashTable是線程安全的實現，避免了上面提到的這種情況的發生。但是，因為CRUD所有操作都被synchronized修飾，則這種實現十分緩慢。比如，如果線程1調用了get(key1)，線程2調用了get(key2)，線程3調用了get(key3)，一次只能有一個線程取到其值，及時3個線程同時執行，同時找到數據。

自從Java 5開始，存在了一個更聰明的線程安全的HashMap的實現：ConcurrentHashMap。只有桶是同步的，所以在不訪問相同的桶或者擴容內部數組大小的情況下，Map支持多線程同時get(), remove()或者put()。在多線程應用中，使用這種實現顯然是更好的選擇

鍵的不可變性

為什么字符類型和整數型適合做為HashMap的鍵？絕大部分的原因在于它們是不可變的！如果你選擇創建自己的Key類，并且不把它設為為不可變的，則在使用HashMap時，你可能會丟失數據。

看下面的使用案例：

1、你有一個內部值為1的鍵

2、使用這個Key，向HashMap中put一個對象

3、HashMap以用這個Key（這里值為1）生成一個哈希值

4、Map在新創建的條目中存儲了這個哈希值

5、修改Key的內部值為2

6、鍵的哈希值被修改，但是HashMap并不知情（因為舊的哈希值已經被存儲起來了）

7、你嘗試使用修改后的Key去HashMap中獲取對象

8、map嘗試用新的Key的哈希值去找條目在哪個鏈表里

情況1：由于Key被修改，所以Map嘗試在錯誤的桶中尋找條目，卻沒有找到

情況2：修改后的Key和修改前的Key生成的桶是同一個。Map遍歷鏈表，去找有相同Key的這個條目。但是為了找到相同的Key，Map首先比較兩者的哈希值，然后調用equals()進行比較。由于修改后的Key哈希值已經和舊值不同，則Map沒辦法在鏈表中找到條目。

這里有一個在Java中的具體例子。我在Map中放置了兩個鍵值對，修改了第一個Key，然后嘗試獲取這二個值。只有第二個值成功返回，第一個值丟失在HashMap中：

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

}
}

輸出是"test1= null test2=test 2"。正如預想的那樣，Map不能使用修改后的key去遍歷得到它的值。

Java 8 中的改進

在Java8中，HashMap的內部表現形式改變了很多。事實上，Java7中的實現大約是1k行代碼，而Java8中得實現大約是2k行代碼。上面提到的內容除了條目的鏈表，其他基本上都是正確的。在Java8中，你仍然有一個數組，但是現在它存儲了Node，Node就像Entry一樣，存儲了相同的信息，所以仍然是一個鏈表：下面是Java8中部分Node的實現代碼：

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

那么到底與Java7中最大的不同在哪里呢？答案是Node現在可以繼承TreeNode。一個TreeNode是一個紅黑樹結構，存儲了足夠多得信息，所以能在O(long(n))的復雜度下添加、刪除和獲取一個元素。

另外值得一提，下面是TreeNode內部存儲的詳盡的數據列表：

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

紅黑樹是自平衡二叉查找樹。他們的內部機制確保了無論是添加新的節點還是移除節點，長度總能保證在log(n)。使用樹的最大優勢在于萬一在內部表中相同索引的桶中存儲了大量的數據，使用樹的搜索僅需要O(long(n))的復雜度，而鏈表搜索的復雜度為O(n)。

正如你看到的那樣，樹結構比鏈表使用了更多的空間，這點，我們在下一部分詳細討論。

通過繼承，內部表可以同時包含Node（鏈表）和TreeNode（紅黑樹）。Oracle決定按照下面的規則使用兩個數據結構：

1、對于內部表中給定索引位置的桶超過8個節點，則鏈表轉換成紅黑樹

2、對于內部表中給定索引位置的桶低于6個節點，則樹會被轉換鏈表

上圖展示了在Java8中一個HashMap內部既有樹（0號桶）又有鏈表（1、2、3號桶）的情況。桶0是樹因為它有超過8個節點。

內存開銷

Java 7中

使用HashMap的代價全在內存。在Java 7中，一個HashMap將鍵值對包在條目中。一個條目具有：

1、一個對下一個條目的引用

2、一個預先計算過的哈希值（整形）

3、一個對key的引用

4、一個對value的引用

此外，Java7的HashMap使用內部條目數組。假設在Java7中一個HashMap包含N個元素，其內部數組的容量為CAPACITY，則額外的內存開銷大約是：

sizeOf(integer)* N + sizeOf(reference)* (3*N+C)

這里：

1、一個整形的大小是4個字節

2、引用的大小要看JVM、操作系統和處理器，但是通常是4個字節

這就意味著開銷通常是 16 * N + 4 * CAPACITY個字節。

提示：在Map擴容后，內部數組的CAPACITY等于N的下一個是2的冪的數字。

備注：自從Java7開始，HashMap類有懶加載。也就意味著及時你分配了一個HashMap，內部條目數組在不使用put()方法放置對象時是不會被分配內存的。

Java 8中

在Java8的實現中，估算內存使用變得有點復雜，因為一個Node可以和一個條目一樣存儲相同的數據，也可能要加上6個引用和一個布爾值（如果節點是一個TreeNode）。

如果所有的節點都是Node，那么Java8的HashMap的內存消耗和Java7中得HashMap應當是一樣的。

如果所有的節點都是TreeNode，那么Java8中得HashMap得內存消耗則變成了： N * sizeOf(integer) + N * sizeOf(boolean) + sizeOf(reference)* (9*N+CAPACITY ) 在大多數標準的JVM中，通暢等于44 * N + 4 * CAPACITY個字節。

性能問題

傾斜的HashMap vs 平衡的HashMap

最好的場景中，get()和put()方法均耗費O(1)的時間復雜度。但是，如果不注意鍵的哈希函數，則最終你可能在執行put()和get()時十分緩慢。性能良好的put()和get()取決于數據重新分配到不同索引的內部數組中。如果鍵的哈希函數設計不良，則可能會產生傾斜的重新分區（無論內部數組的容量有多大），所有與最長的鏈表打交道的put()和get()因為要便利整個鏈表，所以會變得很慢。在最壞的情況下（即所有的數據被放置在同一個桶中），時間復雜度就變成了O(n)。

下面是一個圖例，第一幅圖展示了一個傾斜的HashMap，第二張圖展示了一個平衡的HashMap。

在這個傾斜的HashMap中，在0號桶執行get()和put()操作花費十分昂貴。得到條目K需要6次迭代。

在這個平衡的HashMap中，取得條目K僅需要3次迭代。兩個HashMap存儲的相同的數據，并且內部數組大小一樣。唯一的區別在于鍵的哈希函數不同導致桶中條目的分布不同。

下面是一個極端的示例代碼，這段代碼中，我創建了一個哈希函數，將所有的數據放置在同一個桶中，然后我向桶中添加了200萬個元素。

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

在我配置為i5-2500k @ 3.6GHz的電腦上，使用Java 8u40，耗時超過了45分鐘（45分鐘后我停止了這個進程）。

現在，如果使用相同的代碼，只不過將哈希函數修改為下面的代碼：

@Override public int hashCode() { int key = 2097152-1; return key+2097152*i; } 則僅需要46s，簡直是巨大的進步！這個哈希函數比之前的函數具有更好的分配方案，所以put()的調用更快。

當我使用下面的哈希函數運行相同的代碼：

@Override public int hashCode() { return i; }

僅需2s！

我希望你能通過上面的例子意識到哈希函數的重要性。如果使用相同的例子在Java7中運行，結果會更差，因為在Java7中put()得時間復雜度是O(n)而在Java8中則是O(log(n))。

當使用HashMap是，你需要找到一個合適的哈希函數，將你的鍵盡可能分配到最多的桶中。為了做到這個，你需要避免哈希碰撞。String類型的對象是鍵的很好選擇，因為它有不錯的哈希函數。整形也不錯，因為它的哈希值就是他們自己本身的值。

調整大小的開銷

如果你需要存儲大量的數據，你應該在創建HashMap時指定初始化容量為你期待的值。

如果你不這樣做，Map會默認大小為16，負載率為0.75.那么前11個put()操作會很快，而第12個（16x0.75）會創建一個新的內部數組（關聯之前的鏈表或者樹），大小為32.那么第13到23個put()操作也會很快，但是第24個操作（32x0.75）又會花費昂貴來為內部數組的大小加倍。內部大小的調整操作會在第48、96、192...個put()操作調用時產生。當內部數組大小較小時，調整大小很快，但是當內部數組的容量不斷擴大，重新調整大小的耗時會由秒級到分鐘級。所以初始化期待的大小，可以避免這樣昂貴的操作。

當然這樣做也有缺點，如果你設置數組的大小非常大，比如2^28，而實際上僅僅使用了2^26個桶，那么會浪費大量的內存（大約為2^30個字節）。

結論

對于簡單的使用，你不需要知道HashMap的內部原理，因為你根本不會體會到O(1)、O（n）和O(log(n))操作的不同。但是了解一下常用數據結構內部機制總是更好的一件事情。另外，對于Java開發者來說，這也是一個典型的面試題。

在大數據量的情況下，了解哈希函數的內部原理和重要性是十分重要的。

我希望本文能幫助你對HashMap的實現有個更深的認識。

來自： http://www.jointforce.com/jfperiodical/article/2037

本文由用戶 bcjv0401 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1466149951121.html

Java 鏈表 Java開發