LRU指的是最近不经常使用的。LRU缓存指的是当加入新元素时,如果缓存空间不够,需要清理掉原LRU中的一个元素,腾出位置放新元素。LRU缓存算法要求的是清除缓存中最近不使用的元素。这种实现机制可以使用LinkedHashMap来实现比较合适。但有一点需要注意,LinkedHash不是线程安全的,如果有多个线程需要写数据需要进行同步控制。如果需要增加线程同步功能,可以使用Collections工具。
通过阅读LinkedHashMap源码可以发现,LinkedHashMap有一个构造函数,构造函数可以接受三个参数,分别是默认初始容量,负载因子,是否按访问排序。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
定义LRU缓存实现类,继承LinkedHashMap类,在LRU的构造函数中调用LinkedHashMap的构造函数。在构造函数中定义一个初始容量(hashMap默认为16,这里需要根据实际业务量大小合理的设置,如果太大浪费空间,如果太小容易触发扩容,会有元素复制的开销),还要定义一个负载因子即当容量占用多大时触发HashMap扩容(默认0.45),accessOrder要设置为true(即将最近访问的元素放到链表的尾部)。此外,还需要复写boolean removeEldestEntry方法,自定义清除元素的条件(清除元素从列表头开始清理)。
package base.container; import java.util.LinkedHashMap; import java.util.Map; /* * LRU:最近最少使用 * 场景:假设缓存大小为10,现在缓存已经有是个元素了, * 新加入元素时,就需要把原缓存里面清除掉一个元素从, * LRU缓存算法要求清除掉最近最少使用的元素, * LinkedHashmap有一个参数access-order可以控制双链表是按访问排序还是插入排序 * 如果access-order==true,则按访问排序, * 每次访问linkedhashmap中元素,就将元素放到链表后面, * 这样新加入元素时,就将链表的第一个元素清除掉,把新元素放上去即可 */ public class LRUCache extends LinkedHashMap{ private static final int MAX_ENTRIES = 3; protected boolean removeEldestEntry(Map.Entry eldest) { return size()>MAX_ENTRIES;//当map的size大于3时,即清理元素 } LRUCache(){ super(MAX_ENTRIES,0.75F,true);//true:按访问顺序排序 } public static void main(String args[]) { LRUCache cache = new LRUCache(); cache.put(1, "a"); cache.put(2, "b"); cache.put(3, "c"); //输出1,2,3 System.out.println(cache.keySet()); cache.get(1); //输出2,3,1 System.out.println(cache.keySet()); cache.put(4, "d"); //输出3,1,4 System.out.println(cache.keySet()); } }