使用LinkedHashMap的accessOrder实现LRU算法
作者:binLRU是Least Recently Used的缩写,即最近最少使用算法:
基础理论:最近使用的数据,需要提高访问效率,很长时间不使用的数据,对访问效率要求更低。
initialCapacity 初始容量大小,使用无参构造方法时,此值默认是16
loadFactor 加载因子,使用无参构造方法时,此值默认是 0.75f
accessOrder false: 基于插入顺序 true: 基于访问顺序
当accessOrder设置为true时,被访问的数据,将会被移到链表的尾部,我们知道put时也是追加在尾部。
同时get是从尾部开始访问,所以等于越常使用的数据,遍历的时间越短。
class LRUCache { class LinkedCache<K,V> extends LinkedHashMap<K,V>{ private final int size; LinkedCache(int initSize){ super(initSize, 0.75f, true); size = initSize; } @Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest){ return size() > size; } } LinkedCache<Integer, Integer> linkedCache; public LRUCache(int capacity) { linkedCache = new LinkedCache(capacity); } public int get(int key) { return linkedCache.containsKey(key)? linkedCache.get(key): -1; } public void put(int key, int value) { linkedCache.put(key, value); } }