原理
LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。
相关算法原理参考:https://www.jianshu.com/p/d533d8a66795
实现
基于链表实现,当map容量大于最大值移除头部最旧的对象,当命中key时,把命中对象移到链表结尾。
由于LinkedHashMap非线形安全,所以加入ReentrantLock在读写后加锁。
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private final int maxCapacity;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private final Lock lock = new ReentrantLock();
public LRULinkedHashMap(int maxCapacity) {
super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
return size() > maxCapacity;
}
@Override
public V get(Object key) {
try {
lock.lock();
return super.get(key);
} finally {
lock.unlock();
}
}
@Override
public V put(K key, V value) {
try {
lock.lock();
return super.put(key, value);
} finally {
lock.unlock();
}
}
}
相关测试:
@Test
public void test(){
LRULinkedHashMap map = new LRULinkedHashMap(3);
map.put(1,1);
map.put(2,2);
map.put(3,3);
System.out.println(map.get(1));
map.put(4,4);
System.out.println(JSON.toJSON(map));
}
打印结果:
1
{"3":3,"1":1,"4":4}