前言
在看缓存的时候看到利用LinkedHashMap可以比较容易的实现LRU算法。
缓存
为了提高数据访问速度会使用到缓存,但是由于内存大小的限制，当存储的数据超过缓存容量的时候，需要对缓存的数据进行清理。一般缓存清理算法有FIFO淘汰最早数据、LRU剔除最近最少使用、和LFU剔除最近使用频率最低的数据几种。这里我们看看LRU算法。
LRU算法
LRU算法就是将最近最少用的缓存移除，让给最新使用的缓存。而往往最常读取的，也就是读取次数最多的，所以利用好LRU算法，我们能够提供对热点数据的缓存效率，能够提高缓存服务的内存使用率。
基于LinkedHashMap的实现
import java.util.LinkedHashMap;
import java.util.Map;
/**
* 简单用LinkedHashMap来实现的LRU算法的缓存
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LRUCache(int cacheSize) {
super(16, (float) 0.75, true);
this.cacheSize = cacheSize;
}
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cacheSize;
}
}
基于LinkedHashMap实现看上去看是很简单的,那么问题来了为什么LinkedHashMap能实现这样的一个算法呢?
LinkedHashMap
LinkedHashMap是HashMap的一个子类，在HashMap的数据结构上加上了一个双向链表，也就在HashMap的基础上实现有序性。根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。 当链表根据读取顺序时，每次被读取的数据会被挪动到尾端，那么表头就是最近最少使用的数据了，在数据超过缓存容量的时候表头数据移除掉就达到了LRU算法的目的了。
