LinkedHashMap实现LRU - 附重点源码解析

最近接触LRU(Least Recently Used)，即最近最少使用，也称淘汰算法，在JDK中LinkedHashMap有相关实现，下面针对LRU及LinkedHashMap的LRU实现进行详细讲解

1. 为什么使用LRU

有些数据需要缓存在内存中，以便高效查询。但是当缓存的数据量很大，并且某一时间段只有某小部分缓存数据被频繁使用(称之为热点数据)，而其他缓存数据暂时没有访问，这时就需要LRU策略对热点数据进行保留，对非热点数据进行及时下线，保证缓存空间健康。
应用场景: 商城分时段商品秒杀

2. LRU的LinkedHashMap实现

创建LRULinkedHashMap继承LinkedHashMap并重写removeEldestEntry方法，该方法返回的boolean代表是否删除最早使用/存放的Entry。

• LRULinkedHashMap

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {

    private int threshold;

    public LRULinkedHashMap(int threshold) {
        super(16, 0.75f, true);
        this.threshold = threshold;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > threshold;
    }
}

• 使用

1. get操作，会将节点移动到队尾。
2. put操作，如果key不存在，则节点放置队尾，如果节点存在，会将节点移动到队尾。

public static void main(String[] args) {
    LRULinkedHashMap<String, String> lruLinkedHashMap = new LRULinkedHashMap<>(5);
    lruLinkedHashMap.put("1", null);
    lruLinkedHashMap.put("2", null);
    lruLinkedHashMap.put("3", null);
    lruLinkedHashMap.put("4", null);
    lruLinkedHashMap.put("5", null);
    lruLinkedHashMap.put("6", null);
    lruLinkedHashMap.put("7", null);
    System.out.println(lruLinkedHashMap);
    lruLinkedHashMap.get("4");
    System.out.println(lruLinkedHashMap);
    lruLinkedHashMap.put("5", null);
    System.out.println(lruLinkedHashMap);

    out => {3=null, 4=null, 5=null, 6=null, 7=null}
    out => {3=null, 5=null, 6=null, 7=null, 4=null}
    out => {3=null, 6=null, 7=null, 4=null, 5=null}
}

3. LinkedHashMap实现Map有序 - 源码分析

LinkedHashMap继承自HashMap，HashMap采用数组加链表的结构存储数据，存储节点为HashMap.Node，分别存放hash值，key，value，以及指向下一个Node节点的next指针，链表结构是单项链表，HashMap并没有维护有序性。

• HashMap

  
  image.png

LinkedHashMap继承了HashMap，也是采用了数据加链表的结构，不同的是LinkedHashMap的存储节点(Entry)继承自HashMap.Node，多维护了before和after指针，用来指向上一个和下一个节点，实现双向链表。这个双向链表就可以实现Map有序性(access-order:访问顺序/insertion-order插入顺序，默认是insertion-order)。

• LinkedHashMap

  
  image.png

重点代码

• HashMap.Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    ...
}

• LinkedHashMap.Entry

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    ...
}

• HashMap - newNode

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

• LinkedHashMap - newNode

// 重写了HashMap - newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p); // 添加节点到队尾
    return p;
}

• HashMap - forEach
  先遍历数组，再顺序遍历链表

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (Node<K,V> e : tab) { // 先遍历数据
            for (; e != null; e = e.next) //再书序遍历链表
                action.accept(e.key, e.value);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

• LinkedHashMap - forEach
  直接遍历双向链表，实现有序性。

// Map overrides
public void forEach(BiConsumer<? super K, ? 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.key, e.value);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

4. LinkedHashMap实现LRU - 源码分析

下面是设置LinkedHashMap为访问顺序时的示意图。

image.png

• LinkedHashMap - 构造器
  accessOrder默认为false，即维护插入顺序，设置为true时，维护访问顺序。

* @param  accessOrder the ordering mode - {@code true} for access-order, {@code false} for insertion-order
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

public LinkedHashMap() {
    super();
    accessOrder = false; // 默认为插入顺序
}

• LinkedHashMap - get
  当设置为访问顺序时，在get/put的时候调用afterNodeAccess方法，将节点移动到队尾。

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

• LinkedHashMap - put - 更新值
  下面是HashMap的put操作，调用LinkedHashMap 的afterNodeAccess方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    ....
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e); // 将节点移动到队尾
        return oldValue;
    }
    ....
}

• LinkedHashMap - put - 插入新值
  插入新值， 调用linkNodeLast添加节点到队尾

// 重写了HashMap - newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p); // 添加节点到队尾
    return p;
}

相关参考

1. LeetCode – LRU Cache (Java)
2. 玩转Redis：8 种数据淘汰策略及近似LRU、LFU原理！