1. 概述

眾所周知，HashMap 提供的訪問(wèn)，是無(wú)序的。而在一些業(yè)務(wù)場(chǎng)景下，我們希望能夠提供有序訪問(wèn)的 HashMap 。那么此時(shí)，我們就有兩種選擇：

• TreeMap ：按照 key 的順序。
• LinkedHashMap ：按照 key 的插入和訪問(wèn)的順序。

LinkedHashMap ，在 HashMap 的基礎(chǔ)之上，提供了順序訪問(wèn)的特性。而這里的順序，包括兩種：

• 按照 key-value 的插入順序進(jìn)行訪問(wèn)。關(guān)于這一點(diǎn)，相信大多數(shù)人都知道。

• 按照 key-value 的訪問(wèn)順序進(jìn)行訪問(wèn)。通過(guò)這個(gè)特性，我們實(shí)現(xiàn)基于 LRU 算法的緩存。

  面試中，有些面試官會(huì)喜歡問(wèn)你，如何實(shí)現(xiàn)一個(gè) LRU 的緩存。

實(shí)際上，LinkedHashMap 可以理解成是 LinkedList + HashMap 的組合。為什么這么說(shuō)呢？讓我們帶著這樣的疑問(wèn)，一起往下看。

2. 類圖

LinkedHashMap 實(shí)現(xiàn)的接口、繼承的類，如下圖所示：類圖

• 實(shí)現(xiàn) Map 接口。
• 繼承 HashMap 類。

?? 很簡(jiǎn)單，很粗暴。嘿嘿~

因?yàn)?LinkedHashMap 繼承自 HashMap 類，所以它的代碼并不多，不到 500 行。

3. 屬性

在開(kāi)始看 LinkedHashMap 的屬性之前，我們先來(lái)看在 《精盡 JDK 源碼解析 —— 集合（三）哈希表 HashMap》 看到的 HashMap 的 Node 子類圖：Node 類圖

在圖中，我們可以看到 LinkedHashMap 實(shí)現(xiàn)了自定義的節(jié)點(diǎn) Entry ，一個(gè)支持指向前后節(jié)點(diǎn)的 Node 子類。代碼如下：

// LinkedHashMap.java

static class Entry<K,V> extends HashMap.Node<K,V> {

    Entry<K,V> before, // 前一個(gè)節(jié)點(diǎn)
            after; // 后一個(gè)節(jié)點(diǎn)

    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }

}

• before 屬性，指向前一個(gè)節(jié)點(diǎn)。after 屬性，指向后一個(gè)節(jié)點(diǎn)。
• 通過(guò) before + after 屬性，我們就可以形成一個(gè)以 Entry 為節(jié)點(diǎn)的鏈表。

既然 LinkedHashMap 是 LinkedList + HashMap 的組合，那么必然就會(huì)有頭尾節(jié)點(diǎn)兩兄弟。所以屬性如下：

// LinkedHashMap.java

/**
 * 頭節(jié)點(diǎn)。
 *
 * 越老的節(jié)點(diǎn)，放在越前面。所以頭節(jié)點(diǎn)，指向鏈表的開(kāi)頭
 *
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * 尾節(jié)點(diǎn)
 *
 * 越新的節(jié)點(diǎn)，放在越后面。所以尾節(jié)點(diǎn)，指向鏈表的結(jié)尾
 *
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * 是否按照訪問(wèn)的順序。
 *
 * true ：按照 key-value 的訪問(wèn)順序進(jìn)行訪問(wèn)。
 * false ：按照 key-value 的插入順序進(jìn)行訪問(wèn)。
 *
 * The iteration ordering method for this linked hash map: {@code true}
 * for access-order, {@code false} for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;

• 仔細(xì)看下每個(gè)屬性的注釋。

• head + tail 屬性，形成 LinkedHashMap 的雙向鏈表。而訪問(wèn)的順序，就是 head => tail 的過(guò)程。

• accessOrder
  

  屬性，決定了 LinkedHashMap 的順序。也就是說(shuō):

  • true 時(shí)，當(dāng) Entry 節(jié)點(diǎn)被訪問(wèn)時(shí)，放置到鏈表的結(jié)尾，被 tail 指向。
  • false 時(shí)，當(dāng) Entry 節(jié)點(diǎn)被添加時(shí)，放置到鏈表的結(jié)尾，被 tail 指向。如果插入的 key 對(duì)應(yīng)的 Entry 節(jié)點(diǎn)已經(jīng)存在，也會(huì)被放到結(jié)尾。

總結(jié)來(lái)說(shuō)，就是如下一張圖：

FROM 《Working of LinkedHashMap》

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-lY07rdsD-1680959944490)(http://www.thejavageek.com/wp-content/uploads/2016/06/SecondObjectInserted.png)]LinkedHashMap 結(jié)構(gòu)圖

4. 構(gòu)造方法

LinkedHashMap 一共有 5 個(gè)構(gòu)造方法，其中四個(gè)和 HashMap 相同，只是多初始化 accessOrder = false 。所以，默認(rèn)使用插入順序進(jìn)行訪問(wèn)。

另外一個(gè) #LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 構(gòu)造方法，允許自定義 accessOrder 屬性。代碼如下：

// LinkedHashMap.java

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

5. 創(chuàng)建節(jié)點(diǎn)

在插入 key-value 鍵值對(duì)時(shí)，例如說(shuō) #put(K key, V value) 方法，如果不存在對(duì)應(yīng)的節(jié)點(diǎn)，則會(huì)調(diào)用 #newNode(int hash, K key, V value, Node<K,V> e) 方法，創(chuàng)建節(jié)點(diǎn)。

因?yàn)?LinkedHashMap 自定義了 Entry 節(jié)點(diǎn)，所以必然需要重寫(xiě)該方法。代碼如下：

// LinkedHashMap.java

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // <1> 創(chuàng)建 Entry 節(jié)點(diǎn)
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<>(hash, key, value, e);
    // <2> 添加到結(jié)尾
    linkNodeLast(p);
    // 返回
    return p;
}

• <1> 處，創(chuàng)建 Entry 節(jié)點(diǎn)。雖然此處傳入 e 作為 Entry.next 屬性，指向下一個(gè)節(jié)點(diǎn)。但是實(shí)際上，#put(K key, V value) 方法中，傳入的 e = null 。

• <2> 處，調(diào)用 #linkNodeLast(LinkedHashMap.Entry<K,V> p) 方法，添加到結(jié)尾。代碼如下：

  // LinkedHashMap.java
  
  private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
      // 記錄原尾節(jié)點(diǎn)到 last 中
      LinkedHashMap.Entry<K,V> last = tail;
      // 設(shè)置 tail 指向 p ，變更新的尾節(jié)點(diǎn)
      tail = p;
      // 如果原尾節(jié)點(diǎn) last 為空，說(shuō)明 head 也為空，所以 head 也指向 p
      if (last == null)
          head = p;
      // last <=> p ，相互指向
      else {
          p.before = last;
          last.after = p;
      }
  }
  

  • 這樣，符合越新的節(jié)點(diǎn)，放到鏈表的越后面。

6. 節(jié)點(diǎn)操作回調(diào)

在 HashMap 的讀取、添加、刪除時(shí)，分別提供了 #afterNodeAccess(Node<K,V> e)、#afterNodeInsertion(boolean evict)、#afterNodeRemoval(Node<K,V> e) 回調(diào)方法。這樣，LinkedHashMap 可以通過(guò)它們實(shí)現(xiàn)自定義拓展邏輯。

6.1 afterNodeAccess

在 accessOrder 屬性為 true 時(shí)，當(dāng) Entry 節(jié)點(diǎn)被訪問(wèn)時(shí)，放置到鏈表的結(jié)尾，被 tail 指向。所以 #afterNodeAccess(Node<K,V> e) 方法的代碼如下：

// LinkedHashMap.java

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // accessOrder 判斷必須是滿足按訪問(wèn)順序。
    // (last = tail) != e 將 tail 賦值給 last ，并且判斷是否 e 已經(jīng)是隊(duì)尾。如果是隊(duì)尾，就不用處理了。
    if (accessOrder && (last = tail) != e) {
        // 將 e 賦值給 p 【因?yàn)橐?Node 類型轉(zhuǎn)換成 Entry 類型】
        // 同時(shí) b、a 分別是 e 的前后節(jié)點(diǎn)
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 第一步，將 p 從鏈表中移除
        p.after = null;
        // 處理 b 的下一個(gè)節(jié)點(diǎn)指向 a
        if (b == null)
            head = a;
        else
            b.after = a;
        // 處理 a 的前一個(gè)節(jié)點(diǎn)指向 b
        if (a != null)
            a.before = b;
        else
            last = b;
        // 第二步，將 p 添加到鏈表的尾巴。實(shí)際這里的代碼，和 linkNodeLast 是一致的。
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        // tail 指向 p ，實(shí)際就是 e 。
        tail = p;
        // 增加修改次數(shù)
        ++modCount;
    }
}

• 代碼已經(jīng)添加詳細(xì)的注釋，胖友認(rèn)真看看噢。
• 鏈表的操作看起來(lái)比較繁瑣，實(shí)際一共分成兩步：1）第一步，將 p 從鏈表中移除；2）將 p 添加到鏈表的尾巴。

因?yàn)?HashMap 提供的 #get(Object key) 和 #getOrDefault(Object key, V defaultValue) 方法，并未調(diào)用 #afterNodeAccess(Node<K,V> e) 方法，這在按照讀取順序訪問(wèn)顯然不行，所以 LinkedHashMap 重寫(xiě)這兩方法的代碼，如下：

// LinkedHashMap.java

public V get(Object key) {
    // 獲得 key 對(duì)應(yīng)的 Node
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果訪問(wèn)到，回調(diào)節(jié)點(diǎn)被訪問(wèn)
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

public V getOrDefault(Object key, V defaultValue) {
    // 獲得 key 對(duì)應(yīng)的 Node
    Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
    // 如果訪問(wèn)到，回調(diào)節(jié)點(diǎn)被訪問(wèn)
    if (accessOrder)
       afterNodeAccess(e);
   return e.value;
}

6.2 afterNodeInsertion

在開(kāi)始看 #afterNodeInsertion(boolean evict) 方法之前，我們先來(lái)看看如何基于 LinkedHashMap 實(shí)現(xiàn) LRU 算法的緩存。代碼如下：

class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int CACHE_SIZE;

    /**
     * 傳遞進(jìn)來(lái)最多能緩存多少數(shù)據(jù)
     *
     * @param cacheSize 緩存大小
     */
    public LRUCache(int cacheSize) {
        // true 表示讓 LinkedHashMap 按照訪問(wèn)順序來(lái)進(jìn)行排序，最近訪問(wèn)的放在頭部，最老訪問(wèn)的放在尾部。
        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
        CACHE_SIZE = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 當(dāng) map 中的數(shù)據(jù)量大于指定的緩存?zhèn)€數(shù)的時(shí)候，就自動(dòng)刪除最老的數(shù)據(jù)。
        return size() > CACHE_SIZE;
    }

}

為什么能夠這么實(shí)現(xiàn)呢？我們?cè)?#afterNodeInsertion(boolean evict) 方法中來(lái)理解。代碼如下：

// LinkedHashMap.java

// evict 翻譯為驅(qū)逐，表示是否允許移除元素
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // first = head 記錄當(dāng)前頭節(jié)點(diǎn)。因?yàn)橐瞥龔念^開(kāi)始，最老
    // <1> removeEldestEntry(first) 判斷是否滿足移除最老節(jié)點(diǎn)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        // <2> 移除指定節(jié)點(diǎn)
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

• <1> 處，調(diào)用 #removeEldestEntry(Map.Entry<K,V> eldest) 方法，判斷是否移除最老節(jié)點(diǎn)。代碼如下：

  // LinkedHashMap.java
  
  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
      return false;
  }
  

  • 默認(rèn)情況下，都不移除最老的節(jié)點(diǎn)。所以在上述的 LRU 緩存的示例，重寫(xiě)了該方法，判斷 LinkedHashMap 是否超過(guò)緩存最大大小。如果是，則移除最老的節(jié)點(diǎn)。

• <2> 處，如果滿足條件，則調(diào)用 #removeNode(...) 方法，移除最老的節(jié)點(diǎn)。

?? 這樣，是不是很容易理解基于 LinkedHashMap 實(shí)現(xiàn) LRU 算法的緩存。

6.3 afterNodeRemoval

在節(jié)點(diǎn)被移除時(shí)，LinkedHashMap 需要將節(jié)點(diǎn)也從鏈表中移除，所以重寫(xiě) #afterNodeRemoval(Node<K,V> e) 方法，實(shí)現(xiàn)該邏輯。代碼如下：

// LinkedHashMap.java

void afterNodeRemoval(Node<K,V> e) { // unlink
    // 將 e 賦值給 p 【因?yàn)橐?Node 類型轉(zhuǎn)換成 Entry 類型】
    // 同時(shí) b、a 分別是 e 的前后節(jié)點(diǎn)
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 將 p 從鏈表中移除
    p.before = p.after = null;
    // 處理 b 的下一個(gè)節(jié)點(diǎn)指向 a
    if (b == null)
        head = a;
    else
        b.after = a;
    // 處理 a 的前一個(gè)節(jié)點(diǎn)指向 b
    if (a == null)
        tail = b;
    else
        a.before = b;
}

7. 轉(zhuǎn)換成數(shù)組

因?yàn)?LinkedHashMap 需要滿足按順序訪問(wèn)，所以需要重寫(xiě) HashMap 提供的好多方法，例如說(shuō)本小節(jié)我們看到的幾個(gè)。

#keysToArray(T[] a) 方法，轉(zhuǎn)換出 key 數(shù)組順序返回。代碼如下：

// LinkedHashMap.java

@Override
final <T> T[] keysToArray(T[] a) {
    Object[] r = a;
    int idx = 0;
    // 通過(guò) head 順序遍歷，從頭到尾
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        r[idx++] = e.key;
    }
    return a;
}

• 要小心噢，必須保證 a 放得下 LinkedHashMap 所有的元素。

#valuesToArray(T[] a) 方法，轉(zhuǎn)換出 value 數(shù)組順序返回。代碼如下：

// LinkedHashMap.java

@Override
final <T> T[] valuesToArray(T[] a) {
    Object[] r = a;
    int idx = 0;
    // 通過(guò) head 順序遍歷，從頭到尾
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        r[idx++] = e.value;
    }
    return a;
}

艿艿：看到此處，胖友基本可以結(jié)束本文落。

8. 轉(zhuǎn)換成 Set/Collection

#keySet() 方法，獲得 key Set 。代碼如下：

// LinkedHashMap.java

public Set<K> keySet() {
    // 獲得 keySet 緩存
    Set<K> ks = keySet;
    // 如果不存在，則進(jìn)行創(chuàng)建
    if (ks == null) {
        ks = new LinkedKeySet(); // LinkedKeySet 是 LinkedHashMap 自定義的
        keySet = ks;
    }
    return ks;
}

• 其中， LinkedKeySet 是 LinkedHashMap 自定義的 Set 實(shí)現(xiàn)類。代碼如下：

  // LinkedHashMap.java
  
  final class LinkedKeySet extends AbstractSet<K> {
  
      public final int size()                 { return size; }
      public final void clear()               { LinkedHashMap.this.clear(); }
      public final Iterator<K> iterator() {
          return new LinkedKeyIterator(); // <X>
      }
      public final boolean contains(Object o) { return containsKey(o); }
      public final boolean remove(Object key) {
          return removeNode(hash(key), key, null, false, true) != null;
      }
      public final Spliterator<K> spliterator()  {
          return Spliterators.spliterator(this, Spliterator.SIZED |
                                          Spliterator.ORDERED |
                                          Spliterator.DISTINCT);
      }
  
      public Object[] toArray() {
          return keysToArray(new Object[size]);
      }
  
      public <T> T[] toArray(T[] a) {
          return keysToArray(prepareArray(a));
      }
  
      public final void forEach(Consumer<? super K> action) {
          if (action == null)
              throw new NullPointerException();
          int mc = modCount;
          for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
              action.accept(e.key);
          if (modCount != mc)
              throw new ConcurrentModificationException();
      }
  }
  

  • 其內(nèi)部，調(diào)用的都是 LinkedHashMap 提供的方法。

#values() 方法，獲得 value Collection 。代碼如下：

// LinkedHashMap.java

public Collection<V> values() {
    // 獲得 values 緩存
    Collection<V> vs = values;
    // 如果不存在，則進(jìn)行創(chuàng)建
    if (vs == null) {
        vs = new LinkedValues(); // LinkedValues 是 LinkedHashMap 自定義的
        values = vs;
    }
    return vs;
}

• 其中， LinkedValues 是 LinkedHashMap 自定義的 Collection 實(shí)現(xiàn)類。代碼如下：

  // LinkedHashMap.java
  
  final class LinkedValues extends AbstractCollection<V> {
      public final int size()                 { return size; }
      public final void clear()               { LinkedHashMap.this.clear(); }
      public final Iterator<V> iterator() {
          return new LinkedValueIterator(); // <X>
      }
      public final boolean contains(Object o) { return containsValue(o); }
      public final Spliterator<V> spliterator() {
          return Spliterators.spliterator(this, Spliterator.SIZED |
                                          Spliterator.ORDERED);
      }
  
      public Object[] toArray() {
          return valuesToArray(new Object[size]);
      }
  
      public <T> T[] toArray(T[] a) {
          return valuesToArray(prepareArray(a));
      }
  
      public final void forEach(Consumer<? super V> action) {
          if (action == null)
              throw new NullPointerException();
          int mc = modCount;
          for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
              action.accept(e.value);
          if (modCount != mc)
              throw new ConcurrentModificationException();
      }
  }
  

  • 其內(nèi)部，調(diào)用的都是 LinkedHashMap 提供的方法。

#entrySet() 方法，獲得 key-value Set 。代碼如下：

// LinkedHashMap.java

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    // LinkedEntrySet 是 LinkedHashMap 自定義的
    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}

• 其中， LinkedEntrySet 是 LinkedHashMap 自定義的 Set 實(shí)現(xiàn)類。代碼如下：

  // LinkedHashMap.java
  
  final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
      public final int size()                 { return size; }
      public final void clear()               { LinkedHashMap.this.clear(); }
      public final Iterator<Map.Entry<K,V>> iterator() {
          return new LinkedEntryIterator(); // <X>
      }
      public final boolean contains(Object o) {
          if (!(o instanceof Map.Entry))
              return false;
          Map.Entry<?,?> e = (Map.Entry<?,?>) o;
          Object key = e.getKey();
          Node<K,V> candidate = getNode(hash(key), key);
          return candidate != null && candidate.equals(e);
      }
      public final boolean remove(Object o) {
          if (o instanceof Map.Entry) {
              Map.Entry<?,?> e = (Map.Entry<?,?>) o;
              Object key = e.getKey();
              Object value = e.getValue();
              return removeNode(hash(key), key, value, true, true) != null;
          }
          return false;
      }
      public final Spliterator<Map.Entry<K,V>> spliterator() {
          return Spliterators.spliterator(this, Spliterator.SIZED |
                                          Spliterator.ORDERED |
                                          Spliterator.DISTINCT);
      }
      public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
          if (action == null)
              throw new NullPointerException();
          int mc = modCount;
          for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
              action.accept(e);
          if (modCount != mc)
              throw new ConcurrentModificationException();
      }
  }
  

  • 其內(nèi)部，調(diào)用的都是 LinkedHashMap 提供的方法。

在上面的代碼中，艿艿實(shí)際標(biāo)記了三處 <X> 標(biāo)記，分別是 LinkedKeyIterator、LinkedValueIterator、LinkedEntryIterator ，用于迭代遍歷 key、value、Entry 。而它們都繼承了 LinkedHashIterator 抽象類，代碼如下：

// LinkedHashMap.java

abstract class LinkedHashIterator {

    /**
     * 下一個(gè)節(jié)點(diǎn)
     */
    LinkedHashMap.Entry<K,V> next;
    /**
     * 當(dāng)前節(jié)點(diǎn)
     */
    LinkedHashMap.Entry<K,V> current;
    /**
     * 修改次數(shù)
     */
    int expectedModCount;

    LinkedHashIterator() {
        next = head;
        expectedModCount = modCount;
        current = null;
    }

    public final boolean hasNext() {
        return next != null;
    }

    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        // 如果發(fā)生了修改，拋出 ConcurrentModificationException 異常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // 如果 e 為空，說(shuō)明沒(méi)有下一個(gè)節(jié)點(diǎn)，則拋出 NoSuchElementException 異常
        if (e == null)
            throw new NoSuchElementException();
        // 遍歷到下一個(gè)節(jié)點(diǎn)
        current = e;
        next = e.after;
        return e;
    }

    public final void remove() {
        // 移除當(dāng)前節(jié)點(diǎn)
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        // 如果發(fā)生了修改，拋出 ConcurrentModificationException 異常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // 標(biāo)記 current 為空，因?yàn)楸灰瞥?        current = null;
        // 移除節(jié)點(diǎn)
        removeNode(p.hash, p.key, null, false, false);
        // 修改 expectedModCount 次數(shù)
        expectedModCount = modCount;
    }

}

final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {

    // key
    public final K next() { return nextNode().getKey(); }
}

final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {

    // value
    public final V next() { return nextNode().value; }
}

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {

    // Entry
    public final Map.Entry<K,V> next() { return nextNode(); }
}

9. 清空

#clear() 方法，清空 LinkedHashMap 。代碼如下：

// LinkedHashMap.java

public void clear() {
    // 清空
    super.clear();
    // 標(biāo)記 head 和 tail 為 null
    head = tail = null;
}

• 需要額外清空 head、tail 。

10. 其它方法

本小節(jié)，我們會(huì)羅列下其他 LinkedHashMap 重寫(xiě)的方法。當(dāng)然，可以選擇不看。

在序列化時(shí)，會(huì)調(diào)用到 #internalWriteEntries(java.io.ObjectOutputStream s) 方法，重寫(xiě)代碼如下：

// LinkedHashMap.java

void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
    // 通過(guò) head 順序遍歷，從頭到尾
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        // 寫(xiě)入 key
        s.writeObject(e.key);
        // 寫(xiě)入 value
        s.writeObject(e.value);
    }
}

在反序列化時(shí)，會(huì)調(diào)用 #reinitialize() 方法，重寫(xiě)代碼如下：

// LinkedHashMap.java

void reinitialize() {
    // 調(diào)用父方法，初始化
    super.reinitialize();
    // 標(biāo)記 head 和 tail 為 null
    head = tail = null;
}

查找值時(shí)，會(huì)調(diào)用 #containsValue(Object value) 方法，重寫(xiě)代碼如下：

// LinkedHashMap.java

public boolean containsValue(Object value) {
    // 通過(guò) head 順序遍歷，從頭到尾
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        // 判斷是否相等
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

666. 彩蛋

如下幾個(gè)方法，是 LinkedHashMap 重寫(xiě)和紅黑樹(shù)相關(guān)的幾個(gè)方法，胖友可以自己瞅瞅：

• #replacementNode(Node<K,V> p, Node<K,V> next)
• #newTreeNode(int hash, K key, V value, Node<K,V> next)
• #replacementTreeNode(Node<K,V> p, Node<K,V> next)
• #transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst)

下面，我們來(lái)對(duì) LinkedHashMap 做一個(gè)簡(jiǎn)單的小結(jié)：

• LinkedHashMap 是 HashMap 的子類，增加了

  順序

  訪問(wèn)的特性。

  • 【默認(rèn)】當(dāng) accessOrder = false 時(shí)，按照 key-value 的插入順序進(jìn)行訪問(wèn)。
  • 當(dāng) accessOrder = true 時(shí)，按照 key-value 的讀取順序進(jìn)行訪問(wèn)。

• LinkedHashMap 的順序特性，通過(guò)內(nèi)部的雙向鏈表實(shí)現(xiàn)，所以我們把它看成是 LinkedList + LinkedHashMap 的組合。

• LinkedHashMap 通過(guò)重寫(xiě) HashMap 提供的回調(diào)方法，從而實(shí)現(xiàn)其對(duì)順序的特性的處理。同時(shí)，因?yàn)?LinkedHashMap 的順序特性，需要重寫(xiě) #keysToArray(T[] a) 等遍歷相關(guān)的方法。

• LinkedHashMap 可以方便實(shí)現(xiàn) LRU 算法的緩存，文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-418372.html

到了這里，關(guān)于【LinkedHashMap】| 深度剝析Java SE 源碼合集Ⅴ的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！