[Leetcode] LRU Cache 最近使用缓存

Render 发布于2019-08-14 12:31 / 3108人阅读

摘要：但是哈希表无序的，我们没办法在缓存满时，将最早更新的元素给删去。所以双向链表是最好的选择。我们用双向链表实现一个队列用来记录每个元素的顺序，用一个哈希表来记录键和值的关系，就行了。

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. 
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

双向链表加哈希表 复杂度

时间 Get O(1) Set O(1) 空间 O(N)

思路

缓存讲究的就是快，所以我们必须做到O(1)的获取速度，这样看来只有哈希表可以胜任。但是哈希表无序的，我们没办法在缓存满时，将最早更新的元素给删去。那么是否有一种数据结构，可以将先进的元素先出呢？那就是队列。所以我们将元素存在队列中，并用一个哈希表记录下键值和元素的映射，就可以做到O(1)获取速度，和先进先出的效果。然而，当我们获取一个元素时，还需要把这个元素再次放到队列头，这个元素可能在队列的任意位置，可是队列并不支持对任意位置的增删操作。而最适合对任意位置增删操作的数据结构又是什么呢？是链表。我可以用链表来实现一个队列，这样就同时拥有链表和队列的特性了。不过，如果仅用单链表的话，在任意位置删除一个节点还是很麻烦的，要么记录下该节点的上一个节点，要么遍历一遍。所以双向链表是最好的选择。我们用双向链表实现一个队列用来记录每个元素的顺序，用一个哈希表来记录键和值的关系，就行了。

注意

这题更多的是考察用数据结构进行设计的能力，再写代码时尽量将子函数拆分出来，先写个整体的框架。

移出链表最后一个节点时，要记得在链表和哈希表中都移出该元素，所以节点中也要记录Key的信息，方便在哈希表中移除

代码

public class LRUCache {
    
    int size;
    int capacity;
    ListNode tail;
    ListNode head;
    Map map;
    
    public LRUCache(int capacity) {
        this.head = new ListNode(-1,-1);
        this.tail = new ListNode(-1,-1);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
        this.capacity = capacity;
        this.map = new HashMap();
    }
    
    public int get(int key) {
        ListNode n = map.get(key);
        if(n != null){
            moveToHead(n);
            return n.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        ListNode n = map.get(key);
        if(n == null){
            n = new ListNode(value, key);
            attachToHead(n);
            size++;
        } else {
            n.val = value;
            moveToHead(n);
        }
        // 如果更新节点后超出容量，删除最后一个
        if(size > capacity){
            removeLast();
            size--;
        }
        map.put(key, n);
    }
    
    // 将一个孤立节点放到头部
    private void attachToHead(ListNode n){
        n.next = head.next;
        n.next.prev = n;
        head.next = n;
        n.prev = head;
    }
    
    // 将一个链表中的节点放到头部
    private void moveToHead(ListNode n){
        n.prev.next = n.next;
        n.next.prev = n.prev;
        attachToHead(n);
    }
    
    // 移出链表最后一个节点
    private void removeLast(){
        ListNode last = tail.prev;
        last.prev.next = tail;
        tail.prev = last.prev;
        map.remove(last.key);
    }
    
    public class ListNode {
        ListNode prev;
        ListNode next;
        int val;
        int key;
        public ListNode(int v, int k){
            this.val = v;
            this.prev = null;
            this.next = null;
            this.key = k;
        }
    }
}

云服务器服务器托管最近最多使用算法最近最少使用算法java实现最近最久未使用算法博客最近最久未使用算法程序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64530.html

剑指offer/LeetCode146/LintCode134_LRU缓存实现

摘要：剑指缓存实现声明文章均为本人技术笔记，转载请注明出处解题思路缓存两种功能获取的对应，不存在返回版本版本设置缓存已满，删除最近最久未被使用的节点，添加新节点进缓存缓存未满，节点存在，修改节点不存在，添加新节点进缓存解题思路由于缓存插入和删除剑指offer/LeetCode146/LintCode134_LRU缓存实现声明文章均为本人技术笔记，转载请注明出处[1] https://s...

you_De 2019-08-14 18:08 评论0 收藏0
力扣(LeetCode)146

摘要：当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。但是无法保证是，也无法保证更新数据时是，因为这两个操作必然要遍历队列。因为可以通过来判断是否有这个节点。题目地址：https://leetcode-cn.com/probl...题目描述：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获...

zr_hebo 2019-08-16 15:22 评论0 收藏0
笔记｜缓存

摘要：缓存算法我是，我会统计每一个缓存数据的使用频率，我会把使用最少的缓存替换出缓存区。浏览器就是使用了我作为缓存算法。在缓存系统中找出最少最近的对象是需要较高的时空成本。再来一次机会的缓存算法，是对的优化。直到新的缓存对象被放入。缓存什么是缓存？ showImg(https://segmentfault.com/img/bVusZg); 存贮数据（使用频繁的数据）的临时地方，因为取原始...

elliott_hu 2019-08-06 13:15 评论0 收藏0
NPM酷库：lru-cache 基于内存的缓存管理

摘要：酷库，每天两分钟，了解一个流行库。而直接将数据保存在程序变量中，最经济快捷。但是这样就会带来一些其他问题，比如缓存更新缓存过期等。用于在内存中管理缓存数据，并且支持算法。可以让程序不依赖任何外部数据库实现缓存管理。 NPM酷库，每天两分钟，了解一个流行NPM库。为了优化程序性能，我们常常需要奖数据缓存起来，根据实际情况，我们可以将数据存储到磁盘、数据库、redis等。但是有时候要缓...

Yumenokanata 2019-08-06 13:29 评论0 收藏0