LRU 缓存淘汰算法

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

Least Recently Used(LRU) 是缓存淘汰一种常用的策略,内存满了则优先删除最久没被使用的数据。

LRU 算法的需求

  1. 接收一个参数 capacity 作为缓存的最大容量
  2. 实现一个函数 put() 添加数据到缓存
  3. 实现一个函数 get() 查询缓存中的数据
  4. 以上函数应该在 \(O(1)\) 的时间内完成

满足以上需求的数据结构 —— 哈希表 + 双向链表,通过哈希表快速定位到链表中的节点,然后完成添加、删除等操作。

LRU 算法的实现

节点定义

public class Node {
    public int key;
    public String data;
    public Node next;
    public Node prev;
    
    public Node(int key, String data) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

双向链表

public class MyLinkedList {
    private Node head;    // 头节点
    private Node tail;    // 尾节点
    private int size;
    
    public MyLinkedList() {
        this.head = new Node(-1, "head");
        this.tail = new Node(-1, "tail");
        
        head.next = tail;
        tail.prev = head;
        
        this.size = 0;
    }
    
     // 添加新的数据到缓存
     public void addLast(Node node) {
         node.prev = tail.prev;
         node.next = tail;
         tail.prev.next = node;
         tail.prev = node;
         
         this.size += 1;
     }
    
    // 删除缓存中的某项数据
    public void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        
        this.size -= 1;
    }
    
    // 缓存空间已满,删除最早未被使用的数据
    public Node removeFirst() {
        if (head.next == tail) {
            return null;
        }
        
        Node first = head.next;
        remove(first);
        
        return first;
    } 
    
    public int size() {
        return this.size;
    }
}

LRU Cache

目前使用的双向链表支持从尾部插入,即尾部为最新的数据,头部则是最久未被使用的数据。文章来源地址https://www.toymoban.com/news/detail-505252.html

public class LRUCache {
    private Map<Integer, Node> map;
    private MyLinkedList cache;
    private int capacity;
    
    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.cache = new MyLinkedList();
        this.capacity = capacity;
    }
    
    public String get(int key) {
        if (!map.containsKey(key)) {
            return null;
        }
        
        makeRecently(key);
        return map.get(key).data;
    }
    
    /**
     * 1. 判断 key 是否已存在于缓存,若已存在则更新对应的data,并设置为最新使用即添加到队尾
     * 2. 判断缓存空间是否已满,若已满则删除最久未使用的数据
     */
    public void put(int key, String data) {
        if (map.containsKey(key)) {
            deleteKey(key);
            addRecently(key, data);
            return;
        }
        
        // 缓存空间已满
        if (this.capacity == cache.size()) {
            removeLeastRecently();
        }
        
        addRecently(key, data);
    }
    
    private void addRecently(int key, String data) {
        Node node = new Node(key, data);
        cache.addLast(node);
        map.put(key, node);
    }
    
    private void makeRecently(int key) {
        Node node = map.get(key);
        cache.remove(node);
        cache.addLast(node);
    }
    
    private void deleteKey(int key) {
        Node node = map.get(key);
        cache.remove(node);
        map.remove(key);
    }
    
    /**
     * 删除最久未被使用的数据
     */
    private void removeLeastRecently() {
        Node node = cache.removeFirst();
        map.remove(node.key);
    }
}

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

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

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

相关文章

  • cache教程1.LRU 缓存淘汰策略

    这一节实现LRU算法,要理解明白其使用的数据结构。 Cache的缓存全部存储在内存中,内存是有限的,因此不可能无限制地添加数据。当占用内存超过了给定的内存大小时候,就需要从缓存中移除一条或多条数据了。我们肯定希望尽可能移除“没用”的数据,那如何判定数据“

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

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

    2024年01月23日
    浏览(45)
  • 数据结构与算法之LRU: 实现 LRU 缓存算法功能 (Javascript版)

    关于LRU缓存 LRU - Lease Recently Used 最近使用 如果内存优先,只缓存最近使用的,删除 ‘沉睡’ 数据 核心 api: get set 分析 使用哈希表来实现, O(1) 必须是有序的,常用放在前面,沉睡放在后面, 即:有序,可排序 这样 {} 不符合要求;Map是可以排序的,按照设置顺序 不用 Map 如何

    2024年02月06日
    浏览(53)
  • 面试遇到算法题:实现LRU缓存

    请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。 这是一道大厂面试高频出现的算法题,难度为⭐️⭐️⭐️,属于中等,老铁们来一起看看这个题该怎么解? 没有废话,翠花,上酸菜! 为了实现一个满足 LRU (最近最少使用)缓存约束的数据结构,我们需

    2024年04月25日
    浏览(40)
  • Python算法题集_LRU 缓存

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

    2024年02月21日
    浏览(41)
  • 【算法训练-模拟 一】模拟设计LRU缓存结构

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是LRU缓存结构设计,这类题目出现频率还是很高的,几乎所有大厂都常考。 当然面对这道题,首先要讲清楚LRU是干什么的 LRU(Least Recently Used)缓存结构是一种常见的缓存管理策略, 用于

    2024年02月10日
    浏览(50)
  • LRU淘汰策略执行过程

    目录 1 介绍 2 Redis内存淘汰策略 2.1 设置过期时间的淘汰策略 2.2 所有 key 的淘汰策略 3 LRU淘汰策略执行过程 4 算法实现 Redis无论是惰性删除还是定期删除,都可能存在删除不尽的情况,无法删除完全,比如每次删除完过期的 key 还是超过 25%,且这些 key 再也不会被客户端访问。

    2024年02月11日
    浏览(26)
  • 【golang项目-GeeCache】动手写分布式缓存 day1 - 实现LRU算法

    【go项目-geecache】动手写分布式缓存 - day1 - 实现LRU算法 【go项目-geecache】动手写分布式缓存 - day2 - 单机并发缓存 【go项目-geecache】动手写分布式缓存 - day3 - HTTP 服务端 【go项目-geecache】动手写分布式缓存 - day4 - 一致性哈希(hash) 【go项目-geecache】动手写分布式缓存 - day5 - 分布

    2023年04月20日
    浏览(36)
  • 缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

    CMU 15-445 (FALL 2022) Project #1 Task#2 LRU-K 替换策略详解实现,尽量提供思路,也可以为其他同学实现LRU-K算法做参考 参考文献:The LRU-K page replacement algorithm for database disk buffering (acm.org) 在网上都找不到其他参考,只有这一篇1993年的论文 LRU-K替换策略 LRU-K是LRU算法的一种衍生。强烈

    2023年04月12日
    浏览(35)
  • 初识Go语言25-数据结构与算法【堆、Trie树、用go中的list与map实现LRU算法、用go语言中的map和堆实现超时缓存】

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

    2024年02月12日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包