如何進行JDK源碼分析LinkedHashMap相關

這期內容當中小編將會給大家帶來有關如何進行JDK源碼分析LinkedHashMap相關，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

LinkedHashMap實質是HashMap+LinkedList，提供了順序訪問的功能。

一、整體結構

1. 定義

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {}

從上述定義中也能看到LinkedHashMap其實就是繼承了HashMap，并加了雙向鏈表記錄順序，代碼和結構本身不難，但是其中結構的組織，代碼復用這些地方十分值得我們學習；具體結構如圖所示：

2. 構造函數和成員變量

public LinkedHashMap(int initialCapacity, float loadFactor) {}public LinkedHashMap(int initialCapacity) {}public LinkedHashMap() {}public LinkedHashMap(Map<? extends K, ? extends V> m) {}public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {}/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 * @serial
 */
 final boolean accessOrder;

可以看到LinkedHashMap的5個構造函數和HashMap的作用基本是一樣的，都是初始化initialCapacity和loadFactor，但是多了一個accessOrder，這也是LinkedHashMap最重要的一個成員變量了；

• 當accessOrder為true的時候，表示LinkedHashMap中記錄的是訪問順序，也是就沒放get一個元素的時候，這個元素就會被移到鏈表的尾部；

• 當accessOrder為false的時候，表示LinkedHashMap中記錄的是插入順序；

3. Entry關系

扎眼一看可能會覺得HashMap體系的節點繼承關系比較混亂；一所以這樣設計因為

• LinkedHashMap繼承至HashMap，其中的節點同樣有普通節點和樹節點兩種；并且樹節點很少使用；

• 現在的設計中，樹節點是可以完全復用的，但是HashMap的樹節點，會浪費雙向鏈表的能力；

• 如果不這樣設計，則至少需要兩條繼承關系，并且需要抽出雙向鏈表的能力，整個繼承體系以及方法的復用會變得非常復雜，不利于擴展；

二、重要方法

上面我們已經講了LinkedHashMap就是HashMap+鏈表，所以我們只需要在結構有可能改變的地方加上鏈表的修改就可以了，結構可能改變的地方只要有put/get/replace，這里需要注意擴容的時候雖然結構改變了，但是節點的順序仍然保持不變，所以擴容可以完全復用；

1. put 方法

• 未找到key時，直接在最后添加一個節點

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  linkNodeLast(p);  return p;
}TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
  TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
  linkNodeLast(p);  return p;
}private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  LinkedHashMap.Entry<K,V> last = tail;
  tail = p;  if (last == null)
    head = p;  else {
    p.before = last;
    last.after = p;
  }
}

上面代碼很簡單，但是很清晰的將添加節點到最后的邏輯抽離的出來；

• 找到key，則替換value，這部分需要聯系 HashMap 相關 中的put方法部分；

// HashMap.putVal...// 如果找到keyif (e != null) { // existing mapping for key
  V oldValue = e.value;  if (!onlyIfAbsent || oldValue == null)
    e.value = value;
  afterNodeAccess(e);  return oldValue;
}// 如果沒有找到key++modCount;if (++size > threshold)
  resize();
afterNodeInsertion(evict);return null;
...

在之前的HashMap源碼分析當中可以看到有幾個空的方法

void afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node<K,V> p) { }

這三個就是用來調整鏈表位置的事件方法，可以看到HashMap.putVal中就使用了兩個，

void afterNodeAccess(Node<K,V> e) { // move node to last
  LinkedHashMap.Entry<K,V> last;  if (accessOrder && (last = tail) != e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.after = null;    if (b == null)
      head = a;    else
      b.after = a;    if (a != null)
      a.before = b;    else
      last = b;    if (last == null)
      head = p;    else {
      p.before = last;
      last.after = p;
    }
    tail = p;
    ++modCount;
  }
}

afterNodeAccess可以算是LinkedHashMap比較核心的方法了，當訪問了一個節點的時候，如果accessOrder = true則將節點放到最后，如果accessOrder = false則不變；

void afterNodeInsertion(boolean evict) { // possibly remove eldest
  LinkedHashMap.Entry<K,V> first;  if (evict && (first = head) != null && removeEldestEntry(first)) {
    K key = first.key;
    removeNode(hash(key), key, null, false, true);
  }
}protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {  return false;
}

afterNodeInsertion方法是插入節點后是否需要移除最老的節點，這個方法和維護鏈表無關，但是對于LinkedHashMap的用途有很大作用，后天會舉例說明；

2. get 方法

public V get(Object key) {
  Node<K,V> e;  if ((e = getNode(hash(key), key)) == null)    return null;  if (accessOrder)
    afterNodeAccess(e);  return e.value;
}public V getOrDefault(Object key, V defaultValue) {
 Node<K,V> e; if ((e = getNode(hash(key), key)) == null)   return defaultValue; if (accessOrder)
   afterNodeAccess(e); return e.value;
}

get方法主要也是通過afterNodeAccess來維護鏈表位置關系；
以上就是LinkedHashMap鏈表位置關系調整的主要方法了；

3. containsValue 方法

public boolean containsValue(Object value) {  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;
}

可以看到LinkedHashMap還重寫了containsValue，在HashMap中尋找value的時候，需要遍歷所有節點，他是遍歷每個哈希桶，在依次遍歷桶中的鏈表；而在LinkedHashMap里面要遍歷所有節點的時候，就可以直接通過雙向鏈表進行遍歷了；

三、應用

public class Cache<K, V> {  private static final float DEFAULT_LOAD_FACTOR = 0.75f;  private final int MAX_CAPACITY;  private LinkedHashMap<K, V> map;  public Cache(int capacity, boolean accessOrder) {
    capacity = (int) Math.ceil((MAX_CAPACITY = capacity) / DEFAULT_LOAD_FACTOR) + 1;
    map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, accessOrder) {      @Override
      protected boolean removeEldestEntry(Map.Entry eldest) {        return size() > MAX_CAPACITY;
      }
    };
  }  public synchronized void put(K key, V value) {
    map.put(key, value);
  }  public synchronized V get(K key) {    return map.get(key);
  }  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();    for (Map.Entry entry : map.entrySet()) {
      sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
    }    return sb.toString();
  }
}

以上是就是一個LinkedHashMap的簡單應用，

• 當accessOrder = true時，就是LRUCache，

• 當accessOrder = false時，就是FIFOCache；

// LRUCacheCache<String, String> cache = new Cache<>(3, true);
cache.put("a", "1");
cache.put("b", "2");
cache.put("c", "3");
cache.put("d", "4");
cache.get("c");

System.out.println(cache);

// 打印：b:2 d:4 c:3

// FIFOCacheCache<String, String> cache = new Cache<>(3, false);
cache.put("a", "1");
cache.put("b", "2");
cache.put("c", "3");
cache.put("d", "4");
cache.get("c");

System.out.println(cache);

// 打印：b:2 c:3 d:4

• 總體而言LinkedHashMap的代碼比較簡單，但是我覺得里面代碼的組織，邏輯的提取等方面特別值得借鑒。

上述就是小編為大家分享的如何進行JDK源碼分析LinkedHashMap相關了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。