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;
