Least recently used cache (LRU) implementation

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;
    }

   

}