当前位置: 首页 > >

java 带超时时间lru_带有过期时间的LRU实现(java版)

发布时间:

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


一、什么是LRU


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


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


解决方案:利用链表加HashMap


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



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


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


二、代码实现


1、定义节点


//这个Node对用HashMap中每一个节点


class?Node?implements?Comparable{


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?


return?0;


}


}


2、LRU实现


public?class?LRU{


//?变量1:用于设置清除过期数据的线程池


private?static?ScheduledExecutorService?swapExpiredPool


=?new?ScheduledThreadPoolExecutor(10);


//?变量2:用户存储数据,为了保证线程安全,使用了ConcurrentHashMap


private?ConcurrentHashMap?cache?=?new?ConcurrentHashMap<>(1024);


//?变量3:保存最新的过期数据,过期时间最小的数据排在队列前


private?PriorityQueue?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,今天的代码就先写到这。







相关资源:最*最少使用cache,提取leveldb的lru cache部分,增加过期时间过期失效



友情链接: