1.LRU 算法简介

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

常用与缓存数据的淘汰

2.LRU的思想

1、所谓缓存，必须要有读+写两个操作，按照命中率的思路思考，写操作+读操作的时间复杂度都需要为O(1)

2、特性要求

• 比如要有顺序之分，区分最近使用和很久没有使用的数据排序
• 写和读操作一次搞定
• 如果容量满了要删除最不常用的数据，每次新访问还要把新的数据插入到队头(按照业务决定左右那一边是队头)

LRU 算法的核心是哈希+链表：本质就是HashMap+DoubleLinkedList，时间复杂度是O(1)，哈希找一次就可以找到，满足我们查找快的需求，双向链表保证增删比较快。所以查找用哈希增删用链表，这样就比较方便

3.LinkedHashMap实现LRU

LinkedHashMap就是LRU算法的体现

LinkedHashMap底层就是用的HashMap加双向链表实现的，而且本身已经实现了按照访问顺序的存储。此外，LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数，方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数。

代码示例如下：

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

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

    // 缓存的容量
    private int capacity;

    // 构造器方法
    /*  capacity：指定缓存的容量
        loadFactor：负载因子，HashMap默认是0.75 这里不做修改
        accessOrder：访问顺序
           true：按照访问顺序将数据设置为最活跃
           false：按照插入顺序将数据设置为最活跃
     */
    public LRUCacheDemo(int capacity) {
        super(capacity,0.75F,false);
        this.capacity = capacity;
    }

    // 过期数据清理方法：HashMap里面的数据大于自己定义的容量，则删除最近最少使用的数据
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return super.size() > capacity;
    }

    public static void main(String[] args) {
        LRUCacheDemo lruCacheDemo= new LRUCacheDemo(3);

        // LinkedHashMap继承了HashMap的get和put方法，所以代码中可以不写，直接调用
        lruCacheDemo.put(1,"a");
        lruCacheDemo.put(2,"b");
        lruCacheDemo.put(3,"c");

        System.out.println(lruCacheDemo.keySet());

        lruCacheDemo.put(4,"d");
        System.out.println(lruCacheDemo.keySet());

        lruCacheDemo.put(3,"c");
        System.out.println(lruCacheDemo.keySet());
        lruCacheDemo.put(3,"c");
        System.out.println(lruCacheDemo.keySet());
        lruCacheDemo.put(3,"c");
        System.out.println(lruCacheDemo.keySet());

        lruCacheDemo.put(5,"e");
        System.out.println(lruCacheDemo.keySet());
    }
}

列表中最左边的数据是最近最少使用数据，右边是最经常使用数据

accessOrder为true

执行结果：可以看到，accessOrder为true的情况下，最新的数据是按照最近一次访问顺序来决定的

[1, 2, 3]
[2, 3, 4]
[2, 4, 3]
[2, 4, 3]
[2, 4, 3]
[4, 3, 5]

accessOrder为false

执行结果：可以看到，accessOrder为false的情况下，最新的数据是按照插入顺序来决定的

[1, 2, 3]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[3, 4, 5]

4.手写LRU

利用双向链表+hashmap实现：当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

import java.util.HashMap;
import java.util.Map;

public class LRUCacheDemo{

    // map负责查找，构建一个虚拟的双向链表，它里面安装的就是一个个Node节点，作为数据载体

    // 1、构造一个Node节点，作为数据载体
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;

        public Node(){
            this.prev = this.next = null;
        }

        public Node(K key,V value){
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }
    // 2、构建一个虚拟的双向链表，里面安放的就是我们的Node
    class DoubleLinkedList<K,V>{
        Node<K,V> head;
        Node<K,V> tail;

        // 构造方法
        public DoubleLinkedList(){
            head = new Node<>();
            tail = new Node<>();
            head.next = tail;
            tail.prev = head;
        }

        // 添加到头
        public void addHead(Node<K,V> node){
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        // 删除节点
        public void removeNode(Node<K,V> node){
            node.next.prev = node.prev;
            node.prev.next = node.next;
            node.prev = null;
            node.next = null;
        }

        // 获得最后一个节点
        public Node getLast(){
            return tail.prev;
        }
    }

    private int cacheSize;
    Map<Integer, Node<Integer,Integer>> map;
    DoubleLinkedList<Integer,Integer> doubleLinkedList;

    public LRUCacheDemo(int cacheSize){
        // 设置缓存容量
        this.cacheSize = cacheSize;
        // 查找
        map = new HashMap<>();
        doubleLinkedList = new DoubleLinkedList<>();
    }

    // 查找方法
    public int get(int key){
        // 如果没有这个key则返回-1
        if (!map.containsKey(key)){
            return -1;
        }

        // 返回数据，并且将数据从当前位置移除，添加到队头
        Node<Integer, Integer> node = map.get(key);
        doubleLinkedList.removeNode(node);
        doubleLinkedList.addHead(node);

        return node.value;
    }

    // 保存以及更新方法
    public void put(int key, int value){
        if (map.containsKey(key)) { // 更新操作
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            map.put(key,node);

            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
        } else {
            if (map.size() == cacheSize){  // 容量满了
                Node<Integer,Integer> lastNode = doubleLinkedList.getLast();
                map.remove(lastNode.key);
                doubleLinkedList.removeNode(lastNode);
            }
            // 新增操作
            Node<Integer, Integer> newNode = new Node<>(key, value);
            map.put(key,newNode);
            doubleLinkedList.addHead(newNode);
        }
    }

    public static void main(String[] args) {
        LRUCacheDemo lruCacheDemo= new LRUCacheDemo(3);

        lruCacheDemo.put(1,1);
        lruCacheDemo.put(2,2);
        lruCacheDemo.put(3,3);

        System.out.println(lruCacheDemo.map.keySet());

        lruCacheDemo.put(4,4);
        System.out.println(lruCacheDemo.map.keySet());

        lruCacheDemo.put(3,3);
        System.out.println(lruCacheDemo.map.keySet());
        lruCacheDemo.put(3,3);
        System.out.println(lruCacheDemo.map.keySet());
        lruCacheDemo.put(3,3);
        System.out.println(lruCacheDemo.map.keySet());

        lruCacheDemo.put(5,5);
        System.out.println(lruCacheDemo.map.keySet());
    }
}

程序输出结果如下：

[1, 2, 3]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[3, 4, 5]

转载请注明：西门飞冰的博客 » LRU最近最少使用算法