LRU

LRUCache.java

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class LRUCache<T> {
	private int maxItems;
	private Node top = new Node("", null);
	private Node btm = new Node("", null);
	private Map<String, Node> hm = Collections.synchronizedMap(new HashMap<String, Node>());

	public LRUCache(int maxItems) {
		if (maxItems <= 0) {
			throw new IllegalArgumentException("maxItems cannot be <=0.");
		}
		this.maxItems = maxItems;
		top.next = btm;
		btm.previous = top;
	}

	public Object get(String key) {
		Node tmpNode = hm.get(key);
		if (tmpNode != null) {
			moveToTop(tmpNode, true);
			return tmpNode.value;
		}
		return null;
	}

	public void put(String key, T value) {
		Node tmpNode = hm.get(key);
		if (tmpNode != null) {
			tmpNode.value = value;
			moveToTop(tmpNode, true);
			return;
		} else {
			tmpNode = new Node(key, value);
			moveToTop(tmpNode, false);
			cleanupIfFull();
			hm.put(key, tmpNode);
		}
	}

	private void moveToTop(Node node, boolean preCleanup) {
		if (preCleanup) {
			// unlink first
			Node prev = node.previous;
			Node next = node.next;
			node.previous = null;
			node.next = null;
			prev.next = next;
			next.previous = prev;
		}
		// move to top
		node.next = top.next;
		top.next.previous = node;
		node.previous = top;
		top.next = node;
	}

	private void cleanupIfFull() {
		if (hm.size() >= maxItems) {
			// unlink first
			Node prev = btm.previous;
			Node prepre = prev.previous;
			prev.next = null;
			prev.previous = null;
			prepre.next = btm;
			btm.previous = prepre;
			// remove from HashMap
			hm.remove(prev.key);
		}
	}

	private class Node {
		String key;
		T value;
		Node next;
		Node previous;

		public Node(String key, T value) {
			this.key = key;
			this.value = value;
		}
	}
}

LRUCacheCool.java

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheCool<T> {
	private Map<String, T> hm;
	@SuppressWarnings("serial")
	public LRUCacheCool(int maxItems) {
        Map<String, T> t = new LinkedHashMap<String, T>(maxItems, 0.75f, true){
            @SuppressWarnings("rawtypes")
			protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > maxItems;
            }
        };
        hm = Collections.synchronizedMap(t);
    }
    public T get(String key) {
        return hm.get(key);
    }
    public void set(String key, T value) {
    	if(key==null || value==null) {
    		throw new IllegalArgumentException("key/value cannot be null");
    	}
        hm.put(key, value);
    }
}