由于blog各种垃圾评论太多,而且本人审核评论周期较长,所以懒得管理评论了,就把评论功能关闭,有问题可以直接qq骚扰我

LRU最近最少使用算法

算法 西门飞冰 59℃
[隐藏]

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最近最少使用算法

喜欢 (2)or分享 (0)