LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。
LRU算法的表现
实现LRU的方法
比较三种方法优劣:
对于第一种方法,需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是O(n)。对于第二种方法,链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。
LinkedHashMap的实现方案
LinkedHashMap继承于HashMap,来一张LinkedHashMap的结构图
LinkedHashMap的结构图
其中next是用于维护HashMap指定table位置上连接的Entry的顺序的,before、after是用于维护Entry插入的先后顺序的
LinkedHashMap底层就是用的HashMap加双链表实现的。实现LRU算法主要有两个注意的地方:
所以使用LinkedHashMap很简单的实现了LRU算法,代码如下。另外如果生产中使用的话,一定要记得线程安全加锁。
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> { // 定义缓存的容量 private int capacity; // 带参数的构造器 LRULinkedHashMap(int capacity){ // 第三个参数为accessOrder super(16,0.75f,true); // 传入指定的缓存最大容量 this.capacity=capacity; } // 实现LRU的关键方法,如果map里面的元素个数大于了缓存最大容量,则删除链表的顶端元素 @Override public boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size()>capacity; } }
更多内容,欢迎关注微信公众号:全菜工程师小辉~