带有过期时间的LRU实现（Java版）

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

创新互联专注于北仑网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供北仑营销型网站建设，北仑网站制作、北仑网页设计、北仑网站官网定制、微信平台小程序开发服务，打造北仑网络公司原创品牌,更为您提供北仑网站排名全网营销落地服务。

一、什么是LRU

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

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

解决方案：利用链表加HashMap

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

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

OK，下面我们就开始实现：

二、代码实现

1、定义节点

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

2、LRU实现

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

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

3、过期清除线程方法

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

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

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

4、set方法

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

5、get方法

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

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

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

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

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

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

网页题目：带有过期时间的LRU实现（Java版）
网站链接：http://www.shufengxianlan.com/qtweb/news14/153664.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

微信小程序知识

各行业网站

成都网站制作　　 　重庆服务器托管　　 　渠县网站建设　　 　移动网站建设　　 　四川内江电信机房　　 　成都企业网站建设公司　　 　成都机柜租用　　 　网站SEO优化排名　　 　400电话办理　　 　高端网站建设　　 　网站维护报价　　 　广汉长尔科技　　 　绵阳服务器托管　　 　香港服务器空间　　 　橡塑保温管　　 　全网营销推广　　 　彭州做网站　　 　小程序开发公司　　 　眉山服务器托管　　 　雅安主机托管