細讀源碼之-HashMap

文章将在我的Git Page更新 原文連結

前言

大家開發中用得最多的工具類就是JAVA的集合架構了，今天我們來從源碼的角度剖析Map集合的實作之一

HashMap

。

HashMap 簡介

這裡我就直接翻譯JDK源碼注釋了，其實注釋講得很詳細了。

基于哈希表的Map接口的實作。 此實作提供所有可選的映射操作，并允許空值和空鍵。 （ HashMap類與Hashtable大緻等效，不同之處在于它是不同步的，并且允許為null。）此類不保證映射的順序。 特别是，它不能保證順序會随着時間的推移保持恒定。

假設哈希函數将元素正确分散在存儲桶中，則此實作為基本操作（ get和put ）提供恒定時間(這裡指時間複雜度為o1)的性能。 集合視圖上的疊代所需的時間與HashMap執行個體的“容量”（存儲桶數）及其大小（鍵-值映射數）成正比。 是以，如果疊代性能很重要，則不要将初始容量設定得過高（或負載因數過低），這一點非常重要。

HashMap的執行個體具有兩個影響其性能的參數：初始容量和負載因子。 容量是哈希表中存儲桶的數量，初始容量隻是建立哈希表時的容量。 負載因子是在自動增加其哈希表容量之前允許哈希表獲得的滿度的度量。 當哈希表中的條目數超過負載因子和目前容量的乘積時，哈希表将被重新哈希（即，内部資料結構将被重建），是以哈希表的存儲桶數約為兩倍。

通常，預設負載因子（.75）在時間和空間成本之間提供了一個很好的權衡。 較高的值會減少空間開銷，但會增加查找成本（在HashMap類的大多數操作中都得到展現，包括get和put ）。 設定其初始容量時，應考慮映射中的預期條目數及其負載因子，以最大程度地減少重新哈希操作的次數。 如果初始容量大于最大條目數除以負載因子，則将不會發生任何哈希操作。

如果将許多映射存儲在HashMap執行個體中，則建立具有足夠大容量的映射将比讓其根據需要增長表的自動重新哈希處理更有效地存儲映射。 請注意，使用具有相同hashCode()許多鍵是降低任何哈希表性能的肯定方法。 為了改善影響，當鍵為Comparable ，此類可以使用鍵之間的比較順序來幫助打破平局。

請注意，此實作未同步。 如果多個線程同時通路哈希映射，并且至少有一個線程在結構上修改該映射，則必須在外部進行同步。 （結構修改是添加或删除一個或多個映射的任何操作；僅更改與執行個體已經包含的鍵相關聯的值不是結構修改。）通常通過在自然封裝了Map的某個對象上進行同步來實作。 。 如果不存在這樣的對象，則應使用Collections.synchronizedMap方法“包裝”Map。 最好在建立時完成此操作，以防止意外不同步地通路Map：

Map m = Collections.synchronizedMap(new HashMap(...));           

該類的所有“集合視圖方法”傳回的疊代器都是快速失敗的：如果在建立疊代器後的任何ff時間以任何方式對Map進行結構修改，則除了通過疊代器自己的remove方法之外，疊代器都會抛出ConcurrentModificationException 。 是以，面對并發修改，疊代器會快速幹淨地失敗，而不會在未來的不确定時間冒着任意，不确定的行為的風險。

請注意，疊代器的快速失敗行為無法得到保證，因為通常來說，在存在不同步的并發修改的情況下，不可能做出任何嚴格的保證。 快速失敗的疊代器會盡最大努力抛出ConcurrentModificationException 。 是以，編寫依賴于此異常的程式的正确性是錯誤的：疊代器的快速失敗行為應僅用于檢測錯誤。

此類是Java Collections Framework的成員

幾個重要的成員變量

• Node<K,V>[] table

  核心資料結構 數組 + 連結清單

• int size

  集合的大小

• int modCount

  被修改的次數

• int threshold

  下一個要調整大小的大小值（容量 * 負載因子)

• float loadFactor

  負載因子

• Set<Map.Entry<K,V>> entrySet

  KV集

方法

構造方法

HashMap

有多個重載構造方法，但最終都會去掉下面這個構造方法

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }           

有兩個參數

• initialCapacity 初始容量
• loadFactor 負載因子

HashMap

就是對

散清單

這種資料結構的實作，是以需要這個兩個參數去定義

散清單

tableSizeFor

我們從上面的構造方法可以看出，

HashMap

在初始化的時候，會調用這個方法去計算實際初始化的容量并暫存為

threshold

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }           

這個方法傳回大于輸入參數且最近的2的整數次幂的數。比如10，則傳回16。

先來分析有關n位操作部分：先來假設n的二進制為01xxx...xxx。接着

• 對n右移1位：001xx...xxx，再位或：011xx...xxx
• 對n右移2為：00011...xxx，再位或：01111...xxx
• 此時前面已經有四個1了，再右移4位且位或可得8個1
• 同理，有8個1，右移8位肯定會讓後八位也為1。

綜上可得，該算法讓最高位的1後面的位全變為1。

最後再讓結果n+1，即得到了2的整數次幂的值了。

現在回來看看第一條語句：

int n = cap - 1;           

讓

cap - 1

再指派給n的目的是另找到的目标值大于或等于原值。例如二進制1000，十進制數值為8。如果不對它減1而直接操作，将得到答案10000，即16。顯然不是結果。減1後二進制為111，再進行操作則會得到原來的數值1000，即8。

這種方法的效率非常高，可見Java8對容器優化了很多

hash

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
           

這裡是取hash的高16位與hash值進行異或運算，因為在進行槽位計算的時候容易丢失高位的特征，是以采取低位與高位進行運算獲得一個結果，保留了高位與低位的特征。如果采用

|

将會使位偏向1，如果采用

&

将會偏向0，而采用

^

則沒有明顯的偏向性。

槽位計算源碼

tab[i = (n - 1) & hash]           

PUT

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }           

這個方法将元素加入散清單，具體實作是下面這個

putVal

/**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }           

明确幾個局部變量的意義

• Node<K,V>[] tab

  散清單

• Node<K,V> p

  新增的節點

• int n

  散清單數組的長度

• int i

  計算出的槽位

我們跟随源碼的流程進行分析

首先判斷散清單是否有被建立出來，如果沒有建立，則進行散清單的初始化。這是一種懶加載政策。初始化的過程我們下面再分析。

然後就是計算散列位置，判斷該位置上是否有元素。若沒有則直接把元素放入。如果該節點上有元素了，則發生了hash碰撞，需要另外的處理。

下面分析一下槽點計算的源碼

i = (n - 1) & hash           

将容量-1與hash值進行與運算。由于散清單在初始化的時候，容量是2的次幂，是以在減一之後，二進制位都變為了1，再與hash值進行與運算其實就是取餘數，這個就相當于

hash % n

。但是效率确比取模運算高出很多。