一、HashMap
HashMap 是一種用於儲存鍵值對的資料型別，基於雜湊表的 Map 介面的非同步實現，key 可以為 null，不允許插入重複的 key，允許 value 重複
HashMap 實際上是陣列+連結串列+紅黑樹的結合體，其底層包含一個數組，陣列中每一項元素的型別分為四種可能：null、單獨一個結點、連結串列、紅黑樹（JDK1.8 開始透過使用紅黑樹來提高元素查詢效率）。當往 HashMap 中存入元素時，會先根據 key 的雜湊值得到該元素在陣列中的位置（即陣列下標），如果該位置上已經存放有其它元素了，那麼在這個位置上的元素將以連結串列或者紅黑樹的形式來存放，如果該位置上沒有元素，就直接向該位置存放元素。因此 HashMap 要求 key 必須是不可變物件，即 key 的雜湊值不能發生改變，否則就會導致後續訪問時無法定位到它的存放位置了
1、雜湊Hash，一般翻譯做雜湊或者雜湊，是把輸入的任意物件透過雜湊演算法變換成固定長度的輸出，該輸出就是雜湊值。不同的輸入可能會雜湊成相同的輸出，所以不可能從雜湊值來確定唯一的輸入值，但可以將雜湊值作為這個物件的一個特徵
雜湊的作用可以透過舉一個例子來說明。假設存在一千個單詞，現在需要從中找到“hello”這個單詞的位置索引，那麼最直觀的做法就是將這些單詞儲存到一個長度為一千的陣列中並進行遍歷，最壞的結果就需要遍歷一千次。如果單詞數量越多，那麼需要的陣列空間就會越多，平均需要進行遍歷的次數也會越高。為了節省記憶體空間並減少遍歷次數，我們可以透過雜湊演算法拿到每個單詞的雜湊值，將這些雜湊值對映為一個長度為一百的陣列內的索引值，在該索引位置上儲存對應的單詞。如果採用的雜湊演算法足夠優秀，不同的單詞得到的雜湊值就具有很大的隨機性，這樣一千個單詞就可以均勻地分佈到陣列內了，最好的情況就是每個陣列位置只儲存十個單詞，這十個單詞再按照連結串列或者其它資料結構串聯起來。這樣我們在查詢的時候只需要計算出“hello”對應的索引值，然後在這個索引位置遍歷十個單詞即可。如果陣列空間足夠大，雜湊演算法得到的索引值足夠均勻，那麼最好的情況就是隻需要進行一次查詢就可以得到目標結果，最壞的結果也只是需要查詢該位置上的所有單詞即可，大大減少了遍歷次數
HashMap 內部就採用了雜湊演算法來儲存元素。但由於雜湊演算法對於不同的輸入有可能會雜湊成相同的輸出，而且陣列空間不可能是無限大的，所以在同個陣列位置上就不可避免的需要儲存多個元素了，這種情況就叫做雜湊衝突。此外，HashMap 不保證元素的儲存順序和迭代順序，因為根據需要 HashMap 會對元素重新雜湊，元素的順序也會被再次打亂，因此在不同時間段其儲存順序和迭代順序都可能會發現變化。此外，HashMap 也不保證執行緒安全，如果有多個執行緒同時進行寫操作的話可能會導致資料錯亂甚至執行緒死鎖
2、類宣告 public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable複製程式碼HashMap 中的全域性常量主要看以下幾個
//雜湊桶陣列的預設容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //雜湊桶陣列能夠達到的最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //裝載因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //為了提高效率，當連結串列的長度超出這個值時，就將連結串列轉換為紅黑樹 static final int TREEIFY_THRESHOLD = 8; //當紅黑樹的長度小於這個值時，就將紅黑樹轉換為連結串列 static final int UNTREEIFY_THRESHOLD = 6;複製程式碼裝載因子用於規定陣列在自動擴容之前資料佔有其容量的最高比例，即當資料量佔有陣列的容量達到這個比例後，陣列將自動擴容。裝載因子衡量的是一個散列表的空間的使用程度，裝載因子越大表示散列表的裝填程度越高，反之愈小。對於使用連結串列的散列表來說，查詢一個元素的平均時間是O(1+a)，因此裝載因子越大，對空間的利用程度就越高，相對應的是查詢效率越低。如果裝載因子太小，那麼陣列的資料將過於稀疏，對空間的利用率就變低，相應查詢效率也會提升
官方預設的裝載因子大小是 DEFAULT_LOAD_FACTOR，即 0.75，是平衡空間利用率和查詢效率兩者之後的結果。在實際情況中，如果記憶體空間較多而對時間效率要求很高，可以選擇降低裝載因子大小；如果記憶體空間緊張而對時間效率要求不高，則可以選擇加大裝載因子
此外，即使裝載因子和雜湊演算法設計得再合理，也難免會出現由於雜湊衝突導致連結串列長度過長的情況，這也將影響 HashMap 的效能。為了最佳化效能，從 JDK1.8 開始引入了紅黑樹，當連結串列長度超出 TREEIFY_THRESHOLD 規定的值時，連結串列就會被轉換為紅黑樹，利用紅黑樹快速增刪改查的特點以提高 HashMap 的效能
4、變數 //雜湊桶陣列，在第一次使用時才初始化 //容量值應是2的整數倍 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; //Map的大小 transient int size; //每當Map的結構發生變化時，此引數就會遞增 //當在對Map進行迭代操作時，迭代器會檢查此引數值 //如果檢查到此引數的值發生變化，就說明在迭代的過程中Map的結構發生了變化，因此會直接丟擲異常 transient int modCount; //陣列的擴容臨界點，當陣列的資料量達到這個值時就會進行擴容操作 //計算方法：當前容量 x 裝載因子 int threshold; //使用的裝載因子值 final float loadFactor;複製程式碼 //設定Map的初始化大小和裝載因子 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); } //設定初始化大小 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //使用預設值 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } //傳入初始資料 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }複製程式碼在上邊說過，HashMap 是 陣列+連結串列+紅黑樹 的結合體，陣列中每一項元素的型別分為四種可能：null、單獨一個結點、連結串列、紅黑樹
每一個要插入的鍵值對都會被包裝為 Node 物件，根據 key 的雜湊值來決定 Node 物件在陣列中的位置。如果計算出的位置此時不包含值，即為 null，則直接將 Node 物件放到該位置即可；如果不為 null ，則說明發生了雜湊碰撞，此時就需要將 Node 物件插入到連結串列或者是紅黑樹中。如果 key 與連結串列或紅黑樹中某個已有結點的 key 相等（hash 值相等且兩者 equals 成立），則新新增的 Node 物件將覆蓋原有資料
當雜湊演算法的計算結果越分散均勻，發生雜湊碰撞的機率就越小，HashMap 的存取效率就會越高
Node 類的宣告如下所示
static class Node<K,V> implements Map.Entry<K,V> { //key 的雜湊值 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; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }複製程式碼插入鍵值對的方法是 put(K key, V value)
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //計算 key 的雜湊值 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }複製程式碼putVal 方法較為複雜，因為該方法要考慮以下幾種情況：
如果 table 還未初始化或者容量為 0 則進行初始化和擴容判斷是否存在雜湊衝突如果不存在雜湊衝突，則直接將該鍵值對存入計算出來的位置如果存在雜湊衝突，則將鍵值對新增到該位置的紅黑樹或者連結串列上，並且在連結串列達到最大長度時將連結串列轉換為紅黑樹當存在相同 key 的結點時，判斷是否需要覆蓋舊值為 LinkedHashMap 預留方法埋點當儲存鍵值對後，進行必要的擴容 /** * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent 為 true 表示不會覆蓋有相同 key 的非 null 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; //如果 table 還未初始化或者容量為0，則呼叫 resize 方法進行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //判斷要存入的 key 是否存在雜湊衝突 //p 指向了鍵值對希望存入的陣列位置 //p 等於 null 說明不存在衝突 if ((p = tab[i = (n - 1) & hash]) == null) //直接在索引 i 處構建包含待存入元素的結點 tab[i] = newNode(hash, key, value, null); else { //走入本分支，說明待存入的 key 存在雜湊衝突 Node<K, V> e; K k; //p 值已在上一個 if 語句中賦值了，此處就直接來判斷 Node key 的相等性 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //會走進這裡，說明 p 結點 key 和待存入的鍵值對 key 相等 //此時該位置可能只有一個結點，也有可能是紅黑樹或者連結串列， //那麼 e 就指向該衝突結點 //此時就已經找到了鍵值對待存入的位置了 e = p; //如果 Node key 不相等，且頭結點是 TreeNode 型別，說明此時該位置當前是採用紅黑樹來處理雜湊衝突 else if (p instanceof TreeNode) //如果紅黑樹中不存在相同 key 的話則插入儲存鍵值對並返回 null，否則不儲存並返回該該相同 key 的結點 e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); else { //該位置當前是採用連結串列來處理雜湊衝突 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //會走進這裡，說明遍歷到了連結串列尾部，且連結串列中每個結點的 key 均不相等 //那麼就將其新增到連結串列尾部 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)))) //找到了相同 key 的結點，即 e break; p = e; } } //如果 e != null，說明原先存在相同 key 的鍵值對 //那麼就再來判斷下是否需要覆蓋 value if (e != null) { V oldValue = e.value; //如果 onlyIfAbsent 為 false 或者 oldValue 為 null 則覆蓋原有值 if (!onlyIfAbsent || oldValue == null) e.value = value; //用於 LinkedHashMap ，在 HashMap 中是空實現 afterNodeAccess(e); return oldValue; } } ++modCount; //判斷是否需要擴容 if (++size > threshold) resize(); //用於 LinkedHashMap ，在 HashMap 中是空實現 afterNodeInsertion(evict); return null; }複製程式碼獲取 value 對應的是 get(Object key)方法
public V get(Object key) { Node<K, V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } //根據 key 獲取結點 final Node<K, V> getNode(int hash, Object key) { Node<K, V>[] tab; Node<K, V> first, e; int n; K k; //只有當 table 不為空且 hash 對應的位置不為 null 時說明才有可能存在該 key if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) //如果與頭結點相等的話說明找到了對應值 return first; // e != null 說明存在該位置存在連結串列或紅黑樹，那麼就從這兩者中獲取 if ((e = first.next) != null) { if (first instanceof TreeNode) //紅黑樹 return ((TreeNode<K, V>) first).getTreeNode(hash, key); do { //連結串列 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }複製程式碼從 Map 中移除鍵值對的操作，對於其底層資料結構的體現就是要移除對某個 Node 物件的引用，這個資料結構可能是陣列、紅黑樹、或者連結串列
//如果真的存在該 key，則返回對應的 value，否則返回 null public V remove(Object key) { Node<K, V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * @param value key對應的值，只有當matchValue為true時才需要使用到，否則忽略該值 * @param matchValue 如果為 true ，則只有當找到key和value均匹配的結點時才會移除該結點，否則只要key相等就直接移除該元素 * @param movable if false do not move other nodes while removing * @return the node, or null if none */ final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K, V>[] tab; Node<K, V> p; int n, index; //只有當 table 不為空且 hash 對應的位置不為 null 時說明才有可能存在該 key if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K, V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果與頭結點 p 的 key 相等，那麼就已經找到了目標 node node = p; else if ((e = p.next) != null) { //存在紅黑樹或者連結串列 if (p instanceof TreeNode) //紅黑樹 node = ((TreeNode<K, V>) p).getTreeNode(hash, key); else { //連結串列 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } //node != null 說明存在 key 對應結點 //如果 matchValue 為 false ，則此處就可以直接移除結點 node //如果 matchValue 為 true ，則當 value 相等時才需要移除該結點 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) //紅黑樹 ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable); else if (node == p) //對應 key 與頭結點相等的情況，此時直接將指標移向下一位即可 tab[index] = node.next; else //連結串列 p.next = node.next; ++modCount; --size; //用於 LinkedHashMap ，在 HashMap 中是空實現 afterNodeRemoval(node); return node; } } return null; }複製程式碼在插入、查詢和移除鍵值對時，定位到雜湊桶陣列的對應位置都是很關鍵的第一步，只有 HashMap 中的元素儘量分佈均勻，才能儘量讓陣列中的每個位置都只儲存一個 Node，避免頻繁地去構建和遍歷連結串列或者紅黑樹，這就需要依靠於一個比較好的雜湊演算法了
以下是 HashMap 中計算 key 值的雜湊值以及根據雜湊值獲取其在雜湊桶陣列中位置的方法
static final int hash(Object key) { int h; //高位參與運算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //根據 key 值獲取 Value public V get(Object key) { Node<K, V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } //查詢指定結點 final Node<K, V> getNode(int hash, Object key) { ··· //只有當 table 不為空且 hash 對應的位置不為 null 才有可獲取的元素值 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { ··· } return null; }複製程式碼確定鍵值對在雜湊桶陣列的位置的步驟分為三步：
計算 key 的 hashCode：h = key.hashCode()高位運算：h >>> 16取模運算：（n - 1) & hash我也不懂這麼取值的優點在於哪裡，就不多說了
10、擴容如果雜湊桶陣列很大，即使是較差的雜湊演算法，元素也會比較分散；如果雜湊桶陣列很小，即使是好的雜湊演算法也會出現較多雜湊碰撞的情況，所以就需要在空間成本和時間成本之間權衡，除了需要設計較好的雜湊演算法以便減少雜湊衝突外，也需要在合適的的時機對雜湊桶陣列進行擴容
當 HashMap 中的元素越來越多時，因為陣列的容量是固定的，所以雜湊衝突的機率也會越來越高，為了提高效率，此時就需要對 HashMap 中的陣列進行擴容，而擴容操作最消耗效能的地方就在於：原陣列中的資料必須重新計算其在新陣列中的位置並遷移到新陣列中
那麼 HashMap 擴容操作的觸發時機是什麼時候呢？當 HashMap 中的元素個數超出 threshold 時（陣列容量 與 loadFactor 的乘積），就會進行陣列擴容。例如，假設陣列當前大小是16，loadFactor 值是0.75，那麼當 HashMap 中的元素個數達到12個時，就會自動觸發擴容操作，把陣列的大小擴充到 2 * 16 = 32，即擴大一倍，然後重新計算每個元素在新陣列中的位置，這是一個非常消耗效能的操作，所以如果已經預知到待存入 HashMap 的資料量，那麼在初始化 HashMap 時直接指定初始化大小會是一種更為高效的做法
預設情況下，陣列的容量是 16，loadFactor 是 0.75，這是平衡空間利用率和時間效率兩者之後的結果
初始化陣列和擴容陣列這兩個操作對應的是 resize()方法
final Node<K, V>[] resize() { //擴容前的陣列 Node<K, V>[] oldTab = table; //擴容前陣列的容量 int oldCap = (oldTab == null) ? 0 : oldTab.length; //當前的擴容臨界值 int oldThr = threshold; //擴容後的陣列容量和擴容臨界值 int newCap, newThr = 0; if (oldCap > 0) { //oldCap > 0 對應的是 table 已被初始化的情況，此時是來判斷是否需要進行擴容 //如果陣列已達到最大容量，則不再進行擴容，並將擴容臨界點 threshold 提升到 Integer.MAX_VALUE，結束 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) { //如果將陣列的現有容量提升到兩倍依然小於 MAXIMUM_CAPACITY，且現有容量大於等於 DEFAULT_INITIAL_CAPACITY //則將陣列的容量和擴容臨界值均提升為原先的兩倍 newThr = oldThr << 1; } //此處應該還有一種情況 //即將陣列的現有容量提升到現在的兩倍後大於等於 MAXIMUM_CAPACITY 的情況 //此時 newThr 等於 0，newCap 等於 oldCap 的兩倍值 //此處並沒有對 newCap 的數值進行還原，說明 HashMap 是允許擴容後容量超出 MAXIMUM_CAPACITY 的 //只是在現有容量超出 MAXIMUM_CAPACITY 後，不允許再次進行擴容 } else if (oldThr > 0) { //oldCap <= 0 && oldThr > 0 //對應的是 table 還未被初始化，且在呼叫建構函式時有傳入 initialCapacity 或者 Map 的情況 //此時就直接將容量提升為 threshold，在後邊重新計算新的擴容臨界值 newCap = oldThr; } else { //oldCap <= 0 && oldThr <= 0 //對應的是 table 還未被初始化，且呼叫的是無參建構函式 //將 table 的容量擴充到預設大小，並使用預設的裝載因子來計算擴容臨界值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float) newCap * loadFactor; //計算擴容後新的擴容臨界值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes", "unchecked"}) Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; table = newTab; //如果舊陣列中存在值，則需要將其中的資料複製到新陣列中 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K, V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //e.next == null 說明元素 e 沒有產生 hash 衝突，因此可以直接轉移該元素 if (e.next == null) //計算元素 e 在新陣列中的位置 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //存在雜湊衝突且是用了紅黑樹 ((TreeNode<K, V>) e).split(this, newTab, j, oldCap); else { //存在雜湊衝突且是用了連結串列 Node<K, V> loHead = null, loTail = null; Node<K, V> hiHead = null, hiTail = null; Node<K, V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }複製程式碼這裡來測試下不同的初始化大小和不同情況下的 hashCode 值對 HashMap 執行效率的影響
首先來定義作為鍵值對 key 的類，hashCode() 方法直接返回其 value 屬性
public class Key { private int value; public Key(int value) { this.value = value; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Key key = (Key) o; return value == key.value; } @Override public int hashCode() { return value; }}複製程式碼初始化大小從 200 到 200000 之間以 10 倍的倍數遞增，向不同 HashMap 存入同等資料量的資料，觀察存入資料所需要的時間
public class Test { private static final int MAX_KEY = 20000; private static final Key[] KEYS = new Key[MAX_KEY]; static { for (int i = 0; i < MAX_KEY; i++) { KEYS[i] = new Key(i); } } private static void test(int size) { long startTime = System.currentTimeMillis(); Map<Key, Integer> map = new HashMap<>(size); for (int i = 0; i < MAX_KEY; i++) { map.put(KEYS[i], i); } long endTime = System.currentTimeMillis(); System.out.println("初始化大小是：" + size + "，用時：" + (endTime - startTime) + "毫秒"); } public static void main(String[] args) { for (int i = 20; i <= MAX_KEY; i *= 10) { test(i); } }}複製程式碼在上述例子中，各個 Key 物件之間的雜湊值各不相同，所以鍵值對在雜湊桶陣列中的分佈可以說是很均勻的了，此時主要影響效能的就是擴容機制了，由日誌可以看出此時不同的初始化大小對 HashMap 的效能影響還不大
初始化大小是：20，用時：4毫秒初始化大小是：200，用時：3毫秒初始化大小是：2000，用時：4毫秒初始化大小是：20000，用時：2毫秒複製程式碼如果讓 Key 類的 hashCode() 方法固定返回 100，那麼每個 Key 物件在存在 HashMap 時肯定都會發生雜湊衝突
@Override public int hashCode() { return 100; }複製程式碼可以看到此時存入同等資料量的資料所需要的時間就呈幾何數增長了，說明如果存在大量雜湊衝突的話對 HashMap 的影響還是很大的
初始化大小是：20，用時：2056毫秒初始化大小是：200，用時：1902毫秒初始化大小是：2000，用時：1892毫秒初始化大小是：20000，用時：1865毫秒複製程式碼HashMap 並不保證元素的儲存順序和迭代順序能夠和存入順序保持一致，即 HashMap 本身是無序的。為了解決這一個問題，Java 提供了 LinkedHashMap 來實現有序的 HashMap
1、類宣告LinkedHashMap 是 HashMap 的子類，它保留了元素的插入順序，其內部維護著一個按照元素插入順序或者元素訪問順序來排列的連結串列，預設是按照元素的插入順序來排列，就像使用 ArrayList 一樣；如果是按照元素的訪問順序來排列，那麼每次訪問元素後該元素將移至連結串列的尾部，可以靠此來實現 LRUcache 快取演算法
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>複製程式碼HashMap 中每個存入的鍵值對都會被包裝為 Node 物件，LinkedHashMap 則是包裝為 Entry 物件，看 newNode 方法就知道了。Entry 類在 Node 類的基礎上擴充套件了兩個新的成員變數：before 和 after，這兩個變數就是 LinkedHashMap 來實現有序訪問的關鍵。每當儲存了新的鍵值對，Entry 就會透過這兩個變數將其和之前的鍵值對串聯起來，儲存為連結串列的尾結點，從而保留了鍵值對的順序資訊
不管 Entry 在 HashMap 內部為了解決雜湊衝突採用的是連結串列還是紅黑樹，這兩個變數的指向都不受資料結構變化的影響。從這也可以看出集合框架在設計時一個很巧妙的地方：LinkedHashMap 內部沒有新建一個連結串列用來維護元素的插入順序，而是透過擴充套件父類來實現擴充套件功能
static class Entry<K,V> extends HashMap.Node<K,V> { //用於指定上一個結點 before 和下一個結點 after Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); linkNodeLast(p); return p; }複製程式碼變數 accessOrder 用於決定 LinkedHashMap 中元素的排序方式，如果為 true 就按照元素訪問順序來排序，為 false 就按照元素插入順序來排序
//序列化ID private static final long serialVersionUID = 3801124242820219131L; //指向雙向連結串列的頭結點 transient LinkedHashMap.Entry<K,V> head; //指向最新訪問的結點 transient LinkedHashMap.Entry<K,V> tail; final boolean accessOrder;複製程式碼預設情況下 LinkedHashMap 都是按照元素插入順序來排序
public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } public LinkedHashMap() { super(); accessOrder = false; } public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }複製程式碼在 HashMap 中有三個預留的空方法，原始碼註釋中也寫明這三個函式就是為 LinkedHashMap 預留的
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }複製程式碼當 HashMap 中的某個結點被訪問了（例如呼叫了 get 方法）且 accessOrder 為 true，那麼afterNodeAccess 方法就會被呼叫，該方法用於將最新訪問的鍵值對移至連結串列的尾部，由於連結串列內結點位置的改變僅僅是修改幾個引用即可，所以這個操作還是非常輕量級的
public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; } //當訪問了結點 e 時呼叫 //結點 e 是最新訪問的一個結點，此時就將結點 e 置為連結串列的尾結點 void afterNodeAccess(Node<K,V> e) { //last 用來指向連結串列的尾結點 LinkedHashMap.Entry<K,V> last; //只有當 last 和 e 不相等時才需要進行下一步，如果相等說明 e 已經在連結串列尾部了 if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //因為結點 p 將成為尾結點，所以 after 置為null p.after = null; //如果 b == null ，說明結點 p 此時是連結串列的頭結點，那 a 就會成為新的頭結點 //如果 b != null ，則移除結點 b 對結點 p 的引用並和 a 串聯起來 if (b == null) head = a; else b.after = a; //如果 a != null，說明結點 p 此時不是連結串列的尾結點，則移除結點 a 對結點 p 的引用並和 b 串聯起來 //如果 a == null，則說明結點 p 此時是連結串列的尾結點，那 a 就會成為新的尾結點 if (a != null) a.before = b; else last = b; //如果 last == null，說明原連結串列為空，則此時頭結點就是結點 p //如果 last != null，則 p 就會成為新的尾結點 if (last == null) head = p; else { p.before = last; last.after = p; } //最新一個引用到的結點就是 tail tail = p; ++modCount; } }複製程式碼當 put 方法被呼叫時afterNodeInsertion 方法也會被呼叫，該方法用於判斷是否移除最近最少使用的元素，依此可以來構建 LRUcache 快取
//在插入元素後呼叫，此方法可用於 LRUcache 演算法中移除最近最少使用的元素 void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } //此方法就用於決定是否移除最舊的快取，預設返回 false //可以透過重寫該方法來實現按照特定規則移除舊資料 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }複製程式碼當 HashMap 內部移除了某個結點時，LinkedHashMap 也要透過 afterNodeRemoval 方法將對該結點的引用從維護的連結串列中移除
//在移除結點 e 後呼叫 void afterNodeRemoval(Node<K,V> e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //移除結點 p 對相鄰結點的引用 p.before = p.after = null; //如果 b == null，說明結點 p 是連結串列的頭結點，則 a 將成為新的頭結點 //如果 b != null，則更新結點間的引用 if (b == null) head = a; else b.after = a; //如果 a == null，說明結點 a 是尾結點，則移除結點 p 後最新一個訪問的結點就是原倒數第二的結點 //如果 a != null，則更新結點間的引用 if (a == null) tail = b; else a.before = b; }複製程式碼在 Android 端的應用開發中，LRUCache 演算法（最近最少使用演算法）是很常見的，一種典型的用途就是用來在記憶體中快取 Bitmap，因為從 IO 流中讀取 Bitmap 的資源消耗較大，為了防止多次從磁碟中讀取某張圖片，所以通常會在記憶體中快取 Bitmap。但記憶體空間也是有限的，所以也不能每張圖片都進行快取，需要有選擇性地快取一定數量的圖片，LRUCache 就是最常見的快取方案之一
這裡利用 LinkedHashMap 可以按照元素使用順序進行排列的特點，來實現一個 LRUCache 策略的快取
public class LRUCache { private static class LRUCacheMap<K, V> extends LinkedHashMap<K, V> { //最大的快取數量 private final int maxCacheSize; public LRUCacheMap(int maxCacheSize) { super(16, 0.75F, true); this.maxCacheSize = maxCacheSize; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxCacheSize; } } public static void main(String[] args) { //最大快取數量是 5 LRUCacheMap<String, Integer> map = new LRUCacheMap<>(5); map.put("Java", 1); map.put("Jetpack", 2); map.put("Kotlin", 3); map.put("葉志陳", 4); map.put("位元組陣列", 5); map.put("leaveC", 6); System.out.println(); Set<String> keySet = map.keySet(); //輸出結果是：Jetpack Kotlin 葉志陳 位元組陣列 leaveC keySet.forEach(key -> System.out.print(key + " ")); //獲取連結串列的頭結點的值，使之移動到連結串列尾部 map.get("Jetpack"); System.out.println(); keySet = map.keySet(); //輸出結果是：Kotlin 葉志陳 位元組陣列 leaveC Jetpack keySet.forEach(key -> System.out.print(key + " ")); //向連結串列新增元素 map.put("Dart", 5); System.out.println(); //輸出結果是：葉志陳 位元組陣列 leaveC Jetpack Dart keySet.forEach(key -> System.out.print(key + " ")); }}複製程式碼HashSet 實現了 Set 介面，不允許插入重複的元素，允許包含 null 元素，且不保證元素的迭代順序，原始碼十分簡單，去掉註釋後不到兩百行，因為其底層也是透過 HashMap 來實現的，看了上面關於 HashMap 原始碼的解析後再來看 HashSet 就會有一種“不過如此”的感覺了
向 HashSet 新增的值都會被轉換為一個鍵值對，key 即外部傳入的值，value 則由 HashSet 來提供。如果 HashMap 中存在某個 key 值與外部傳入的值相等（hashCode() 方法返回值相等， equals() 方法也返回 true），那麼待新增的鍵值對的 value 會覆蓋原有資料，但 key 不會改變，即如果向 HashSet 新增一個已存在的元素時，並不會被存到 HashMap 中，從而實現了 HashSet 元素不重複的特性
在此就直接貼出原始碼了
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{ static final long serialVersionUID = -5024744406713321676L; //HashSet 底層用 HashMap 來存放資料 //Key 值由外部傳入，Value 則由 HashSet 內部來維護 private transient HashMap<E,Object> map; //HashMap 中所有鍵值對都共享同一個值 //即所有存入 HashMap 的鍵值對都是使用這個物件作為值 private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<>(); } //使用預設的裝載因子，並以此來計算 HashMap 的初始化大小 //+1 是為了彌補精度損失 public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } //此建構函式為包訪問許可權，只用於支援 LinkedHashSet HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } //將對 HashSet 的迭代轉換為對 HashMap 的 Key 值的迭代 public Iterator<E> iterator() { return map.keySet().iterator(); } public int size() { return map.size(); } public boolean isEmpty() { return map.isEmpty(); } public boolean contains(Object o) { return map.containsKey(o); } //如果 HashMap 中不包含 key 是 e 的鍵值對，則新增該元素並返回 true //如果包含則只會覆蓋 value 而不會影響 key，同時返回 false //從而實現 HashSet key 不重複的特性 public boolean add(E e) { return map.put(e, PRESENT)==null; } public boolean remove(Object o) { return map.remove(o)==PRESENT; } public void clear() { map.clear(); }}複製程式碼LinkedHashSet 其內部原始碼十分簡單，簡單到只有幾十行程式碼，從其名字就可以猜出它是 HashSet 的子類，並且是依靠連結串列來實現有序的 HashSet
HashSet 為 LinkedHashSet 預留了一個建構函式，其 dummy 引數並沒有實際意義，只是為了和其它建構函式區分開。其它建構函式會將 map 變數初始化為 HashMap 型別變數，特意預留的建構函式則是會初始化為 LinkedHashMap 型別變數，從而透過 LinkedHashMap 內部的雙向連結串列來實現 LinkedHashSet 自身存取有序，元素唯一的特性
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { private transient HashMap<E,Object> map; HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }}public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2851667679971038690L; public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); } public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } //使用預設的初始容量以及裝載因子 public LinkedHashSet() { super(16, .75f, true); } public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); } @Override public Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED); }}複製程式碼整理了一套大廠Android崗高階面試題資料，有需要的朋友可以 點贊+評論 後，後臺私信我獲取！