Skip to main content

146. LRU 缓存


请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
实现 LRUCache 类：
  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4



 




提示：


    

  • 1 <= capacity <= 3000
    • 

  • 0 <= key <= 10000
    • 

  • 0 <= value <= 105
    • 

  • 最多调用 2 * 105 次 get 和 put
    • 




解决办法


    

  1. 先搞懂什么是LRU
    2. 

  2. 时间复杂度的要求
    3. 



什么是LRU


一种页面缓存管理机制,类似图书馆的最近热门读书榜单,热门的书在前面,当有新的热门的书出现时,旧的相较与新书,不太热门的书就会淘汰出榜单


时间复杂度要求


当数据量n时,程序运行时间的“增长速度”有多快。 如果“增长速度”这个词还是有点抽象，你可以把它理解为“工作量的膨胀率”。




假设你是一个搬运工，老板给你安排了任务。而“增长速度”指的不是你搬一趟要多久，而是当任务量翻倍时，你累倒的速度有多快。


    

  1. O(1)：老板让你去拿一个快递不管快递站里有 10 件快递还是 10,000 件快递，你手里有取件码，进去直接拿了就走。
增长速度： 零增长。即便快递站扩建成了物流园，你拿快递的体力消耗依然是一份。
    2. 

  2. O(n)：老板让你去数一排苹果，如果桌上有 10 个苹果，你数 10 下；如果桌上有 100 个苹果，你得数 100 下。
增长速度： 线性增长。苹果增加 10 倍，你的体力消耗就增加 10 倍。
    3. 





用java解决LRU


1. 核心思路：寻找“完美的搭档”


设计LRU的难点在与在O(1)的时间复杂度内同时解决数据的 增、删、查 的操作，核心的思想就是借助高效的数据结构完成目标。且单一的数据结构完全不能满足要求（为什么？），所以我们需要结合两种数据结构完成要求


    

  1. hashmap 哈希表： 它的查找效率是O(1),但是它并不是有序的,且无法知道最近使用的时间
    2. 

  2. Doubly Linked List 双向链表: 它的插入和删除节点是O(1) (前提是已经知道节点的位置).我们可以约定: 靠近头部的节点是最近使用的,靠近尾部的节点是最久没有使用的。（用这个数据结构来帮助管理）
    3. 



2.现实的模型






ps: 其实比喻成书榜也是对的




class LRUCache {

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

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

        public int getValue(){
            return this.value;
        }

        public void setValue(int value){
            this.value = value;
        }
    }

    private int size;
    private int cap;
    private Node head, tail;
    private HashMap<Integer, Node> cache;

    public LRUCache(int capacity) {
        this.cache = new HashMap<Integer, Node>();
        this.cap = capacity;
        this.size = 0;
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = tail;
        this.tail.prev = head;
    }



    public int get(int key) {
        Node node = cache.get(key);
        if (null == node) return -1;
        rmAndMoveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        // get
        Node node = cache.get(key);
        // null?
        if(null == node){
            // isAdd
            node = new Node(key,value);
            cache.put(key,node);
            size++;
            // flush new node index
            addNodeTohead(node);
            // overCap?
            if(size > cap){
                // removeOldNode
                Node oldNode = tail.prev;
                rmNode(oldNode);
                cache.remove(oldNode.key);
                size--;
            // reflush cap;
            }
        }else{
            // not null;
            node.setValue(value);
            // setNode
            cache.put(key,node);
            // putItOnTop;
            rmAndMoveToHead(node);
        }
    }

    public void addNodeTohead(Node node){
        // head => .. => ?
        Node top = head.next;
        head.next = node;
        node.prev = head;

        top.prev = node;
        node.next = top;
    }

    public void rmAndMoveToHead(Node node){
        rmNode(node);
        addNodeTohead(node);
    }

    public void rmNode(Node node){
        // A => node => B
        // A => B
        Node A = node.prev;
        Node B = node.next;
        if (A != null) A.next = B;
        if (B != null) B.prev = A;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */



    
        

    


            

        

    


    


    



    

        

             Back to top