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

一、什么是LRU

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

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

解决方案：利用链表加HashMap

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

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

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

二、代码实现

1、定义节点

2、LRU实现

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

3、过期清除线程方法

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

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

4、set方法

5、get方法

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

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

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

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