LRU算法的两种简单实现

一、什么是LRU

我们来看一下百度百科的解释。

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

这里只是说页面置换算法中的一种，其实我们缓存中这种算法也是很常见的，mysql底层其实用的是这种置换算法。一般我们做缓存不希望内存被大量消耗导致OOM的时候，这种算法是很常用的，比如redis默认的就是一种伪lru，原理是一样的。今天就来自己简单实现一下这种算法。

二、两种实现方式

1.第一种利用LinkedHashMap的方式实现

研究过HashMap源码的人都应该会发现不管是putAll方法还是一个get方法，只要访问到元素的方法或多或少都会出现下面几个莫名的方法。

刚开始研究源码的时候觉得这不是有毛病吧，调用几个空方法什么意思。后面看多了就发现这是维护热点数据功能的LinkedHashMap而实现的。如果你想要维持写入HashMap元素的顺序或者维持一个热点的话，可以选择LinkedHashMap快捷实现。接下来我就来利用LinkedHashMap来简单实现一个demo，demo是这样的一个直播间只允许５个人进入，当直播间里面已经有五个人的时候，第６个人要想进入，就必须将最早进入或者最近时间发言最少的人踢出直播间。具体demo如下：

LruCache.java

import java.util.LinkedHashMap;
import java.util.Map;
/**
 * 利用LinkedHashMap 自定义实现lru算法
 * @param <K>
 * @param <V>
 */
public class  LruCache<K,V> extends LinkedHashMap {
    private int capacity;
    public LruCache(int capacity){
        super(capacity,0.75F,true);
        this.capacity = capacity;
    }
    //　进入直播间的人发言方法
    public V get(Object key){
        return (V) super.get(key);
    }
    //　进入直播间的方法
    public V put(Object key, Object value){
        V oldValue = (V) super.put(key,value);
        return oldValue;
    }
    // 进来之后最近最久为发言的人被自动踢出
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }
}

利用这个类我们来实现这个demo:

PutRoom.java

import java.util.Iterator;

public class PutRoom {
    public static void main(String[] args) {
        // 验证利用LinkedHashMap
        LruCache<Integer,String> lruCache = new LruCache<Integer, String>(5);
        for(int i = 1; i < 6; i++){
            lruCache.put(i,i+1);
            System.out.println("第 " + i +" 个人进入房间");
        }
        System.out.print("此时在房间中的人：");
        Iterator iterator = (Iterator) lruCache.keySet().iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next() + " ");
        }
        lruCache.get(1);
        System.out.println();
        System.out.println("第1个进入房间的人说话了！");
        lruCache.put(6,"第　" + 6 + " 个人进入了房间");
        System.out.println("第二个进入房间的人被踢了，应为他比剩下的没发言的都早进来！！");
        System.out.print("房间中剩余的人：");
        Iterator peopleAfter = (Iterator) lruCache.keySet().iterator();
        while (peopleAfter.hasNext()){
            System.out.print(peopleAfter.next() + " ");
        }
    }
}

我们可以来看看结果：

很明显达到到了我们的要求。这里是把热点数据放到了链表尾部，接下来我们自己实现一个把热点数据链表头部的算法吧。

2.第二种我们利用HashTable + 双向链表来实现

这种实现方式其实和上面的原理是一样的，只不过这是我们自己来实现一个双端链表的结构，将热点数据放在链表头部以及插入和删除。这里的话也和上面一样实现一个demo。具体看下面代码：

CustomLruCache.java

import java.util.Hashtable;
public class CustomLruCache {
    /**
     * 自定义双端链表
     */
    class DLinkedNode {
        int key;
        String value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    /**
     * 链表操作的新增节点，并使用头插法，保持热点数据在头部
     * @param node
     */
    private void addNode(DLinkedNode node) {

        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    /**
     * 链表操作的移除节点
     * @param node
     */
    private void removeNode(DLinkedNode node) {

        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    /**
     * 将节点移动到头部
     * @param node
     */
    private void moveToHead(DLinkedNode node) {

        removeNode(node);
        addNode(node);
    }

    /**
     * 将尾部节点移除
     * @return
     */
    private DLinkedNode popTail() {

        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

    private Hashtable<Integer, DLinkedNode> cache =
            new Hashtable<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public CustomLruCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 表头
        head = new DLinkedNode();
        // 表尾
        tail = new DLinkedNode();

        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取节点，不存在返回-1
     * 存在移动到链表头部并返回
     * @param key
     * @return
     */
    public String get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return "-1";

        moveToHead(node);

        return node.value;
    }

    /**
     * 插入节点，保证热点在头部
     * @param key
     * @param value
     */
    public void put(int key, String value) {
        DLinkedNode node = cache.get(key);
        // 插入节点不存在
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            cache.put(key, newNode);
            addNode(newNode);

            ++size;
            // 节点数大于最大容量，移除非热点数据
            if (size > capacity) {
                DLinkedNode tail = popTail();
                cache.remove(tail.key);
                --size;
            }
            // 插入节点已存在，更新值并移动到链表头部
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
}

我们简单来测试一下

LruExample.java

public class LruExample {
    public static void main(String[] args){
        CustomLruCache customLruCache = new CustomLruCache(5);
        for(int i = 0; i < 5; i++){
            customLruCache.put(i,i+"");
        }
        System.out.print("容器key = 0的初始内容：");
        System.out.println(customLruCache.get(0));
        System.out.println("key = 0，被获取了一次，所以会在队头，新增一个，导致key = 1被淘汰");
        customLruCache.put(6,"6");
        System.out.println("里面没有key =　1的，以及被淘汰,索引返回值为" + customLruCache.get(1));
    }
}

输出结果：