­

Java 中HashMap 詳解

本篇重點:

1.HashMap的存儲結構

2.HashMap的put和get操作過程

3.HashMap的擴容

4.關於transient關鍵字

 HashMap的存儲結構

1. HashMap 總體是數組+鏈表的存儲結構, 從JDK1.8開始,當數組的長度大於64,且鏈表的長度大於8的時候,會把鏈錶轉為紅黑樹。

2. 數組的默認長度是16。數組中的每一個元素為一個node,也就是鏈表的一個節點,node的數據包含: key的hashcode, key, value,指向下一個node節點的指針。

部分源碼如下:

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

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
...
}

3. 隨著put操作的進行,如果數組的長度超過64,且鏈表的長度大於8的時候, 則將鏈錶轉為紅黑樹,紅黑樹節點的結構如下,TreeNode繼承的LinkedHashMap.Entry是繼承HashMap.Node的,所以TreeNode是上面Node的子類。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
//...
}

4. HashMap類的主要成員變數:

/* ---------------- Fields -------------- */

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;

    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

View Code

HashMap的put操作過程

本小節講述put操作中的主要步驟,細小環節會忽略。

1. map.put(key, value),首先計算key的hash,得到一個int值。

2.如果Node數組為空則初始化Node數組。這裡注意,Node數組的長度length始終應該是2的n次方,比如默認的16, 還有32,64等 

3.用 hash&(length-1) 運算得到數組下標,這裡要提一句,其實正常我們最容易想到的,而且也是我之前很長一段時間以為的,這一步應該進行的是求模運算:hash % length,這樣得到的正好是0~length-1之間的值,可以作為數組的下標,那麼為何此處是位與運算呢?

先說結論:上面提到數組的長度length始終是2^n,在這個前提下,hash & (length-1) 與hash % length是等價的。 而位與運算更快。這裡後面會另開一遍進行詳解。

4.  如果Node[hash&(length-1)]處為空,用傳入的的key, value創建Node對象,直接放入該下標;如果該下標處不為空,且對象為TreeNode類型,證明此下標處的元素們是按照紅黑樹的結構存儲的,將傳入的key,value作為新的紅黑樹的節點插入到紅黑樹;否則,此處為鏈表,用next找到鏈表的末尾,將新的元素插入。如果在遍歷鏈表的過程中發現鏈表的長度超過了8,此時如果數組長度<64則進行擴容,否則轉紅黑樹。

5. 如果key的hash和key本身都相等則將該key對應的value更新為新的value

6. 需要擴容的話則進行擴容。

注意:

1. 如果key是null則返回的hash為0,也就是key為null的元素一直被放在數組下標為0的位置。

2. 在JDK 1.8以前,鏈表是採用的頭部插入的方式,從1.8改成了在鏈表尾部插入新元素的方式。 這麼做是為了防止在擴容的時候,多執行緒時出現循環鏈表死循環。具體會新開一遍進行詳細演繹。

HashMap的get操作過程

get的過程比較簡單。

1. map.get(key). 首先計算key的hash。

2. 根據hash&(length-1)定位到Node數組中的一個下標。如果該下標的元素(也就是鏈表/紅黑樹的第一個元素)中key的hash的key本身都和傳入的key相同,則證明找到了元素,直接返回即可。

3.如果第一個元素不是要找的,如果第一個元素的類型是TreeNode,則按照紅黑樹的查找方法查找元素,如果不是則證明是鏈表,按照next指針找下去,直到找到或者到達隊尾。

HashMap的擴容

先說這裡的兩個概念: size, length.

size:是map.size() 方法返回的值,表示的是map中有多少個key-value鍵值對兒

length: 這裡是指Node數組的長度,比如默認長度是16.

如下面的程式碼:

        Map<Integer,String> map = new HashMap<>();
        map.put(1,"a");
        map.put(2,"b");
        map.put(3,"c");    

沒有在構造函數中指定HashMap的大小,則數組的長度length取默認的16,put了3個元素,則size為3.

 

Q: 何時需要擴容呢?

A: 在put方法中,每次完成了put操作,都判斷一下++size是否大於threshold,如果大於則進行擴容: 調用resize()方法。

Q: 那麼threshold又是如何得到的呢?

A: 簡單來講threshold = length * loadfactor(默認為0.75)。 也就是說默認情況下,map中的鍵值對的個數(size)大於Node數組長度(length)的75%時,就需要擴容了。 

Q: 擴容時具體做什麼呢?

A: 首先計算出新的數組長度和新的threshold(閾值). 簡單來講,新的length/capacity 是原來的2倍(位運算左移一位),新的threshold為原來的2倍。 還有一些細節此處不再贅述。創建新的Node數組,將原來數組中的元素重新映射到新的數組中。

關於transient關鍵字

transient關鍵字的作用:用transient關鍵字修飾的欄位不會被序列化

查看下面的例子:

public class TransientExample implements Serializable{
    private String firstName;
    private transient String middleName;
    private String lastName;

    public TransientExample(String firstName,String middleName,String lastName) {
        this.firstName = firstName;
        this.middleName = middleName;
        this.lastName = lastName;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("firstName:").append(firstName).append("\n")
                .append("middleName:").append(middleName).append("\n")
                .append("lastName:").append(lastName);
        return sb.toString();


    }


    public static void main(String[] args) throws Exception {
        TransientExample e = new TransientExample("Adeline","test","Pan");

        ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("/path/testObj"));
        oos.writeObject(e);

        ObjectInputStream ois = new ObjectInputStream(new FileInputStream("/path/testObj"));
        TransientExample e1 = (TransientExample) ois.readObject();

        System.out.println("e:"+e.toString());
        System.out.println("e1:"+e1.toString());


    }
}

View Code

輸出結果:

e:firstName:Adeline
middleName:test
lastName:Pan
e1:firstName:Adeline middleName:
null lastName:Pan

被transient關鍵字修飾的middleName欄位沒有被序列化,反序列化回來的值是null

 

Q:HashMap類是實現了Serializable介面的,那麼為何其中的table, entrySet變數都標為transient呢?

A:我們知道,table數組中元素分布的下標位置是根據元素中key的hash進行散列運算得到的,而hash運算是native的,不同平台得到的結果可能是不相同的。舉一個簡單的例子,假設我們在目前的平台有鍵值對 key1-value1,計算出key1的hash為1, 計算後存在table數組中下標為1的地方,假設table被序列化了,並傳輸到了另外的平台,並反序列化為了原來的HashMap,key1-value1仍然存在下標1的位置,當在這個平台運行get(“key1”)的時候,可能計算出key1的hash為2,就有可能到下標為2的地方去找該元素,這樣就出錯了。

Q:那麼HashMap是如何實現的序列化呢?

A:HashMap是通過實現如下方法直接將元素數量(size), key, value等寫入到了ObjectOutputStream中,實現的訂製化的序列化和反序列化。在Serializable介面中有關於這種做法的說明。

private void writeObject(java.io.ObjectOutputStream out)

       throws IOException

private void readObject(java.io.ObjectInputStream in)

       throws IOException, ClassNotFoundException;