LRU算法(JAVA实现)

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

一、算法介绍

最近最久未使用(Least Recently Used    LRU)算法是⼀种缓存淘汰策略,它是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。该算法的思路是,发生缺页中断时,将最近一段时间内最久未使用的页面置换出去。 从程序运行的原理来看,最近最久未使用算法是比较接近理想的一种页面置换算法,这种算法既充分利用了内存中页面调用的历史信息,又正确反映了程序的局部问题

虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。
有利就有弊,虚拟页式存储管理减少了进程所需的内存空间,却也带来了运行时间变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进行交换,由于外存的低速,这一步骤所花费的时间不可忽略。因而,采取尽量好的交换算法以减少读取外存的次数,也是相当有意义的事情。

二、基本原理

假设 序列为 4 3 4 2 3 1 4 2
物理块有3个
4调入内存 4
3调入内存 3 4
4调入内存 4 3
2调入内存 2 4 3
3调入内存 3 2 4
1调入内存 1 3 2(因为最少使用的是4,所以丢弃4)
4调入内存 4 1 3(原理同上)
2调入内存 2 4 1

规律就是,如果新存入或者访问一个值,则将这个值放在队列开头。如果存储容量超过上限cap,那么删除队尾元素,再存入新的值。

我们下面通过一个简单的存储int的方式来实现LRU cache,实现put和get功能。

三、数据结构

⾸先要接收⼀个参数作为缓存的最⼤容量, 然后实现两个 API, ⼀个是 put(key, val) ⽅法存⼊键值对,get(key) ⽅法获取 key 对应的 val, 如果 key 不存在则返回null,get 和 put ⽅法必须都是 O(1) 的时间复杂度。

因此LRU cache 的数据结构的必要的条件: 查找快, 插⼊快, 删除快, 有顺序之分。那么, 什么数据结构同时符合上述条件呢? 哈希表查找快, 但是数据⽆固定顺序; 链表有顺序之分, 插⼊删除快, 但是查找慢。 所以结合⼀下, 形成⼀种新的数据结构: 哈希链表。如下图所示:

java lru,操作系统,算法

四、算法细节

新插入的元素或者最新查询的元素要放到链表的头部,对于长时间未访问的元素要放到链表尾部,所以每次插入或者查询都需要维护链表中元素的顺序。

使用哈希表的原因是查询时间复杂度为O(1),使用双向链表的原因是对于删除和插入操作时间复杂度为O(1)。

其中哈希表中存储的 key 为 K,value 为 Node<K,V> 的引用,双向链表存储的元素为Node<K,V>的引用.

put 方法是线程安全方法,定义如下所示:

public synchronized void put(K key,V value)

对于put操作:

①首先判断缓存中 元素 K 是否存在,如果存在,则把链表中的元素Node<K, V>删除,map中的数据<K, Node<K, V> >不用删除,再在链表头部插入元素,并更新map,直接返回即可 ;

②缓存不存在,并且缓存没有满的话,直接把元素插入链表的表头,缓存满了的话移除表尾元素(最旧未访问元素),将元素K插入表头,增加map中的<K, Node<K, V>>, 更新map。

get 方法是线程安全方法,定义如下所示:

public synchronized V get(K key)

对于get操作:

首先要判断 缓存中(map)是否存在,如果存在则把该节点删除并在链表头部插入该元素并更新map 返回当前元素即可,如果map不存在 则直接返回null;文章来源地址https://www.toymoban.com/news/detail-693752.html

五、算法实现

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在,先通过哈希表定位,再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在,创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量,删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

六、总结

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

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

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

相关文章

  • 操作系统:用C语言模拟先进先出的算法(FIFO)、最久未使用算法(LRU)、改进的Clock置换算法的命中率。

      通过请求页面式存储管理中页面置换算法设计,了解存储技术的特点,掌握请求页式存储管理的页面置换算法。 用程序实现生产者——消费者问题,将指令序列转换为用户虚存中的请求调用页面流。 具体要求: l页面大小为1K l用户内存容量为4页到40页 l用户外存的容量为

    2024年02月03日
    浏览(49)
  • LRU算法(JAVA实现)

    最近最久未使用 (Least Recently Used    LRU)算法是⼀种缓存淘汰策略,它是大部分操作系统为 最大化页面命中率 而广泛采用的一种页面置换算法。该算法的思路是,发生缺页中断时,将最近一段时间内最久未使用的页面置换出去。 从程序运行的原理来看,最近最久未使用算

    2024年02月10日
    浏览(31)
  • 操作系统--磁盘调度算法(FCFSSSTFSCANCSCAN)Java实现

    一、先来先服务算法(FCFS) 根据进程请求访问磁盘的先后次序进行调度。 二、最短时间优先算法(SSTF) 选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。 三、扫描算法(SCAN) 在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作

    2024年02月08日
    浏览(43)
  • 页面置换算法模拟实现-操作系统课程设计基于Java

    存储管理的主要功能之一是合理的分配空间,请求页式存储管理是一种常用的虚拟存储管理技术。在地址映射过程中,若在页表中发现所要访问的页面不在内存,则产生中断,当发生中断时,系统必须在内存选择一个页面移出内存,调用页面置换算法,以便为调入新的页面让

    2024年02月07日
    浏览(42)
  • 操作系统银行家算法(JAVA/Python/C#/JavaScript/C/C++)代码实现

    银行家算法是一种资源分配和死锁避免算法,它通过模拟所有资源的预定最大可能数量的分配来测试安全性,然后进行“s状态”检查以测试可能的活动,然后决定是否应该允许继续分配。 Banker’s algorithm 之所以叫“银行家算法”,是因为它在银行系统中被用来检查贷款是否

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

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

    2024年02月06日
    浏览(53)
  • Go实现LRU算法

      LRU是内存淘汰策略,LRU (Least recently used:最近最少使用)算法在缓存写满的时候,会根据所有数据的访问记录,淘汰掉未来被访问几率最低的数据。也就是说该算法认为,最近被访问过的数据,在将来被访问的几率最大。 那LRU使用什么实现的呢?双链表的话,那查询的

    2024年01月25日
    浏览(26)
  • 面试遇到算法题:实现LRU缓存

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

    2024年04月25日
    浏览(40)
  • LRU页面置换算法(C语言实现)

    1 、实验目的 ( 1 )熟悉虚拟存储器页面置换过程; ( 2 )通过编写和调试页面置换算法的模拟程序以加深对页面置换算法的理解; ( 3 )掌握 LRU 算法的原理; ( 4 )熟悉 OPT 和 FIFO 页面置换算法原理。 2 、 实验要求        编写并调试一个页面置换模拟程序,采用 LR

    2024年02月11日
    浏览(31)
  • 操作系统实验—进程调度算法(java)

    目录 文章目录 前言 一、实验原理 二、实验步骤 1.创建PCB类 2.创建创建类 3.设计主窗口类 4.调度界面函数 5.算法类及其调度算法通用函数 6.进程调度算法函数 总结 操作系统实验1:进程调度算法,步骤3、4在一个类中,步骤5、6在一个类中。 (1)先到先服务调度算法:按照进程提

    2024年02月04日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包