文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

带有过期时间的LRU实现(Java版)

2024-12-11 18:11

关注

在很早之前学操作系统的时候见过这个算法,后来见到的越来越多,以至于刷面经的时候也看到了,总结一下:

一、什么是LRU

LRU全称是Least Recently Used,即最近最久未使用的意思。也就是说:如果一个数据在最近一段时间没有被使用,将来被使用的机会也比较小。

通常的使用场景就是缓存,比如说操作系统中的页面置换算法。实现的方案有很多,我看了很多博客,大多是给了四五种。这里为了简洁,只给出一种,是带有过期时间的。其他的实现类似,就交给聪明的你吧!!

解决方案:利用链表加HashMap

每次来一个新数据,首先判断map中是否含有,有的话就移动到队头,没有的话就新建一个节点,然后放进来就好,对于带过期时间的功能,只需要为每一个节点放一个过期时间,只要到了这个时间就直接删除即可。

 

还有一个问题:多线程环境下应该加锁,为了保证锁的灵活性,我们使用ConcurrentHashMap。

OK,下面我们就开始实现:

二、代码实现

1、定义节点

  1. //这个Node对用HashMap中每一个节点 
  2. class Node implements Comparable { 
  3.     private String key
  4.     private Object value; 
  5.     private long expireTime;//注意这个过期时间是一个时间点,如11点11分 
  6.     public Node(String key, Object value, long expireTime) { 
  7.         this.value = value; 
  8.         this.key = key
  9.         this.expireTime = expireTime; 
  10.     } 
  11.     //按照过期时间进行排序 
  12.     @Override 
  13.     public int compareTo(Node o) { 
  14.         long r = this.expireTime - o.expireTime; 
  15.         if (r > 0)  return 1; 
  16.         if (r < 0) return -1; 
  17.         return 0; 
  18.     } 

2、LRU实现

  1. public class LRU { 
  2.     // 变量1:用于设置清除过期数据的线程池 
  3.     private static ScheduledExecutorService swapExpiredPool  
  4.                   = new ScheduledThreadPoolExecutor(10); 
  5.     // 变量2:用户存储数据,为了保证线程安全,使用了ConcurrentHashMap 
  6.     private ConcurrentHashMap cache = new ConcurrentHashMap<>(1024); 
  7.     // 变量3:保存最新的过期数据,过期时间最小的数据排在队列前 
  8.     private PriorityQueue expireQueue = new PriorityQueue<>(1024); 
  9.     // 构造方法:只要有缓存了,过期清除线程就开始工作 
  10.     public LRU() { 
  11.         swapExpiredPool.scheduleWithFixedDelay(new ExpiredNode(), 3,3,TimeUnit.SECONDS); 
  12.     } 
  13.     //还有代码。。。。。。。 

现在我们定义了几个变量,然后还有一个构造方法,意思是只要启动了这个LRU,就开始清除。清除的线程是ExpiredNode。我们来看一下:

3、过期清除线程方法

这个方法也就是ExpiredNode,当做一个内部类在LRU中。

  1. public class ExpiredNode implements Runnable { 
  2.         @Override 
  3.         public void run() { 
  4.             // 第一步:获取当前的时间 
  5.             long now = System.currentTimeMillis(); 
  6.             while (true) { 
  7.                 // 第二步:从过期队列弹出队首元素,如果不存在,或者不过期就返回 
  8.                 Node node = expireQueue.peek(); 
  9.                 if (node == null || node.expireTime > now)return
  10.                 // 第三步:过期了那就从缓存中删除,并且还要从队列弹出 
  11.                 cache.remove(node.key); 
  12.                 expireQueue.poll(); 
  13.             }// 此过程为while(true),一直进行判断和删除操作 
  14.         } 
  15.     } 

现在知道了过期清除方法,下面看看如何添加数据。

4、set方法

  1. public Object set(String key, Object value, long ttl) { 
  2.         // 第一步:获取过期时间点 
  3.         long expireTime = System.currentTimeMillis() + ttl; 
  4.         // 第二步:新建一个节点 
  5.         Node newNode = new Node(key, value, expireTime); 
  6.         // 第三步:cache中有的话就覆盖,没有就添加新的,过期时间队列也要添加 
  7.         Node old = cache.put(key, newNode); 
  8.         expireQueue.add(newNode); 
  9.         // 第四步:如果该key存在数据,还要从过期时间队列删除 
  10.         if (old != null) { 
  11.             expireQueue.remove(old); 
  12.             return old.value; 
  13.         } 
  14.         return null
  15.     } 

5、get方法

这个方法就比较简单了,直接获取即可。

  1. public Object get(String key) { 
  2.     //第一步:从cache直接获取,注意这个cache是一个HashMap 
  3.     Node n = cache.get(key); 
  4.     //第二步:如果n为空那就返回为null,不为空就返回相应的值 
  5.     return n == null ? null : n.value; 

注意以上345的代码都存放在LRU中。

过期时间的我们已经知道了,其实就是添加了一个过期时间队列,和一个过期清除的线程,清除的时候使用while(true)每次判断队列队首是否过期,然后判断是否返回和清除。设置方法的时候还要把新的node添加到queue,把旧的移除掉。而且我们使用了ConcurrentHashMap保证了线程安全。

本文转载自微信公众号「 愚公要移山」,可以通过以下二维码关注。转载本文请联系 愚公要移山公众号。

OK,今天的代码就先写到这。

 

来源:愚公要移山内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯