高薪必备：如何实现带有过期时间的LRU？（java版）

拼搏现实的明天。 2023-03-13 13:22 53阅读 0赞

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

**一、什么是LRU**

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

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

**解决方案：利用链表加HashMap**

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

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

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

**二、代码实现**

**1、定义节点**

//这个Node对用HashMap中每一个节点
    class Node implements Comparable<Node> { 
        private String key;
        private Object value;
        private long expireTime;//注意这个过期时间是一个时间点，如11点11分
        public Node(String key, Object value, long expireTime) { 
            this.value = value;
            this.key = key;
            this.expireTime = expireTime;
        }
        //按照过期时间进行排序
        @Override
        public int compareTo(Node o) { 
            long r = this.expireTime - o.expireTime;
            if (r > 0)  return 1;
            if (r < 0) return -1;
            return 0;
        }
    }

**2、LRU实现**

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

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

**3、过期清除线程方法**

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

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

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

**4、set方法**

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

**5、get方法**

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

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

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

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NERERMTEw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230312/45df7ea7bad74a3d89a999277d20cddf.png