LinkedHashMap

发表于 2019-01-11 更新于 2020-11-23 分类于 Java 阅读次数：

LinkedHashMap的继承关系

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

继承自HashMap，实现了Map接口

LinkedHashMap的成员变量

private static final long serialVersionUID = 3801124242820219131L;

// 用于指向双向链表的头部
transient LinkedHashMap.Entry<K,V> head;
//用于指向双向链表的尾部
transient LinkedHashMap.Entry<K,V> tail;
/**
 * 用来指定LinkedHashMap的迭代顺序，
 * true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾
 * false则表示按照插入顺序来
 */ 
final boolean accessOrder;

LinkedHashMap的成员变量

private static final long serialVersionUID = 3801124242820219131L;

// 用于指向双向链表的头部
transient LinkedHashMap.Entry<K,V> head;
//用于指向双向链表的尾部
transient LinkedHashMap.Entry<K,V> tail;
/**
 * 用来指定LinkedHashMap的迭代顺序，
 * true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾
 * false则表示按照插入顺序来
 */ 
final boolean accessOrder;

accessOrder 的final关键字，说明我们要在构造方法里给它初始化。

LinkedHashMap的构造方法

跟HashMap类似的构造方法这里就不一一赘述了，里面唯一的区别就是添加了前面提到的accessOrder，默认赋值为false——按照插入顺序来排列，这里主要说明一下不同的构造方法。

//多了一个 accessOrder的参数，用来指定按照LRU排列方式还是顺序插入的排序方式
public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
   super(initialCapacity, loadFactor);
   this.accessOrder = accessOrder;
}

LinkedHashMap的get()方法

LinkedHashMap是怎么加上双向链表的呢，我们先来看一下 get() 方法

public V get(Object key) {
  Node<K,V> e;
  //调用HashMap的getNode的方法，详见上一篇HashMap源码解析
  if ((e = getNode(hash(key), key)) == null)
    return null;
  //在取值后对参数accessOrder进行判断，如果为true，执行afterNodeAccess
  if (accessOrder)
    afterNodeAccess(e);
  return e.value;
}

从上面的代码可以看到，LinkedHashMap的get方法，调用HashMap的getNode方法后，对accessOrder的值进行了判断，我们之前提到：
accessOrder为true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾
由此可见，afterNodeAccess(e) 就是基于访问的顺序排列的关键，让我们来看一下它的代码：

//此函数执行的效果就是将最近使用的Node，放在链表的最末尾
void afterNodeAccess(Node<K,V> e) {
  LinkedHashMap.Entry<K,V> last;
  //仅当按照LRU原则且e不在最末尾，才执行修改链表，将e移到链表最末尾的操作
  if (accessOrder && (last = tail) != e) {
    //将e赋值临时节点p， b是e的前一个节点， a是e的后一个节点
    LinkedHashMap.Entry<K,V> p =
      (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //设置p的后一个节点为null，因为执行后p在链表末尾，after肯定为null
    p.after = null;
    //p前一个节点不存在，情况一
    if (b == null) // ①
      head = a;
    else
      b.after = a;
    if (a != null) 
      a.before = b;
    //p的后一个节点不存在，情况二
    else // ②
      last = b;
    //情况三
    if (last == null) // ③
      head = p;
    //正常情况，将p设置为尾节点的准备工作，p的前一个节点为原先的last，last的after为p
    else {
      p.before = last;
      last.after = p;
    }
    //将p设置为将p设置为尾节点
    tail = p;
    // 修改计数器+1
    ++modCount;
  }
}

标注的情况如下图所示（特别说明一下，这里是显示链表的修改后指针的情况，实际上在桶里面的位置是不变的，只是前后的指针指向的对象变了）：

下面来简单说明一下：
正常情况下：查询的p在链表中间，那么将p设置到末尾后，它原先的前节点b和后节点a就变成了前后节点。
情况一：p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为head
情况二：p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b
情况三：p为链表里的第一个节点，head=p

LinkedHashMap的put()方法

看一下LinkedHashMap是怎么插入Entry的：LinkedHashMap的put方法调用的还是HashMap里的put，不同的是重写了里面的部分方法，一起来看一下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    ...
    tab[i] = newNode(hash, key, value, null);
    ...
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    ...
    if ((e = p.next) == null) {
      p.next = newNode(hash, key, value, null);
    ...
        afterNodeAccess(e);
    ...
        afterNodeInsertion(evict);
      return null;
}

LinkedHashMap将其中newNode方法以及之前设置下的钩子方法afterNodeAccess和afterNodeInsertion进行了重写，从而实现了加入链表的目的。一起来看一下：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  //秘密就在于 new的是自己的Entry类，然后调用了linkedNodeLast
  LinkedHashMap.Entry<K,V> p =
    new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  linkNodeLast(p);
  return p;
}

//顾名思义就是把新加的节点放在链表的最后面
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  //将tail给临时变量last
  LinkedHashMap.Entry<K,V> last = tail;
  //把new的Entry给tail
  tail = p;
  //若没有last，说明p是第一个节点，head=p
  if (last == null)
    head = p;
  //否则就做准备工作，你懂的 (￣▽￣)"
  else {
    p.before = last;
    last.after = p;
  }
}

//这里笔者也把TreeNode的重写也加了进来，因为putTreeVal里有调用了这个
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;
}

//插入后把最老的Entry删除，不过removeEldestEntry总是返回false，所以不会删除，估计又是一个钩子方法给子类用的
void afterNodeInsertion(boolean evict) {
  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;
}

设计者灵活的运用了Override，以及设置的钩子方法，实现了双向链表。

LinkedHashMap的remove()

我们提到过remove里面设计者也设置了一个钩子方法：

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
  ...
      //node即是要删除的节点
      afterNodeRemoval(node);
  ...
}

看一下这个方法干了什么：

void afterNodeRemoval(Node<K,V> e) {
  //与afterNodeAccess一样，记录e的前后节点b，a
  LinkedHashMap.Entry<K,V> p =
    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  //p已删除，前后指针都设置为null，便于GC回收
  p.before = p.after = null;
  //与afterNodeAccess一样类似，一顿判断，然后b，a互为前后节点
  if (b == null)
    head = a;
  else
    b.after = a;
  if (a == null)
    tail = b;
  else
    a.before = b;
}

LinkedHashMap的迭代器

来看一下LinkedHashMap的最基础的迭代器——LinkedHashIterator

abstract class LinkedHashIterator {
  //记录下一个Entry
  LinkedHashMap.Entry<K,V> next;
  //记录当前的Entry
  LinkedHashMap.Entry<K,V> current;
  //记录是否发生了迭代过程中的修改
  int expectedModCount;

  LinkedHashIterator() {
    //初始化的时候把head给next
    next = head;
    expectedModCount = modCount;
    current = null;
  }

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

  //这里采用的是链表方式的遍历方式，有兴趣的园友可以去上一章看看HashMap的遍历方式
  final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
    if (e == null)
      throw new NoSuchElementException();
    //记录当前的Entry
    current = e;
    //直接拿after给next
    next = e.after;
    return e;
  }

  public final void remove() {
    Node<K,V> p = current;
    if (p == null)
      throw new IllegalStateException();
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
    current = null;
    K key = p.key;
    removeNode(hash(key), key, null, false, false);
    expectedModCount = modCount;
  }
}

LinkedHashMap实现LRU缓存

LinkedHashMap，它继承了HashMap。在HashMap中有三个方法是没有实现的：

afterNodeAccess：访问节点之后调用的方法
afterNodeInsertion：插入节点之后调用的方法
afterNodeRemoval：删除节点之后调用的方法

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }  //访问节点之后调用的方法
void afterNodeInsertion(boolean evict) { } //插入节点之后调用的方法
void afterNodeRemoval(Node<K,V> p) { }  //删除节点之后调用的方法

这三个方法都是在put、get、remove方法中回调的方法。在学习HashMap的时候，我并没有注意到这三个方法，现在才知道他们的重要性，目前这三个方法只在LinkedHashMap中实现了。
LinkedHashMap默认是按照节点的插入顺序，即先进先出，但是通过实例化时设置参数(AccessOrder = true)，可以修改为按访问顺序进出。
LRU：最近最少访问，实现原理是：

当访问元素时，先在HashMap中找到该节点，再将该节点移动到链表的末尾；
当添加元素时，先在HashMap中定位，将节点插入到HashMap中，同时将节点插入到链表的末尾；
因为缓存是有大小的，如果插入的节点数目超过了缓存大小，就需要删除最近最少使用的节点，即在HashMap中删除节点，同时删除链表的表头节点；

¶afterNodeAccess(Node<K,V> p) { } //访问节点之后调用的方法

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;
    }
}

这个方法在put方法中被调用，具体是在当put()是更新操作时，即put的key已经存在。这个方法的具体作用就是：在对节点进行访问之后，会更新链表，将节点移动到链表的尾部，表示最近被访问过。细心的同学会问，那调用get方法进行访问的时候，该怎么办呢？是的，因为HashMap的get方法并没有回调这个方法，所以LInkedHashMap自己实现了get方法

¶afterNodeInsertion(boolean evict) { } //插入节点之后调用的方法

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);
    }
}

这个方法是在HashMap中的put方法中被调用，具体是当put方法是添加操作时，即put的key不存在。这个方法的具体作用是：在插入新节点后，因为缓存不够，需要删除最近最少使用的节点。
这里的删除操作还是HashMap中实现的removeNode方法，只是在removeNode方法中调用了 afterNodeRemoval方法（下面介绍）。这里需要用户实现removeEldestEntry(first)方法，即如果需要进行删除的话，将这个方法重写。

1
2
3

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

这个方法默认是返回false，即不进行删除操作。用户如果需要的话，就可以重写该方法，根据自己的条件返回true即可，比如return size() > cacheSize。

¶afterNodeRemoval(Node<K,V> p) { } //删除节点之后调用的方法

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

因为在HashMap的removeNode方法中，只是删除了HashMap中的节点，并没有在链表中删除。所以在removeNode中，回调了这个方法，将该节点从链表中删除（这里是删除的头结点，因为头结点是最早进入或者最近最久未使用的）。

¶get和put方法

LinkedHashMap自己并没有重写put方法，上面已经介绍过。但是为了访问，所以LinkedHashMap自己实现了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;
 }

这里的getNode()方法是HashMap中的方法，这里只是多了一个判断：if(accessOrder)，即如果需要按照访问顺序进行迭代，就调用afterNodeAccess方法，将节点移动到链表的末尾。

¶containsValue方法有改进

/**
*LinkedHashMap中
*/
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;
}

/**
* HashMap中
*/
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

¶代码实现LRU1：类似内部类

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * Created by on 19-4-13
 */
public class LRUCache2 {
    public static void main(String[] args) {
        final int cacheSize = 3;
        Map<String, Integer> map = new LinkedHashMap<String, Integer>((int) Math.ceil(cacheSize / 0.75f) + 1,
                0.75f, true){
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
                return size() > cacheSize;
            }

            @Override
            public String toString() {
                for (Map.Entry<String, Integer> map : entrySet()){
                    System.out.print(String.format("%s:%s ", map.getKey(), map.getValue()));
                }
                System.out.println();
                return null;
            }
        };
        map.put("政治", 5);
        map.put("语文", 1);
        map.put("英文", 3);
        System.out.println(map.toString());
        map.get("政治");
        map.put("地理", 6);
        System.out.println(map.toString());
    }
}

运行结果：

¶LRU实现2：标准实现

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * Created by on 19-4-12
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V>{
    private final int MAX_CACHE_SIZE;

    public LRUCache(int cacheSize){
        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
        MAX_CACHE_SIZE = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_CACHE_SIZE;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(Map.Entry<K, V> entry : entrySet()){
            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> lruCache = new LRUCache<>(3);
        lruCache.put("政治", 5);
        lruCache.put("语文", 1);
        lruCache.put("英文", 3);
        System.out.println(lruCache.toString());
        lruCache.get("政治");
        lruCache.put("地理", 6);
        System.out.println(lruCache.toString());
    }
}

运行结果：