Java集合系列之LinkedHashMap源碼分析

更新時間：2018年02月27日 14:50:36 作者：勞夫子

這篇文章主要為大家詳細介紹了Java集合系列之LinkedHashMap源碼分析，具有一定的參考價值，感興趣的小伙伴們可以參考一下

這篇文章我們開始分析LinkedHashMap的源碼，LinkedHashMap繼承了HashMap，也就是說LinkedHashMap是在HashMap的基礎上擴展而來的，因此在看LinkedHashMap源碼之前，讀者有必要先去了解HashMap的源碼，可以查看我上一篇文章的介紹《Java集合系列[3]----HashMap源碼分析》。只要深入理解了HashMap的實現(xiàn)原理，回過頭來再去看LinkedHashMap，HashSet和LinkedHashSet的源碼那都是非常簡單的。因此，讀者們好好耐下性子來研究研究HashMap源碼吧，這可是買一送三的好生意啊。在前面分析HashMap源碼時，我采用以問題為導向對源碼進行分析，這樣使自己不會像無頭蒼蠅一樣亂分析一通，讀者也能夠針對問題更加深入的理解。本篇我決定還是采用這樣的方式對LinkedHashMap進行分析。

1. LinkedHashMap內部采用了什么樣的結構？

可以看到，由于LinkedHashMap是繼承自HashMap的，所以LinkedHashMap內部也還是一個哈希表，只不過LinkedHashMap重新寫了一個Entry，在原來HashMap的Entry上添加了兩個成員變量，分別是前繼結點引用和后繼結點引用。這樣就將所有的結點鏈接在了一起，構成了一個雙向鏈表，在獲取元素的時候就直接遍歷這個雙向鏈表就行了。我們看看LinkedHashMap實現(xiàn)的Entry是什么樣子的。

private static class Entry<K,V> extends HashMap.Entry<K,V> {
  //當前結點在雙向鏈表中的前繼結點的引用
  Entry<K,V> before;
  //當前結點在雙向鏈表中的后繼結點的引用
  Entry<K,V> after;

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

  //從雙向鏈表中移除該結點
  private void remove() {
    before.after = after;
    after.before = before;
  }

  //將當前結點插入到雙向鏈表中一個已存在的結點前面
  private void addBefore(Entry<K,V> existingEntry) {
    //當前結點的下一個結點的引用指向給定結點
    after = existingEntry;
    //當前結點的上一個結點的引用指向給定結點的上一個結點
    before = existingEntry.before;
    //給定結點的上一個結點的下一個結點的引用指向當前結點
    before.after = this;
    //給定結點的上一個結點的引用指向當前結點
    after.before = this;
  }

  //按訪問順序排序時, 記錄每次獲取的操作
  void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //如果是按訪問順序排序
    if (lm.accessOrder) {
      lm.modCount++;
      //先將自己從雙向鏈表中移除
      remove();
      //將自己放到雙向鏈表尾部
      addBefore(lm.header);
    }
  }
  
  void recordRemoval(HashMap<K,V> m) {
    remove();
  }
}

2. LinkedHashMap是怎樣實現(xiàn)按插入順序排序的？

//父類put方法中會調用的該方法
void addEntry(int hash, K key, V value, int bucketIndex) {
  //調用父類的addEntry方法
  super.addEntry(hash, key, value, bucketIndex);
  //下面操作是方便LRU緩存的實現(xiàn), 如果緩存容量不足, 就移除最老的元素
  Entry<K,V> eldest = header.after;
  if (removeEldestEntry(eldest)) {
    removeEntryForKey(eldest.key);
  }
}

//父類的addEntry方法中會調用該方法
void createEntry(int hash, K key, V value, int bucketIndex) {
  //先獲取HashMap的Entry
  HashMap.Entry<K,V> old = table[bucketIndex];
  //包裝成LinkedHashMap自身的Entry
  Entry<K,V> e = new Entry<>(hash, key, value, old);
  table[bucketIndex] = e;
  //將當前結點插入到雙向鏈表的尾部
  e.addBefore(header);
  size++;
}

LinkedHashMap重寫了它的父類HashMap的addEntry和createEntry方法。當要插入一個鍵值對的時候，首先會調用它的父類HashMap的put方法。在put方法中會去檢查一下哈希表中是不是存在了對應的key，如果存在了就直接替換它的value就行了，如果不存在就調用addEntry方法去新建一個Entry。注意，這時候就調用到了LinkedHashMap自己的addEntry方法。我們看到上面的代碼，這個addEntry方法除了回調父類的addEntry方法之外還會調用removeEldestEntry去移除最老的元素，這步操作主要是為了實現(xiàn)LRU算法，下面會講到。我們看到LinkedHashMap還重寫了createEntry方法，當要新建一個Entry的時候最終會調用這個方法，createEntry方法在每次將Entry放入到哈希表之后，就會調用addBefore方法將當前結點插入到雙向鏈表的尾部。這樣雙向鏈表就記錄了每次插入的結點的順序，獲取元素的時候只要遍歷這個雙向鏈表就行了，下圖演示了每次調用addBefore的操作。由于是雙向鏈表，所以將當前結點插入到頭結點之前其實就是將當前結點插入到雙向鏈表的尾部。

3. 怎樣利用LinkedHashMap實現(xiàn)LRU緩存？

我們知道緩存的實現(xiàn)依賴于計算機的內存，而內存資源是相當有限的，不可能無限制的存放元素，所以我們需要在容量不夠的時候適當?shù)膭h除一些元素，那么到底刪除哪個元素好呢？LRU算法的思想是，如果一個數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高。所以我們可以刪除那些不經(jīng)常被訪問的數(shù)據(jù)。接下來我們看看LinkedHashMap內部是怎樣實現(xiàn)LRU機制的。

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
  //雙向鏈表頭結點
  private transient Entry<K,V> header;
  //是否按訪問順序排序
  private final boolean accessOrder;
  ...
  public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
  }
  //根據(jù)key獲取value值
  public V get(Object key) {
    //調用父類方法獲取key對應的Entry
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null) {
      return null;
    }
    //如果是按訪問順序排序的話, 會將每次使用后的結點放到雙向鏈表的尾部
    e.recordAccess(this);
    return e.value;
  }
  private static class Entry<K,V> extends HashMap.Entry<K,V> {
    ...
    //將當前結點插入到雙向鏈表中一個已存在的結點前面
    private void addBefore(Entry<K,V> existingEntry) {
      //當前結點的下一個結點的引用指向給定結點
      after = existingEntry;
      //當前結點的上一個結點的引用指向給定結點的上一個結點
      before = existingEntry.before;
      //給定結點的上一個結點的下一個結點的引用指向當前結點
      before.after = this;
      //給定結點的上一個結點的引用指向當前結點
      after.before = this;
    }
    //按訪問順序排序時, 記錄每次獲取的操作
    void recordAccess(HashMap<K,V> m) {
      LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
      //如果是按訪問順序排序
      if (lm.accessOrder) {
        lm.modCount++;
        //先將自己從雙向鏈表中移除
        remove();
        //將自己放到雙向鏈表尾部
        addBefore(lm.header);
      }
    }
    ...
  }
  //父類put方法中會調用的該方法
  void addEntry(int hash, K key, V value, int bucketIndex) {
    //調用父類的addEntry方法
    super.addEntry(hash, key, value, bucketIndex);
    //下面操作是方便LRU緩存的實現(xiàn), 如果緩存容量不足, 就移除最老的元素
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
      removeEntryForKey(eldest.key);
    }
  }
  //是否刪除最老的元素, 該方法設計成要被子類覆蓋
  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
  }
}

為了更加直觀，上面貼出的代碼中我將一些無關的代碼省略了，我們可以看到LinkedHashMap有一個成員變量accessOrder，該成員變量記錄了是否需要按訪問順序排序，它提供了一個構造器可以自己指定accessOrder的值。每次調用get方法獲取元素式都會調用e.recordAccess(this)，該方法會將當前結點移到雙向鏈表的尾部。現(xiàn)在我們知道了如果accessOrder為true那么每次get元素后都會把這個元素挪到雙向鏈表的尾部。這一步的目的是區(qū)別出最常使用的元素和不常使用的元素，經(jīng)常使用的元素放到尾部，不常使用的元素放到頭部。我們再回到上面的代碼中看到每次調用addEntry方法時都會判斷是否需要刪除最老的元素。判斷的邏輯是removeEldestEntry實現(xiàn)的，該方法被設計成由子類進行覆蓋并重寫里面的邏輯。注意，由于最近被訪問的結點都被挪動到雙向鏈表的尾部，所以這里是從雙向鏈表頭部取出最老的結點進行刪除。下面例子實現(xiàn)了一個簡單的LRU緩存。

public class LRUMap<K, V> extends LinkedHashMap<K, V> {
  
  private int capacity;
  
  LRUMap(int capacity) {
    //調用父類構造器, 設置為按訪問順序排序
    super(capacity, 1f, true);
    this.capacity = capacity;
  }
  
  @Override
  public boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    //當鍵值對大于等于哈希表容量時
    return this.size() >= capacity;
  }
  
  public static void main(String[] args) {
    LRUMap<Integer, String> map = new LRUMap<Integer, String>(4);
    map.put(1, "a");
    map.put(2, "b");
    map.put(3, "c");
    System.out.println("原始集合:" + map);
    String s = map.get(2);
    System.out.println("獲取元素:" + map);
    map.put(4, "d");
    System.out.println("插入之后:" + map);
  }
  
}

結果如下：