LRU 缓存

这篇具有很好参考价值的文章主要介绍了LRU 缓存。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接

LRU 缓存

题目描述

LRU 缓存,算法TOP100,java,leetcode,数据结构,链表
LRU 缓存,算法TOP100,java,leetcode,数据结构,链表文章来源地址https://www.toymoban.com/news/detail-573178.html

注意点

  • 如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字
  • 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

解答思路

  • 如果想以O(1)的速度进行get,则需要将对应的key、value存到map中
  • 如果想以O(1)的速度进行put,又因为插入的时候可能由于空间已满需要将最久未使用的关键字,元素始终都在进行移动,所以需要使用链表来存储节点
  • 如果使用map存储key、value,链表中每个节点存储key、value,则在get某个节点需要将其移动到链表头部时查找该节点需要花费O(n)的时间,不满足题意,所以应该map存储的key为对应关键字的key,而存储的value应该是该key对应的链表节点

代码

class LRUCache {
    class DoublyLinkedList {
        int key;
        int value;
        DoublyLinkedList prev;
        DoublyLinkedList next;
        DoublyLinkedList() {}
        DoublyLinkedList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    int size;
    DoublyLinkedList head;
    DoublyLinkedList tail;
    Map<Integer, DoublyLinkedList> map;

    public LRUCache(int capacity) {
        size = capacity;
        map = new HashMap<>(capacity);
        head = new DoublyLinkedList();
        tail = new DoublyLinkedList();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DoublyLinkedList node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 将该节点移动到链表头部
        removeNode(node);
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DoublyLinkedList node = new DoublyLinkedList(key, value);
        // key在链表中已存在,只更新了value值,则直接对map进行更新即可,还要将新节点移动到链表头部
        if (map.containsKey(key)) {
            DoublyLinkedList oldNode = map.get(key);
            removeNode(oldNode);
            map.put(key, node);
            moveToHead(node);
            return;
        }
        // key在链表中不存在,且链表还有多余空间,则只需要将新节点插到链表头部
        if (map.size() < size) {
            moveToHead(node);
            map.put(key, node);
        } else {
            // key在链表中不存在,且链表已满,则需要删除链表尾,同时将新节点插到链表头部
            map.remove(tail.prev.key);
            removeNode(tail.prev);
            moveToHead(node);
            map.put(key, node);
        }
    }

    public void moveToHead(DoublyLinkedList node) {
        DoublyLinkedList tmp = head.next;
        head.next = node;
        node.prev = head;
        node.next = tmp;
        tmp.prev = node;
    }

    public void removeNode(DoublyLinkedList node) {
        DoublyLinkedList prevNode = node.prev;
        DoublyLinkedList nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }
}

关键点

  • map中存储的value为key对应的链表中的节点
  • 如果能成功get到值,则需要将该节点移动到链表的头部,移动时,还要删除链表中老位置的该节点
  • 在put时,如果此时链表和map中已经有该关键字,只是更新其value值,则需要更新其在链表中的节点值,同时将该节点移动到链表同步;如果没有该关键字但是链表空间足够,则只需要建一个新节点插到链表头部即可;如果没有该关键字且链表空间已满,则需要将尾部节点删掉,再将新节点插入到头部
  • 在增加和删除链表节点时同时也要对map中的相应值进行更新

到了这里,关于LRU 缓存的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 初识Go语言25-数据结构与算法【堆、Trie树、用go中的list与map实现LRU算法、用go语言中的map和堆实现超时缓存】

      堆是一棵二叉树。大根堆即任意节点的值都大于等于其子节点。反之为小根堆。   用数组来表示堆,下标为 i 的结点的父结点下标为(i-1)/2,其左右子结点分别为 (2i + 1)、(2i + 2)。 构建堆   每当有元素调整下来时,要对以它为父节点的三角形区域进行调整。 插入元素

    2024年02月12日
    浏览(59)
  • 【算法】用JAVA代码实现LRU 【缓存】【LRU】

    LRU(Least Recently Used)是一种常见的缓存淘汰策略,用于在缓存空间不足时确定哪些数据应该被淘汰。其基本原则是淘汰最近最少被访问的数据。 工作原理 : 最近使用优先 : LRU算法基于这样的思想:最近被使用的数据很可能在短时间内还会被使用,因此保留这些数据有助于

    2024年01月23日
    浏览(46)
  • 【设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构】

    LRU是Least Recently Used的缩写,意为最近最少使用。它是一种缓存淘汰策略,用于在缓存满时确定要被替换的数据块。LRU算法认为,最近被访问的数据在将来被访问的概率更高,因此它会优先淘汰最近最少被使用的数据块,以给新的数据块腾出空间。 如图所示: 先来3个元素进入

    2024年01月24日
    浏览(46)
  • 【设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构】

    LRU是Least Recently Used的缩写,意为最近最少使用。它是一种缓存淘汰策略,用于在缓存满时确定要被替换的数据块。LRU算法认为,最近被访问的数据在将来被访问的概率更高,因此它会优先淘汰最近最少被使用的数据块,以给新的数据块腾出空间。 如图所示: 先来3个元素进入

    2024年01月21日
    浏览(57)
  • 【LeetCode】146.LRU缓存

    请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。 实现  LRUCache  类: LRUCache(int capacity)  以  正整数  作为容量  capacity  初始化 LRU 缓存 int get(int key)  如果  key  存在于缓存中,则返回的值,否则返回  -1  。 void put(int key, int value)  如果

    2024年02月09日
    浏览(43)
  • LeetCode刷题---LRU缓存

    LRU是Least Recently Used的缩写,即最近最少使用,是一种内存管理算法,也可以用作缓存淘汰策略。 这种算法的核心思想是:如果数据最近被访问过,那么将来被访问的几率也更高。 因此,当内存或缓存容量有限,需要淘汰部分数据时,LRU算法会优先淘汰那些最长时间未被访问

    2024年02月22日
    浏览(38)
  • leetcode 146. LRU 缓存

             本题核心就是要将map中,最近最少操作的那个key给剔除掉,于是我们可以使用双端链表LinkedList 来维护每个元素的操作情况,最近操作的元素就将其移至表头,越久没操作的元素,自然就会沉到表尾。  一旦缓存满了,将表尾元素剔除即可。  java代码如下:

    2024年02月08日
    浏览(43)
  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(41)
  • 【LeetCode-中等题】146. LRU 缓存

    LRU缓存是什么:LRU缓存机制,你想知道的这里都有 实现 LRU 缓存算法 map —key存 integer value存链表节点 ListNode 存 next 和prev 引用 以及 存 key 和value 具体值 图解:官方图解 步骤: 定义一个自定义的双向链表节点类 DLinkedNode,该类包含 key 和 value 字段,并且具有 prev 和 next 指针

    2024年02月10日
    浏览(52)
  • 【LeetCode刷题-链表】--146.LRU缓存

    方法一:哈希表+双向链表 使用一个哈希表和一个双向链表维护所有在缓存中的键值对 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久使用的 哈希表即为普通的哈希映射,通过缓存数据的键映射到其在双向链表中的

    2024年02月05日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包