本篇重點：
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 =https://www.cnblogs.com/adeline-tech/archive/2022/09/14/ 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;
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/508099.html
標籤：其他