[TOC] ## HashSet 　　前面已經說過 HashSet 是對 HashMap 的簡單包裝，對 HashSet 的函數調用都會轉換成合適的 HashMap 方法，因此 HashSet 的實現非常簡單，只有不到 300 行代碼（適配器模式）。這里不再贅述。 ~~~java //HashSet是對HashMap的簡單包裝 public class HashSet<E> { ...... private transient HashMap<E,Object> map;//HashSet里面有一個HashMap // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<>(); } ...... public boolean add(E e) {//簡單的方法轉換 return map.put(e, PRESENT)==null; } ...... } ~~~ ### 1\. 成員變量 首先了解下`HashSet`的成員變量: ~~~java private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); ~~~ 發現主要就兩個變量: * `map`：用于存放最終數據的。 * `PRESENT`：是所有寫入 map 的`value`值。 ### 2\. 構造函數 ~~~java public HashSet() { map = new HashMap<>(); } public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } ~~~ 構造函數很簡單，利用了`HashMap`初始化了`map`。 ### 3\. add() ~~~java public boolean add(E e) { return map.put(e, PRESENT)==null; } ~~~ 比較關鍵的就是這個`add()`方法。 可以看出它是將存放的對象當做了`HashMap`的健，`value`都是相同的`PRESENT`。由于`HashMap`的`key`是不能重復的，所以每當有重復的值寫入到`HashSet`時，`value`會被覆蓋，但`key`不會收到影響，這樣就保證了`HashSet`中只能存放不重復的元素。 ### 4\. 總結 `HashSet`的原理比較簡單，幾乎全部借助于`HashMap`來實現的。 所以`HashMap`會出現的問題`HashSet`依然不能避免。 ## LinkedHashSet and LinkedHashMap ### 1\. 概覽 　　如果你已看過前面關于 HashSet 和 HashMap，的講解，一定能夠想到本文將要講解的 LinkedHashSet 和 LinkedHashMap 其實也是一回事。 LinkedHashSet 和 LinkedHashMap 在 Java 里也有著相同的實現，前者僅僅是對后者做了一層包裝，也就是說 LinkedHashSet 里面有一個 LinkedHashMap（**適配器模式**）。因此本文將重點分析 LinkedHashMap。 　　LinkedHashMap 實現了 Map 接口，即允許放入 key 為 null 的元素，也允許插入 value 為 null 的元素。從名字上可以看出該容器是 LinkedList 和 HashMap 的混合體，也就是說它同時滿足 HashMap 和 LinkedList 的某些特性。**可將 LinkedHashMap 看作采用 LinkedList 增強的 HashMap。** :-:  事實上 LinkedHashMap 是 HashMap 的直接子類，**二者唯一的區別是 LinkedHashMap 在 HashMap 的基礎上，采用雙向鏈表（doubly-linked list）的形式將所有 entry 連接起來，這樣是為保證元素的迭代順序跟插入順序相同**。上圖給出了 LinkedHashMap 的結構圖，主體部分跟 HashMap 完全一樣，多了`header`指向雙向鏈表的頭部（是一個啞元），**該雙向鏈表的迭代順序就是 entry 的插入順序**。 除了可以保迭代歷順序，這種結構還有一個好處：**迭代 LinkedHashMap 時不需要像 HashMap 那樣遍歷整個table，而只需要直接遍歷 header 指向的雙向鏈表即可**，也就是說 LinkedHashMap 的迭代時間就只跟`entry`的個數相關，而跟`table`的大小無關。 有兩個參數可以影響 LinkedHashMap 的性能：**初始容量**（inital capacity）和**負載系數**（load factor）。初始容量指定了初始`table`的大小，負載系數用來指定自動擴容的臨界值。當`entry`的數量超過`capacity*load_factor`時，容器將自動擴容并重新哈希。對于插入元素較多的場景，將初始容量設大可以減少重新哈希的次數。 將對象放入到 LinkedHashMap 或 LinkedHashSet 中時，有兩個方法需要特別關心：`hashCode()`和`equals()`。**hashCode() 方法決定了對象會被放到哪個 bucket 里，當多個對象的哈希值沖突時，equals() 方法決定了這些對象是否是“同一個對象”**。所以，如果要將自定義的對象放入到`LinkedHashMap`或`LinkedHashSet`中，需要*@Override*`hashCode()`和`equals()`方法。 通過如下方式可以得到一個跟源 Map 迭代順序 一樣的 LinkedHashMap： ~~~java void foo(Map m) { Map copy = new LinkedHashMap(m); ... } ~~~ 出于性能原因，LinkedHashMap 是非同步的（not synchronized），如果需要在多線程環境使用，需要程序員手動同步；或者通過如下方式將 LinkedHashMap 包裝成（wrapped）同步的： `Map m = Collections.synchronizedMap(new LinkedHashMap(...));` ### 2\. get() `get(Object key)`方法根據指定的`key`值返回對應的`value`。該方法跟`HashMap.get()`方法的流程幾乎完全一樣，讀者可自行[參考前文](https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/6-HashSet%20and%20HashMap.md#get)，這里不再贅述。 ### 3\. put() `put(K key, V value)`方法是將指定的`key, value`對添加到`map`里。該方法首先會對`map`做一次查找，看是否包含該元組，如果已經包含則直接返回，查找過程類似于`get()`方法；如果沒有找到，則會通過`addEntry(int hash, K key, V value, int bucketIndex)`方法插入新的`entry`。 注意，這里的**插入有兩重含義**： > 1. 從 table 的角度看，新的 entry 需要插入到對應的 bucket 里，當有哈希沖突時，采用頭插法將新的 entry 插入到沖突鏈表的頭部。 > 2. 從 header 的角度看，新的 entry 需要插入到雙向鏈表的尾部。 :-:  `addEntry()`代碼如下： ~~~java // LinkedHashMap.addEntry() void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);// 自動擴容，并重新哈希 hash = (null != key) ? hash(key) : 0; bucketIndex = hash & (table.length-1);// hash%table.length } // 1.在沖突鏈表頭部插入新的entry HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; // 2.在雙向鏈表的尾部插入新的entry e.addBefore(header); size++; } ~~~ 上述代碼中用到了`addBefore()`方 法將新`entry e`插入到雙向鏈表頭引用`header`的前面，這樣`e`就成為雙向鏈表中的最后一個元素。`addBefore()`的代碼如下： ~~~java // LinkedHashMap.Entry.addBefor()，將this插入到existingEntry的前面 private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; } ~~~ 上述代碼只是簡單修改相關`entry`的引用而已。 ### 4\. remove() `remove(Object key)`的作用是刪除`key`值對應的`entry`，該方法的具體邏輯是在`removeEntryForKey(Object key)`里實現的。`removeEntryForKey()`方法會首先找到`key`值對應的`entry`，然后刪除該`entry`（修改鏈表的相應引用）。查找過程跟`get()`方法類似。 注意，這里的**刪除也有兩重含義**： > 1. 從`table`的角度看，需要將該`entry`從對應的`bucket`里刪除，如果對應的沖突鏈表不空，需要修改沖突鏈表的相應引用。 > 2. 從`header`的角度來看，需要將該`entry`從雙向鏈表中刪除，同時修改鏈表中前面以及后面元素的相應引用。 [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/LinkedList_remove.png) `removeEntryForKey()`對應的代碼如下： ~~~js // LinkedHashMap.removeEntryForKey()，刪除key值對應的entry final Entry<K,V> removeEntryForKey(Object key) { ...... int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length);// hash&(table.length-1) Entry<K,V> prev = table[i];// 得到沖突鏈表 Entry<K,V> e = prev; while (e != null) {// 遍歷沖突鏈表 Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要刪除的entry modCount++; size--; // 1. 將e從對應bucket的沖突鏈表中刪除 if (prev == e) table[i] = next; else prev.next = next; // 2. 將e從雙向鏈表中刪除 e.before.after = e.after; e.after.before = e.before; return e; } prev = e; e = next; } return e; } ~~~ ### 5\. LinkedHashSet 前面已經說過*LinkedHashSet*是對*LinkedHashMap*的簡單包裝，對*LinkedHashSet*的函數調用都會轉換成合適的*LinkedHashMap*方法，因此*LinkedHashSet*的實現非常簡單，這里不再贅述。 ~~~java public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { ...... // LinkedHashSet里面有一個LinkedHashMap public LinkedHashSet(int initialCapacity, float loadFactor) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } ...... public boolean add(E e) {//簡單的方法轉換 return map.put(e, PRESENT)==null; } ...... } ~~~ ### 6\. LinkedHashMap經典用法 LinkedHashMap 除了可以保證迭代順序外，還有一個非常有用的用法：可以輕松實現一個采用了FIFO替換策略的緩存。具體說來，LinkedHashMap 有一個子類方法`protected boolean removeEldestEntry(Map.Entry<K,V> eldest)`，該方法的作用是告訴 Map 是否要刪除“最老”的 Entry，所謂最老就是當前 Map 中最早插入的 Entry，如果該方法返回 true，最老的那個元素就會被刪除。在每次插入新元素的之后 LinkedHashMap 會自動詢問 removeEldestEntry() 是否要刪除最老的元素。這樣只需要在子類中重載該方法，當元素個數超過一定數量時讓 removeEldestEntry() 返回 true，就能夠實現一個固定大小的 FIFO 策略的緩存。示例代碼如下： ~~~java /** 一個固定大小的FIFO替換策略的緩存 */ class FIFOCache<K, V> extends LinkedHashMap<K, V>{ private final int cacheSize; public FIFOCache(int cacheSize){ this.cacheSize = cacheSize; } // 當Entry個數超過cacheSize時，刪除最老的Entry @Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return size() > cacheSize; } } ~~~