文章目錄

• Pre
• 概述
• 數據結構
• 類繼承關系
• 構造函數
• 方法
• • get()
  • put()
  • remove()
• LinkedHashSet
• 使用案例 - FIFO策略緩存

---

Pre

Java Review - HashMap & HashSet 源碼解讀 中我們講了HashSet和HashMap 。 那同樣的套路 ， LinkedHashSet和LinkedHashMap在Java里也有著相同的實現，LinkedHashSet僅僅是對LinkedHashMap做了一層包裝，也就是說LinkedHashSet里面有一個LinkedHashMap(適配器模式)。

故我們還是重點分析LinkedHashMap。

概述

• LinkedHashMap實現了Map接口，即允許放入key為null的元素，也允許插入value為null的元素。

• 從名字上可以看出該容器是linked list和HashMap的混合體，也就是說它同時滿足HashMap和linked list的某些特性。可將LinkedHashMap看作采用linked list增強的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中，需要重寫 hashCode()和equals()方法

• 出于性能原因，LinkedHashMap是非同步的(not synchronized)，如果需要在多線程環境使用，需要程序員手動同步；或者通過如下方式將LinkedHashMap包裝成(wrapped)同步的:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

通過如下方式可以得到一個跟源Map 迭代順序一樣的LinkedHashMap: void

foo(Map m) {Map copy = new LinkedHashMap(m);... }

---

類繼承關系

---

構造函數

/*** Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance* with the specified initial capacity and load factor.** @param initialCapacity the initial capacity* @param loadFactor the load factor* @throws IllegalArgumentException if the initial capacity is negative* or the load factor is nonpositive*/public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;}/*** Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance* with the specified initial capacity and a default load factor (0.75).** @param initialCapacity the initial capacity* @throws IllegalArgumentException if the initial capacity is negative*/public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;}/*** Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance* with the default initial capacity (16) and load factor (0.75).*/public LinkedHashMap() {super();accessOrder = false;}/*** Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with* the same mappings as the specified map. The <tt>LinkedHashMap</tt>* instance is created with a default load factor (0.75) and an initial* capacity sufficient to hold the mappings in the specified map.** @param m the map whose mappings are to be placed in this map* @throws NullPointerException if the specified map is null*/public LinkedHashMap(Map<? extends K, ? extends V> m) {super();accessOrder = false;putMapEntries(m, false);}/*** Constructs an empty <tt>LinkedHashMap</tt> instance with the* specified initial capacity, load factor and ordering mode.** @param initialCapacity the initial capacity* @param loadFactor the load factor* @param accessOrder the ordering mode - <tt>true</tt> for* access-order, <tt>false</tt> for insertion-order* @throws IllegalArgumentException if the initial capacity is negative* or the load factor is nonpositive*/public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}

---

方法

get()

get(Object key)方法根據指定的key值返回對應的value。該方法跟HashMap.get()方法的流程幾乎完全一樣.

參考 Java Review - HashMap & HashSet 源碼解讀

---

put()

put(K key, V value)方法是將指定的key, value對添加到map里。

• 該方法首先會對map做一次查找，看是否包含該元組，如果已經包含則直接返回，查找過程類似于get()方法；
• 如果沒有找到，則會通過addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。

這里的插入有兩重含義:

從table的角度看，新的entry需要插入到對應的bucket里，當有哈希沖突時，采用頭插法將新的entry插入到沖突鏈表的頭部。

從header的角度看，新的entry需要插入到雙向鏈表的尾部。

// 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.在沖突鏈表頭部插入新的entryHashMap.Entry<K,V> old = table[bucketIndex];Entry<K,V> e = new Entry<>(hash, key, value, old);table[bucketIndex] = e;// 2.在雙向鏈表的尾部插入新的entrye.addBefore(header);size++; }

上述代碼中用到了addBefore()方法將新entry e插入到雙向鏈表頭引用header的前面，這樣e就成為雙向鏈表中的最后一個元素。addBefore()的代碼如下:

// LinkedHashMap.Entry.addBefor()，將this插入到existingEntry的前面 private void addBefore(Entry<K,V> existingEntry) {after = existingEntry;before = existingEntry.before;before.after = this;after.before = this; }

上述代碼只是簡單修改相關entry的引用而已。

---

remove()

• remove(Object key)的作用是刪除key值對應的entry，該方法的具體邏輯是在removeEntryForKey(Object key)里實現的。

• removeEntryForKey()方法會首先找到key值對應的entry，然后刪除該entry(修改鏈表的相應引用)。查找過程跟get()方法類似。

這里的刪除也有兩重含義:

從table的角度看，需要將該entry從對應的bucket里刪除，如果對應的沖突鏈表不空，需要修改沖突鏈表的相應引用。

從header的角度來看，需要將該entry從雙向鏈表中刪除，同時修改鏈表中前面以及后面元素的相應引用。

// 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)))) {// 找到要刪除的entrymodCount++; 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; }

---

LinkedHashSet

LinkedHashSet是對LinkedHashMap的簡單包裝，對LinkedHashSet的函數調用都會轉換成合適的LinkedHashMap方法，因此LinkedHashSet的實現非常簡單

public class LinkedHashSet<E>extends HashSet<E>implements Set<E>, Cloneable, java.io.Serializable {......// LinkedHashSet里面有一個LinkedHashMappublic LinkedHashSet(int initialCapacity, float loadFactor) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}......public boolean add(E e) {//簡單的方法轉換return map.put(e, PRESENT)==null;}...... }

---

使用案例 - FIFO策略緩存

LinkedHashMap除了可以保證迭代順序外，還有一個非常有用的用法: 可以輕松實現一個采用了FIFO替換策略的緩存。

具體說來，LinkedHashMap有一個子類方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest)，該方法的作用是告訴Map是否要刪除“最老”的Entry，所謂最老就是當前Map中最早插入的Entry，如果該方法返回true，最老的那個元素就會被刪除。

在每次插入新元素的之后LinkedHashMap會自動詢問removeEldestEntry()是否要刪除最老的元素。這樣只需要在子類中重載該方法，當元素個數超過一定數量時讓removeEldestEntry()返回true，就能夠實現一個固定大小的FIFO策略的緩存。

/** 一個固定大小的FIFO替換策略的緩存 */ class FIFOCache<K, V> extends LinkedHashMap<K, V>{private final int cacheSize;public FIFOCache(int cacheSize){this.cacheSize = cacheSize;}// 當Entry個數超過cacheSize時，刪除最老的Entry@Overrideprotected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return size() > cacheSize;} }

總結

以上是生活随笔為你收集整理的Java Review - LinkedHashMap LinkedHashSet 源码解读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。