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

作者 : 开心源码本文共4028个字，预计阅读时间需要11分钟发布时间： 2022-05-13 共224人阅读

最近接触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;    }}

使用

get操作，会将节点移动到队尾。
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 - newNodeNode<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
先遍历数组，再顺序遍历链表

@Overridepublic 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 overridespublic 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-orderpublic 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 - newNodeNode<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;}