前几天看Redis的时候看见了一个LRU缓存,感觉挺有意思的,今天闲着无事就想着手写一个来练练手。不过在开始动手之前,还是做个简单的介绍,关于LRU的一些知识。LRU(least recently used)即最近最少使用,常用语缓存的过期策略。Redis是一个比较常用的缓存中间件,经常被用来存放一些高访问率的数据,但是有的时候数据量过大,就会导致内存溢出,这个时候就需要按照一定的规则或者策略删除掉旧的数据,而LRU过期策略就是其中一种。
设计
接下来我们就来设计一个简单的基于LRU的Key-Value缓存,说到设计首当其冲的就是数据结构。那么选用什么数据结构最合适呢?首先我们要知道我们是用来作为缓存的,那么缓存最多的操作就是读写,除此之外还要有增删操作,那么这个时候仅仅使用数据肯定就不行了,如果只使用链表呢也不行,这个时候就要使用链表和映射结合的方式。
public class day01 {
public static void main(String[] args) {
LRUCache<String> lruCache = new LRUCache<String>(3);
lruCache.cache("A", "a");
lruCache.cache("B", "b");
lruCache.cache("C", "c");
for (String s : lruCache) {
System.out.print(s + "<-");
}
lruCache.get("A");
System.out.println();
for (String s : lruCache) {
System.out.print(s + "<-");
}
lruCache.cache("D", "d");
System.out.println();
for (String s : lruCache) {
System.out.print(s + "<-");
}
}
static class LRUCache<T> implements Iterable<T>{
private final LinkedHashMap<String, T> cache;
private int MAX;
public LRUCache(int size) {
this.cache = new LinkedHashMap<>(size);
this.MAX = size;
}
public void cache(String key, T value) {
if (cache.size() >= MAX) {
Map.Entry<String, T> first = cache.entrySet().iterator().next();
cache.remove(first.getKey());
} else {
if (cache.containsKey(key)) {
cache.remove(key);
}
}
cache.put(key,value);
}
public T get(String key) {
if (cache.containsKey(key)) {
T val = cache.get(key);
cache.remove(key);
cache.put(key, val);
return val;
}
return null;
}
@Override
public Iterator<T> iterator() {
Iterator<Map.Entry<String, T>> iterator = cache.entrySet().iterator();
return new Iterator() {
@Override
public boolean hasNext() {
return iterator.hasNext();
}
@Override
public T next() {
return iterator.next().getValue();
}
};
}
}
}