前言
今天在看GuavaCache缓存相关的源码，这里想到先自己手动实现一个LRU算法。于是乎便想到LinkedHashMap和LinkedList+HashMap, 这里仅仅是作为简单的复习一下。
LRU
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
代码实现原理
LinkedList + HashMap： LinkedList其实是一个双向链表，我们可以通过get和put来设置最近请求key的位置，然后hashMap去存储数据
LinkedHashMap：LinkedHashMap是继承自HashMap，只不过Map中的Node节点改为了双向节点，双向节点可以维护添加的顺序，在LinkedHashMap的构造函数中有一个accessOrder， 当设置为true后，put和get会自动维护最近请求的位置到last。
LinkedList+HashMap代码实现
LRUCache接口：
/**
* @Description:
* @Author: wangmeng
* @Date: 2018/12/8-10:49
*/
public class LinkedListLRUTest {
public static void main(String[] args) {
LRUCache<String, String> cache = new LinkedListLRUCache<>(3);
cache.put("1", "1");
cache.put("2", "2");
cache.put("3", "3");
System.out.println(cache);
cache.put("4", "4");
System.out.println(cache);
System.out.println(cache.get("2"));
System.out.println(cache);
}
}
LinkedList实现：
/**
* @Description:使用LinkedList+HashMap来实现LRU算法
* @Author: wangmeng
* @Date: 2018/12/8-10:41
*/
public class LinkedListLRUCache<K, V> implements LRUCache<K, V> {
private final int limit;
private final LinkedList<K> keys = new LinkedList<>();
private final Map<K, V> cache = Maps.newHashMap();
public LinkedListLRUCache(int limit) {
this.limit = limit;
}
@Override
public void put(K key, V value) {
Preconditions.checkNotNull(key);
Preconditions.checkNotNull(value);
if (keys.size() >= limit) {
K oldesKey = keys.removeFirst();
cache.remove(oldesKey);
}
keys.addLast(key);
cache.put(key, value);
}
@Override
public V get(K key) {
boolean exist = keys.remove(key);
if (!exist) {
return null;
}
keys.addLast(key);
return cache.get(key);
}
@Override
public void remove(K key) {
boolean exist = keys.remove(key);
if (exist) {
keys.remove(key);
cache.remove(key);
}
}
@Override
public int size() {
return keys.size();
}
@Override
public void clear() {
keys.clear();
cache.clear();
}
@Override
public int limit() {
return this.limit;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (K key : keys) {
builder.append(key).append("=").append(cache.get(key)).append(";");
}
return builder.toString();
}
}
LinkedList测试类：
/**
* @Description:
* @Author: wangmeng
* @Date: 2018/12/8-10:49
*/
public class LinkedListLRUTest {
public static void main(String[] args) {
LRUCache<String, String> cache = new LinkedListLRUCache<>(3);
cache.put("1", "1");
cache.put("2", "2");
cache.put("3", "3");
System.out.println(cache);
cache.put("4", "4");
System.out.println(cache);
System.out.println(cache.get("2"));
System.out.println(cache);
}
}
LinkedList测试类返回值：
1=1;2=2;3=3;
2=2;3=3;4=4;
2
3=3;4=4;2=2;LinkedHashMap实现
/**
* @Description: 不是一个线程安全的类，这里是使用LinkedHashMap来做LRU算法
* @Author: wangmeng
* @Date: 2018/12/8-10:14
*/
public class LinkedHashLRUCache<K, V> implements LRUCache<K, V> {
private static class InternalLRUCache<K, V> extends LinkedHashMap<K, V> {
final private int limit;
private InternalLRUCache(int limit) {
super(16, 0.75f, true);
this.limit = limit ;
}
//实现remove元素的方法，这个是重写了LinkedHashMap中的方法。因为在HashMap的putVal会调用afterNodeInsertion(), 而这个方法会判断removeEldestEntry方法。
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > limit;
}
}
private final int limit;
//使用组合关系优于继承，这里只对外暴漏LRUCache中的方法
private final InternalLRUCache<K, V> internalLRUCache;
public LinkedHashLRUCache(int limit) {
Preconditions.checkArgument(limit > 0, "The limit big than zero.");
this.limit = limit;
this.internalLRUCache = new InternalLRUCache(limit);
}
@Override
public void put(K key, V value) {
this.internalLRUCache.put(key, value);
}
@Override
public V get(K key) {
return this.internalLRUCache.get(key);
}
@Override
public void remove(K key) {
this.internalLRUCache.remove(key);
}
@Override
public int size() {
return this.internalLRUCache.size();
}
@Override
public void clear() {
this.internalLRUCache.clear();
}
@Override
public int limit() {
return this.limit;
}
@Override
public String toString() {
return internalLRUCache.toString();
}
}LinkedHashMap测试类：
/**
* @Description:
* @Author: wangmeng
* @Date: 2018/12/8-10:30
*/
public class LinkedHashLRUTest {
public static void main(String[] args) {
LRUCache<String, String> cache = new LinkedHashLRUCache<>(3);
cache.put("1", "1");
cache.put("2", "2");
cache.put("3", "3");
System.out.println(cache);
cache.put("4", "4");
System.out.println(cache);
System.out.println(cache.get("2"));
System.out.println(cache);
}
}LinkedHashMap测试结果：
{1=1, 2=2, 3=3}
{2=2, 3=3, 4=4}
2
{3=3, 4=4, 2=2}