LRU缓存机制

LRU缓存机制

前言

LRU(Least Recently Used)即最近最少使用、最近最久未使用,是一种缓存解决方案。

缓存思想在计算机科学中应用广泛,其核心是以空间换时间,实现方式主要采用特定的数据结构,在计算机存储层次结构中,低一层的存储器都可以看做是高一层的缓存。比如Cache是内存的缓存,内存是硬盘的缓存,硬盘是网络的缓存等等。

第一次接触到LRU是在操作系统的课程上,在提到OS页面调度算法的时候提到的LRU页面置换算法,页面置换是基于时间和空间局部性原理的基础上,而缓存类似于LRU这样的缓存技术在这样的场景下得到应用。

LRU在数据库缓存中也有广泛应用,例如Redis缓存淘汰策略。在使用next.js的时候,访问页面时,为了加快访问速度也会用到。

LRU:如果一个数据最近没有被访问到,那么它将来被访问的几率也很小,也就是说当限定的内存空间已没有其他空间可用时,应该把最久没有访问到的数据去除掉。

img

LRU为了实现时间复杂度O(1),采用HashMap+双向链表的数据结构,实get和put操作,如下图所示。

LRU数据结构

Java中可以采用LinkedHashMap源实现LRU,Python中可以调用OrderedDict()实现。

例题 LeetCode146. LRU 缓存机制

Java实现

下面用是用Java实现的几种方式,分别是

调用Java的LinkedHashMap实现LRU

package LRU;

import java.util.*;

/**
 * @author Orust
 * @create 2021/5/24 16:07
 */

// 146. LRU 缓存机制: https://leetcode-cn.com/problems/lru-cache/
// LinkedHashMap源码中写道: This kind of map is well-suited to building LRU caches.
// put和get的时间复杂度均为O(1)
// 空间复杂度为O(capacity) capacity为LRU缓存大小
// 广泛应用与OS内存页面调度,Redis缓存淘汰策略

// 样例输入
// ["LRUCache_4","put","put","put","get","put","put","get","put","put","get","put","get","get","get","put","put","get","put","get"]
// [[10],[7,28],[7,1],[8,15],[6],[10,27],[8,10],[8],[6,29],[1,9],[6],[10,7],[1],[2],[13],[8,30],[1,5],[1],[13,2],[12]]
// 预期结果
// [null,null,null,null,-1,null,null,10,null,null,29,null,9,-1,-1,null,null,5,null,-1]


// 调用Java的LinkedHashMap实现LRU

public class LRUCache {
    int capacity;
    LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<>();
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            int num = cache.remove(key);
            cache.put(key, num);
            return num;
        } else return -1;  // 未找到当前元素
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            cache.remove(key);
        } else if (cache.size() == capacity) {
            // cache.remove(cache.entrySet().iterator().next().getKey());
            cache.remove(cache.keySet().iterator().next());
        }
        cache.put(key, value);
    }

    public static void main(String[] args) {
        LRUCache obj = new LRUCache(10);
        obj.put(7, 28);
        obj.put(7, 1);
        obj.put(8, 15);
        System.out.println(obj.get(6));
        obj.put(10, 27);
        obj.put(8, 10);
        System.out.println(obj.get(8));
        obj.put(6, 29);
        obj.put(1, 9);
        System.out.println(obj.get(6));
        obj.put(10, 7);
        System.out.println(obj.get(1));
        System.out.println(obj.get(2));
        System.out.println(obj.get(13));
        obj.put(8, 30);
        obj.put(1, 5);
        System.out.println(obj.get(1));
        obj.put(13, 2);
        System.out.println(obj.get(12));
    }
}

HashMap + 定义双向链表 实现LRU

package LRU;

import java.util.*;

/**
 * @author Orust
 * @create 2021/5/24 16:18
 */

// HashMap + 定义双向链表 实现LRU

public class LRUCache_2 {
    int capacity;
    HashMap<Integer, Node> map;
    Node head;
    Node tail;

    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;

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

    public LRUCache_2(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            moveToHead(node);
            return node.value;
        } else return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            map.put(key, node);
            moveToHead(node);
        } else {
            if (map.size() == capacity)
                map.remove(popTail());
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
        }
    }

    private void addToHead(Node node) {
        if (tail == null) {  // 当前链表为空
            head = node;
            tail = node;
        } else {
            head.prev = node;
            node.next = head;
            node.prev = null;
            head = node;
        }
    }

    private void moveToHead(Node node) {
        if (node == head) return;  // 判断是否是头尾节点并删除节点
        node.prev.next = node.next;
        if (node == tail) tail = tail.prev;
        else node.next.prev = node.prev;
        addToHead(node);
    }

    private int popTail() {
        if (tail == null) throw new NullPointerException("NullPointerException!");
        int key = tail.key;
        if (tail == head) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        return key;
    }

    public static void main(String[] args) {
        LRUCache_2 obj = new LRUCache_2(10);
        obj.put(7, 28);
        obj.put(7, 1);
        obj.put(8, 15);
        System.out.println(obj.get(6));
        obj.put(10, 27);
        obj.put(8, 10);
        System.out.println(obj.get(8));
        obj.put(6, 29);
        obj.put(1, 9);
        System.out.println(obj.get(6));
        obj.put(10, 7);
        System.out.println(obj.get(1));
        System.out.println(obj.get(2));
        System.out.println(obj.get(13));
        obj.put(8, 30);
        obj.put(1, 5);
        System.out.println(obj.get(1));
        obj.put(13, 2);
        System.out.println(obj.get(12));
    }
}

HashMap + 定义静态内部类 MyLinkedList + 泛型 实现LRU

package LRU;

import java.util.*;

/**
 * @author Orust
 * @create 2021/5/24 17:03
 */

// HashMap + 定义静态内部类MyLinkedList + 泛型 实现LRU

public class LRUCache_3<K, V> {
    int capacity;
    Map<K, Node<K, V>> map = new HashMap<>();
    MyLinkedList<K, V> cache = new MyLinkedList<>();

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

    public V get(K key) {
        if (map.containsKey(key)) {
            Node<K, V> node = map.get(key);
            cache.moveToHead(node);
            return node.value;
        } else return null;
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node<K, V> node = map.get(key);
            node.value = value;
            map.put(key, node);
            cache.moveToHead(node);
        } else {
            if (map.size() == capacity)
                map.remove(cache.popTail());
            Node<K, V> node = new Node<>(key, value);
            map.put(key, node);
            cache.addToHead(node);
        }
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private static class MyLinkedList<K, V> {
        Node<K, V> head;  // head是最近使用的数据
        Node<K, V> tail;

        private void addToHead(Node<K, V> node) {
            if (tail == null) {  // 当前链表为空
                head = node;
                tail = node;
            } else {
                head.prev = node;
                node.next = head;
                node.prev = null;
                head = node;
            }
        }

        private void moveToHead(Node<K, V> node) {
            if (node == head) return;  // 判断是否是头尾节点并删除节点
            node.prev.next = node.next;
            if (node == tail) tail = tail.prev;
            else node.next.prev = node.prev;
            addToHead(node);
        }

        private K popTail() {
            if (tail == null) throw new NullPointerException("NullPointerException!");
            K key = tail.key;
            if (tail == head) {
                head = null;
                tail = null;
            } else {
                tail = tail.prev;
                tail.next = null;
            }
            return key;
        }
    }


    public static void main(String[] args) {
        LRUCache_3<String, Integer> obj = new LRUCache_3<>(10);
        obj.put("7", 28);
        obj.put("7", 1);
        obj.put("8", 15);
        System.out.println(obj.get("6"));
        obj.put("10", 27);
        obj.put("8", 10);
        System.out.println(obj.get("8"));
        obj.put("6", 29);
        obj.put("1", 9);
        System.out.println(obj.get("6"));
        obj.put("10", 7);
        System.out.println(obj.get("1"));
        System.out.println(obj.get("2"));
        System.out.println(obj.get("13"));
        obj.put("8", 30);
        obj.put("1", 5);
        System.out.println(obj.get("1"));
        obj.put("13", 2);
        System.out.println(obj.get("12"));
    }
}

在tomcat6.x版本中被使用的LRU实现方式

package LRU;

import java.util.*;

/**
 * @author Orust
 * @create 2021/5/25 10:53
 */

// 文章链接 https://www.iteye.com/blog/flychao88-1977653
// 在tomcat6.x版本中被使用的LRU实现方式

public class LRUCache_4 {
阅读全文 »

模糊聚类与WRSN

模糊聚类与WRSN

模糊关系

​ 现实世界中,事物之间存在着这样或那样的关系.一些是界限非常明确的关系,如“父子关系”、“大小关系”等等,可以简单地用“是”与“否”或者“1”与“0”来刻画.而更多的则是界限不明显的关系,如“朋友关系”、“相近关系”、“相像关系”等.对于这类关系再用简单的“是”与“否”或者“1”与“0”来刻画显然是不合适的,必须用模糊集理论来进行描述,这就是模糊关系.

阅读全文 »

二叉树遍历系列总结

这里分别给出了三种二叉树的遍历方法与N叉树的前序遍历,及其时空复杂度

1:递归:直接递归版本、针对不同题目通用递归版本(包括前序、中序、后序)

2:迭代:最常用版本(常用主要包括前序和层序,即【DFS和BFS】)、【前中后】序遍历通用版本(一个栈的空间)、【前中后层】序通用版本(双倍栈(队列)的空间)

阅读全文 »

并查集的学习与总结

前言

前两天在刷LeetCode每日一题的时候连续遇到了两天有并查集标签的题目,从来没有学过这个算法的我只能硬着头皮去看题,看评论区和题解区大家用并查集都很容易的解决了题目,群里也在讨论一些类似于并查集的优化呀什么的,而我都不知道这是个什么。于是下定决心要学一下这个“神秘的并查集”。

查找资料

阅读全文 »

Chrome浏览器的正确打开方式

新的一周的下午,拿起新的一篇论文,有点看不下去。打开了我的Gridea......
谨以此篇文章记录自己在chrome浏览器摸索的经验和技巧。
以下技巧和经验仅作交流和学习使用,请勿用作其他用途。

阅读全文 »

Hello Gridea

👏 欢迎使用 Gridea
✍️ Gridea 一个静态博客写作客户端。你可以用它来记录你的生活、心情、知识、笔记、创意... ...

阅读全文 »