如何手写一个LRU算法

背景

在Redis的内存占用过多的时候,此时会进行内存淘汰,比较常用的就是基于LRU算法进行淘汰。那么什么是LRU算法呢?

LRU算法概念

LRU 是Least Recently Used的缩写,简称最近最少使用。

也就是说在Redis中内存满了,会优先淘汰那些最近最不常访问的数据。那在Java中用什么数据结构去实现呢?一种的话是基于LinkedHashMap,一种是自己设计数据结构,使用链表+HashMap。

既然有现成的,那我们就直接拿过来用吧。有人会问,为什么用LinkedHashMap呢?我们下面看一下LinkedHashMap的数据结构是怎么样的?

LinkedHashMap数据结构

LinkedHashMap继承了HashMap,拥有HashMap的所有特性,同时LinkedHashMap在增加了head和tail指针,用于实现双向链表

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

LinkedHashMap默认按照插入顺序保存数据,新的数据插入双向链表尾部

public static void main(String[] args) {
    LinkedHashMap<String,String> linkedHashMap = new LinkedHashMap<>();

    linkedHashMap.put("3","3");
    linkedHashMap.put("4","4");
    linkedHashMap.put("1","1");
    linkedHashMap.put("7","7");
    linkedHashMap.put("5","5");
    linkedHashMap.put("9","9");
    linkedHashMap.put("0","0");
    linkedHashMap.put("2","2");
    linkedHashMap.put("6","6");
    linkedHashMap.put("8","8");

    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }

}
=================运行结果=================
3
4
1
7
5
9
0
2
6
8

LinkedHashMap中有构造方法支持按顺序访问,最新访问的数据放到链表尾部

public static void main(String[] args) {
    LinkedHashMap<String,String> linkedHashMap = new LinkedHashMap<>(10,0.75f,true);

    linkedHashMap.put("3","3");
    linkedHashMap.put("4","4");
    linkedHashMap.put("1","1");
    linkedHashMap.put("7","7");
    linkedHashMap.put("5","5");
    linkedHashMap.put("9","9");
    linkedHashMap.put("0","0");
    linkedHashMap.put("2","2");
    linkedHashMap.put("6","6");
    linkedHashMap.put("8","8");

    linkedHashMap.get("4");
    linkedHashMap.get("7");
    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }

}
============运行结果===========
3
1
5
9
0
2
6
8
4
7

从下面源码中,我们可以看到,通过accessOrder如果为true,则按照访问顺序进行排序,将访问到的数据放置链表尾部,如果为false,则按插入顺序进行排序

/**
 * 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;

public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

// 获取元素
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;
}

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 开启按顺序访问且当前节点不是尾结点
    if (accessOrder && (last = tail) != e) {
        // 设置b为e的前置节点,a为e的后置节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 将当前节点的后置节点设为null
        p.after = null;
        // 如果e的前置节点为空,则将e的后置节点设置为头结点,否则将e的前置节点的后置节点设置为a
        if (b == null)
            head = a;
        else
            b.after = a;
        // 如果e的后置节点不为空,将e的后置节点的前置节点设置为b,否则,将e的前置节点设置为尾结点
        if (a != null)
            a.before = b;
        else
            last = b;
        // 如果尾节点为空,则将当前节点p设置为头结点,否则将当前节点的前置节点设置为尾结点,尾结点的后置节点为当前节点
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        // 设置当前节点为尾结点
        tail = p;
        ++modCount;
    }
}

LRU缓存实现

通过LinkedHashMap的特性,如何实现LRU算法呢,自动删除掉链表表头的过期数据

  • 定义一个类继承LinkedHashMap
public class LRULinkedMap<K,V> extends LinkedHashMap<K,V> {

    private int size;

    public LRULinkedMap(int initialCapacity,float loadFactor,boolean accessOrder){
        super(initialCapacity,loadFactor,accessOrder);
        this.size = initialCapacity;
    }

    /**
     * 重写LinkedHashMap的removeEldestEntry方法
     * 当LRU元素超过容量上限size后,删除最不经常使用的
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > size;
    }
}

  • 测试类
public static void main(String[] args) {
    LRULinkedMap<String,String> linkedHashMap = new LRULinkedMap<>(5,0.75f,true);

    linkedHashMap.put("3","3");
    linkedHashMap.put("4","4");
    linkedHashMap.put("1","1");
    linkedHashMap.put("5","5");
    linkedHashMap.put("6","6");

    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }

    System.out.println("=========get(1)后将1移动到尾部=========");

    linkedHashMap.get("1");

    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }

    System.out.println("=========插入新数据后,移除头部最老的3和4=========");

    linkedHashMap.put("2","2");
    linkedHashMap.put("9","9");

    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }
}
=========运行结果========
3
4
1
5
6
=========get(1)后将1移动到尾部=========
3
4
5
6
1
=========插入新数据后,移除头部最老的3和4=========
5
6
1
2
9

removeEldestEntry

目前看的确是达到了效果,但是也许有人会有疑问,为什么重写了removeEldestEntry就可以了,那我们去看看removeEldestEntry方法的源码是怎么样的。

在LinkedHashMap中,removeEldestEntry默认返回的是false

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

我们看看removeEldestEntry在哪里被用到了,false起到了什么作用

我们看到在LinkedHashMap中有这么一个方法afterNodeInsertion,在这个方法里需要同时满足以下3个条件才能将LinkedHashMap中的元素删除

  • 入参evict为true
  • LinkedHashMap中元素头节点不为null
  • removeEldestEntry方法返回为true
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);
    }
}

afterNodeInsertion方法是在HashMap中添加元素后所执行的方法,详情本篇文章就不做介绍了,可以自己去看看HashMap中内部的实现逻辑。

总结

本篇文章基于Redis的缓存淘汰策略介绍了LRU算法的背景,基本概念。基于LinkedHashMap的特性实现了简易版的LRU算法,并介绍LinkedHashMap内部的基本原理来帮助大家更好的理解LRU算法的实现。

(0)

相关推荐