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;