单向链表实现LRU缓存淘汰算法

大数据记事本 2020-07-20

884

一、LRU简介

缓存是一种提高数据读取性能的技术，比如常见的cpu缓存以及浏览器缓存！但是缓存的大小有限，当缓存用满的时候，哪些数据应该被清理出去，哪些数据应该被保留？LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，为最近最少使用策略。也就是说我们认为最近使用过的数据应该是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先清理那些很久没用过的数据。

二、LRU基本操作

查找：根据给定的key查看是否存在对应的value。如果key存在，将对应结点放在链表末尾(假设末尾的数据是最近最多使用的)，然后返回key对应的value，如果不存在，返回一个标记值，如null。
添加：根据给定的key-value数据添加结点。如果该数据结点之前已经在链表中，先遍历得到这个数据对应的结点，然后将其从原来的位置删除，再插入到链表的尾部。如果此数据结点之前不在链表中，分以下两种情况：

如果此时缓存未满，则将此结点直接插入到链表的尾部；
如果此时缓存已满，则删除链表的头部结点，将新的数据结点插入到链表的尾部。

三、代码实现

定义结点类型

class LRUNode{
    int key;
    Object value;
    LRUNode next;


    public LRUNode(int key) {
        this.key = key;
    }


    public LRUNode(int key, Object value) {
        this.key = key;
        this.value = value;
    }


    @Override
    public String toString() {
        return "LRUNode{" +
                "key=" + key +
                ", value=" + value +
                '}';
    }
}

LRU算法实现

public class LRU {
    LRUNode first = null;//头部结点
    LRUNode tail = null;//尾部结点
    int capacity;//缓存容量
    int count = 0;//缓存已使用空间


    public LRU(int capacity) {
        this.capacity = capacity;
    }


    //判断是否为空
    public Boolean isEmpty() {
        return first == null;
    }


    //判断是否已满
    public Boolean isFull() {
        return count == capacity;
    }


    //添加数据
    public void put(int key,Object value) {
        LRUNode node = new LRUNode(key,value);
        //如果链表为空，直接将first和tail指向新增结点
        if (isEmpty()) {
            first = node;
            tail = node;
            count++;
        } else {
            //查看结点是否存在，如果存在，放到链表末尾并return
            Object obj = get(key);
            if (obj != null) {
                return;
            } else {//如果不存在
                if (isFull()) {//如果已满，删除链表头部结点，将新增结点放在链表尾部
                    first = first.next;
                    tail.next = node;
                    tail = tail.next;
                } else {//如果未满，直接在尾部添加
                    tail.next = node;
                    tail = tail.next;
                    count++;
                }
            }
        }
    }




    //查看给定数据的结点是否存在，不存在返回null，如果存在将该结点放在链表尾部并返回value
    public Object get(int key) {
        if(isEmpty()){
            return null;
        }
        LRUNode node = new LRUNode(key);
        Boolean flag = false;
        LRUNode tmp = first;
        //如果first就是查找的结点，将其放在链表末尾，然后返回
        if (first.key == node.key) {
            node.value=first.value;
            tail.next = node;
            tail = tail.next;
            first = first.next;
            return tail.value;
        }
        //如果first不是要查找结点，向后遍历
        while (tmp.next != null) {
            if (tmp.next.key == node.key) {
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if (flag) {
            //如果存在，将该结点移动到链表末尾，然后返回该结点\
            node.value=tmp.next.value;
            tail.next = node;
            tail = tail.next;
            tmp.next = tmp.next.next;
            return tmp.next.value;
        } else {
            return null;
        }
    }


    /**
     * 遍历缓存
     */
    public void list() {
        LRUNode tmp = first;
        while (true) {
            if (tmp == null) {
                break;
            }
            System.out.println(tmp.toString());
            tmp = tmp.next;
        }
    }
}

四、复杂度分析

用单向链表实现LRU缓存淘汰算法时，主要涉及数据的查找、添加和删除，而这三种操作都要涉及数据的查找。单向链表查找的时间复杂度为O(n)，所以用单向链表实现的LRU算法的查找、添加和删除操作的时间复杂度也都是O(n)。

五、扩展

由于单向链表实现的LRU算法查找、添加和删除的时间复杂度为O(n)，效率低，所以一般都使用散列表+链表的方式实现LRU算法，通过散列表查找数据O(1)的时间复杂度来提高LRU的效率。如Java中的LinkedHashMap就是使用散列表+双向链表这两种数据结构组合实现的。

数据库

文章转载自大数据记事本，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

单向链表实现LRU缓存淘汰算法

评论