剑指offer/LeetCode146/LintCode134_LRU缓存实现

you_De 发布于2019-08-14 18:08 / 1420人阅读

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

剑指offer/LeetCode146/LintCode134_LRU缓存实现 声明

文章均为本人技术笔记，转载请注明出处
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

解题思路 LRU缓存两种功能：

get(key)：获取key的对应value，不存在返回-1

set(key, value)（lintcode版本）/put(key, value)（leetcode版本）：设置

缓存已满，删除最近最久未被使用的节点，添加新节点进缓存

缓存未满，

节点存在，修改value；

节点不存在，添加新节点进缓存；

解题思路

由于LRU缓存插入和删除操作频繁，使用双向链表维护缓存节点，

“新节点”：凡是被访问（新建/修改命中/访问命中）过的节点，一律在访问完成后移动到双向链表尾部，保证链表尾部始终为最“新”节点；

“旧节点”：保证链表头部始终为最“旧”节点，LRU策略删除时表现为删除双向链表头部；

从链表头部到尾部，节点访问热度逐渐递增

由于链表不支持随机访问，使用HashMap+双向链表实现LRU缓存；

HashMap中键值对：

双向链表：维护缓存节点CacheNode

注意点

使用双向链表时，时刻记得维护pre和next指针；

题目链接

lintcode 134: http://www.lintcode.com/zh-cn/problem/lru-cache/

leetcode 146: https://leetcode.com/problems/lru-cache/#/description

Java代码

/**
 * HashMap+双向链表实现LRU缓存
 * http://www.lintcode.com/zh-cn/problem/lru-cache/
 * https://leetcode.com/problems/lru-cache/#/description
 * @author yzwall
 */
import java.util.HashMap;

class Solution {
    private HashMap map;
    private int capacity;
    // head.next和tail.next指向链表头尾，包起来防止null
    private CacheNode head = new CacheNode(-1, -1);
    private CacheNode tail = new CacheNode(-1, -1);
    
    // 缓存节点
    private class CacheNode {
        int key, value;
        CacheNode pre, next;
        CacheNode(int key, int value) {
            this.key = key;
            this.value = value;
            this.pre = null;
            this.next = null;
        }
    }
    
    public Solution(int capacity) {
        this.map = new HashMap<>();
        this.capacity = capacity;
    }
    
    // 将已有节点或新建节点移动到链表尾部
    private void moveToTail(CacheNode target, boolean isNew) {
        // 尾部节点显然不需要移动
        if (target != tail.next) {
            if (!isNew) {
                // 修改旧节点的双向链表指针
                target.pre.next = target.next; 
                target.next.pre = target.pre;
            }
            // 添加节点到链表尾部
            tail.next.next = target;
            target.pre = tail.next;
            tail.next = target;
        }
    }
    
    // 命中节点添加到链表尾部，未命中返回-1
    public int get(int key) {
        if (map.containsKey(key)) {
            CacheNode target = map.get(key);
            // 将已有节点移动到链表尾部
            moveToTail(target, false);
            // 此时链表尾部tail.next = target，更新next指向null，防止出现环
            tail.next.next = null;
            return target.value;
        }
        return -1;
    }
    
    /**
     * 1. 节点命中，修改节点并移动到链表尾部tail.next
     * 2. 节点未命中，
     *    2.1 cache已满，删除链表头部head.next
     *    2.2 cache未满，新建节点并添加到链表尾部tail.next
     */
    public void set(int key, int value) {
        // cache中存在节点
        if (map.containsKey(key)) {
            CacheNode target = map.get(key);
            target.value = value;
            map.put(key, target);
            // 将访问过的已有节点移动到链表尾部
            moveToTail(target, false);
        } else if(map.size() < capacity) {    // cache未满，添加节点
            CacheNode newNode = new CacheNode(key, value);
            map.put(key, newNode);
            if (head.next == null) {
                head.next = newNode;
                newNode.pre = head;
                tail.next = newNode;
            } else {
                // 将新建节点移动到链表尾部
                moveToTail(newNode, true);
            }
        } else {    // cache已满，淘汰链表链表头部节点，新节点加入到链表尾部
            CacheNode newNode = new CacheNode(key, value);
            map.remove(head.next.key);
            map.put(key, newNode);
            // cache中只有一个元素
            if (head.next == tail.next) {
                head.next = newNode;
                tail.next = newNode;
            } else {    // cache中不止一个元素，删除头部
                head.next.next.pre = head; // 更新新头部.pre = head
                head.next = head.next.next;// 更新新头部
                // 将新建节点移动到链表尾部
                moveToTail(newNode, true);
            }
        }
    }
}

GPU云服务器云服务器 LintCode134_LRU lru用c语言实现剑指 cdn缓存如何实现

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

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

从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试 ...

tracymac7 2019-08-15 17:57 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试头条一面（Java+项目）头条...

wdzgege 2019-08-19 11:43 评论0 收藏0
一个线程安全的 lrucache 实现 --- 读 leveldb 源码

摘要：在阅读的源代码的时候，发现其中的类正是一个线程安全的实现，代码非常优雅。至此一个线程安全的类就已经全部实现，在中使用的缓存是，其实就是聚合多个实例，真正的逻辑都在类中。缓存是计算机的每一个层次中都是一个非常重要的概念，缓存的存在可以大大提高软件的运行速度。Least Recently Used(lru) cache 即最近最久未使用的缓存，多见与页面置换算法，lru 缓存算法在缓存的...

widuu 2019-08-06 13:30 评论0 收藏0
web技术分享| LRU 缓存淘汰算法

摘要：双向链表用于管理缓存数据结点的顺序，新增数据和缓存命中最近被访问的数据被放置在结点，尾部的结点根据内存大小进行淘汰。了解 LRU 之前，我们应该了解一下缓存，大家都知道计算机具有缓存内存，可以临时存储最常用的数据，当缓存数据超过一定大小时，系统会进行回收，以便释放出空间来缓存新的数据，但从系统中检索数据的成本...

graf 2021-11-24 09:39 评论0 收藏0
Vue的缓存算法—LRU算法

摘要：最近在看的源码，不得不说的是，的源码十分优雅简洁，下面就来分享下的缓存利用的算法算法。关于算法的具体流程，可以来看下这个，这个可视化过程，模拟了算法进行调度的过程。最近在看Vue的源码，不得不说的是，Vue的源码十分优雅简洁，下面就来分享下Vue的缓存利用的算法LRU算法。 LRU算法 LRU是Least recently used的简写，主要原理是根据历史访问记录来淘汰数据，说白了...

elina 2019-08-21 14:30 评论0 收藏0