很久以前学操作系统的时候就看到了这个算法，后来越看越多，以至于刷经的时候也看到了。总结一下：1.什么是LRULRU全称是LeastRecentlyUsed，意思是最近最长时间没有被使用。也就是说：如果一条数据在最近一段时间内没有被使用过，那么以后被使用到的几率就比较小了。通常的使用场景是缓存，比如操作系统中的页面置换算法。实现的方案有很多，看了很多博客，大部分都给了四五个。为了简洁起见，这里只给出一个，有一个过期时间。其他的实现都是类似的，就交给聪明的你吧！！解决方法：使用链表加HashMap，每次取一个新的数据，先判断map中是否包含，如果有则移到队头，如果没有则新建一个节点，然后放入即可。对于有过期时间的函数，只需要给每个节点放一个过期时间，只要到了这个时间就直接删除。还有一个问题：在多线程环境下要加锁。为了保证锁的灵活性，我们使用ConcurrentHashMap。OK，下面开始实现：2.代码实现1.定义节点//这个Node使用了HashMap类中的每个节点NodeimplementsComparable{privateStringkey;privateObjectvalue;privatelongexpireTime;//注意过期时间是一个时间点，这样as11:11publicNode(Stringkey,Objectvalue,longexpireTime){this.value=value;this.key=key;this.expireTime=expireTime;}//根据过期时间排序@OverridepublicintcompareTo(Nodeo){longr=this.expireTime-o.expireTime;if(r>0)return1;if(r<0)return-1;return0;}}2.LRU实现publicclassLRU{//变量1：用于设置清除过期数据的线程池privatestaticScheduledExecutorServiceswapExpiredPool=newScheduledThreadPoolExecutor(10);//变量2：用户存储数据，为了保证线程安全，ConcurrentHashMapprivateConcurrentHashMapcache=newConcurrentHashMap<>(1024);//变量3：保存最新的过期数据，带最小过期时间数据排在队列pr前面ivatePriorityQueueexpireQueue=newPriorityQueue<>(1024);//构造方法：只要有缓存，过期清除线程就会开始工作publicLRU(){swapExpiredPool.scheduleWithFixedDelay(newExpiredNode(),3,3,TimeUnit.SECONDS);}//和代码。......}现在我们定义了几个变量，然后就是构造方法，也就是说只要启动了LRU，就会开始清零。清除的线程是ExpiredNode。我们来看一下：3.过期清除线程方法这个方法也就是ExpiredNode，在LRU中算是一个内部类。publicclassExpiredNodeimplementsRunnable{@Overridepublicvoidrun(){//第一步：获取当前时间longnow=System.currentTimeMillis();while(true){//第二步：从过期队列中弹出第一个元素，如果不存在,ornot如果过期，则返回Nodenode=expireQueue.peek();if(node==null||node.expireTime>now)return;//第三步：当过期时，从缓存中删除，弹出缓存从队列中。remove(node.key);expireQueue.poll();}//这个过程是while(true)，一直在进行判断和删除操作}}知道了过期的清除方法，我们来看看如何添加数据。4.Set方法publicObjectset(Stringkey,Objectvalue,longttl){//第一步：获取过期时间点longexpireTime=System.currentTimeMillis()+ttl;//第二步：新建节点NodenewNode=newNode(key,value,expireTime);//第三步：如果缓存中有东西，则覆盖，如果没有，则添加新的，同时也要添加过期时间队列Nodeold=cache.put(key,newNode);expireQueue.add(newNode);//没有。第四步：如果key有数据，从过期时间队列中删除if(old!=null){expireQueue.remove(old);returnold.value;}returnnull;}5.get方法比较简单。直接拿就行了。publicObjectget(Stringkey){//第一步：直接从缓存中获取，注意这个缓存是一个HashMapNode=cache.get(key);//第二步：如果n为空，则返回null，如果不为空，则返回对应的valuereturnn==null?null:n.value;}注意上面的345个代码都是存放在LRU中的。我们已经知道到期时间。其实我们就是加了一个过期时间队列和一个过期清零线程。清空时用while(true)判断队头是否过期，再判断是否返回清空。设置方法时，将新节点添加到队列中并删除旧节点。而我们使用ConcurrentHashMap来保证线程安全。本文转载自微信公众号“愚公要移山”，可通过以下二维码关注。转载本文请联系愚公想移山公众号。OK，今天的代码就先写到这里吧。
