One of the leetcode questions is to implement a least recently used cache. Basically a cache has to combine two kinds of data structures: a hash table so we can get/set item and a linked list so we can maintain the order of entries.
In JDK there is LinkedHashMap, which does the above, its implement a special Map.Entry class which only has key and value, but also maintain pointer to the next and previous Map.Entry.
Here are couple of my implementations:
1. Use LinkedHapMap directly:
public class SimpleLRUCache {
private int capacity;
LinkedHashMap<Object, Object> map;
public SimpleLRUCache(final int capacity){
this.capacity = capacity;
map = new LinkedHashMap<Object, Object>(12, 0.76f, true){
protected boolean removeEldestEntry(Map.Entry<Object,Object> eldest){
return this.size() == capacity;
}
};
}
}
2. Use HashMap and LinkedList:
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
public static class Node{
Object key;
Object value;
Node pre;
Node next;
}
Map<Object, Node> map;
int capacity;
//head points to the oldest entry
Node head;
Node tail;
public LRUCache (int c){
this.capacity = c;
this.map = new HashMap<Object, Node>();
}
public Object get(Object key){
if(map.containsKey(key)){
Node n = map.get(key);
remove(n);
addLast(n);
return n.value;
}else
return null;
}
public void set(Object key, Object value){
if(map.containsKey(key)){
Node n = map.get(key);
remove(n);
addLast(n);
return;
}
if(map.size() == this.capacity){
map.remove(head.key);
remove(head);
}
Node n = new Node();
n.key = key;
n.value = value;
addLast(n);
map.put(key, n);
}
public void addLast(Node n){
if(head==null){
head = n;
tail = n;
}else{
tail.next = n;
n.pre = tail;
tail = n;
}
}
public void remove(Node n){
if(n.pre == null){
head = n.next;
}else{
n.pre.next = n.next;
}
if(n.next == null){
tail = n.pre;
}else
n.next.pre = n.pre;
//set the pointer so n can be gc'd
n.pre = n.next = null;
}
}
3. Synchronized LRU
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
/*
* a thread-safe LRUCache implementation using lock
*
* note only most important methods are implemented
*/
public class SynchronizedLRUCache<K, V> implements Map<K,V> {
private final Map<K, V> cache;
public SynchronizedLRUCache(final int maxSize, final int initSize, final float lf){
this.cache = new LinkedHashMap<K ,V>(initSize, lf){
private static final long serialVersionUID = -1218440011343946609L;
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> oldest){
return size() > maxSize;
}
};
}
public SynchronizedLRUCache(final int maxSize, final int initSize){
this(maxSize, initSize, 0.75f);
}
public SynchronizedLRUCache(final int maxSize){
this(maxSize, 1<<4, 0.75f);
}
public int size() {
synchronized(cache){
return cache.size();
}
}
public boolean isEmpty() {
synchronized(cache){
return cache.isEmpty();
}
}
public boolean containsKey(Object key) {
synchronized(cache){
return cache.containsKey(key);
}
}
public V put(K key, V value) {
synchronized(cache){
return cache.put(key, value);
}
}
public V get(Object key) {
synchronized(cache){
return cache.get(key);
}
}
public void putAll(Map<? extends K, ? extends V> m) {
synchronized(cache){
cache.putAll(m);
}
}
public boolean containsValue(Object value) {
// TODO Auto-generated method stub
return false;
}
public V remove(Object key) {
// TODO Auto-generated method stub
return null;
}
public void clear() {
// TODO Auto-generated method stub
}
public Set<K> keySet() {
// TODO Auto-generated method stub
return null;
}
public Collection<V> values() {
// TODO Auto-generated method stub
return null;
}
public Set<java.util.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}
}
