快捷導(dǎo)航

Java集合系列之LinkedHashMap源碼分析

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

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

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

1. LinkedHashMap內(nèi)部采用了什么樣的結(jié)構(gòu)？

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

private static class Entry<K,V> extends HashMap.Entry<K,V> {
  //當(dāng)前結(jié)點(diǎn)在雙向鏈表中的前繼結(jié)點(diǎn)的引用
  Entry<K,V> before;
  //當(dāng)前結(jié)點(diǎn)在雙向鏈表中的后繼結(jié)點(diǎn)的引用
  Entry<K,V> after;

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

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

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

  //按訪問順序排序時(shí), 記錄每次獲取的操作
  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是怎樣實(shí)現(xiàn)按插入順序排序的？

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

//父類的addEntry方法中會(huì)調(diào)用該方法
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;
  //將當(dāng)前結(jié)點(diǎn)插入到雙向鏈表的尾部
  e.addBefore(header);
  size++;
}

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

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

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

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

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

public class LRUMap<K, V> extends LinkedHashMap<K, V> {
  
  private int capacity;
  
  LRUMap(int capacity) {
    //調(diào)用父類構(gòu)造器, 設(shè)置為按訪問順序排序
    super(capacity, 1f, true);
    this.capacity = capacity;
  }
  
  @Override
  public boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    //當(dāng)鍵值對(duì)大于等于哈希表容量時(shí)
    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);
  }
  
}

結(jié)果如下：