Skip to content

Instantly share code, notes, and snippets.

@hoffrocket
Created March 4, 2012 01:17
Show Gist options
  • Save hoffrocket/1969769 to your computer and use it in GitHub Desktop.
Save hoffrocket/1969769 to your computer and use it in GitHub Desktop.
Simple LRUCache in java (not threadsafe)
import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V> {
private final Map<K, Pair<Node<K>, V>> map = new HashMap<K, Pair<Node<K>,V>>();
private Node<K> head = null;
private Node<K> tail = null;
private final int maxSize;
public LRUCache(int maxSize) {
this.maxSize = maxSize;
}
static class Node<K> {
public Node(K key) {
this.key = key;
}
K key;
Node<K> next;
Node<K> previous;
public void prepend(Node<K> node) {
node.remove();
node.previous = this.previous;
node.next = this;
this.previous = node;
}
public void remove() {
if (previous != null) {
previous.next = next;
}
if (next != null) {
next.previous = previous;
}
}
}
static class Pair<T1,T2> {
public final T1 _1;
public final T2 _2;
public Pair(T1 _1, T2 _2) {
this._1 = _1;
this._2 = _2;
}
}
public V get(K key) {
Pair<Node<K>, V> entry = map.get(key);
if (entry != null) {
pushHead(entry._1);
return entry._2;
} else {
return null;
}
}
public V put(K key, V value) {
Pair<Node<K>, V> entry = map.get(key);
if (entry == null) {
entry = new Pair<Node<K>,V>(new Node<K>(key), value);
}
Pair<Node<K>, V> previousValue = map.put(key, new Pair<Node<K>, V>(entry._1, value));
pushHead(entry._1);
trim();
return previousValue != null ? previousValue._2 : null;
}
private void trim() {
if (map.size() > maxSize) {
map.remove(tail.key);
if (tail.previous != null) {
tail.previous.next = null;
tail = tail.previous;
}
}
}
private void pushHead(Node<K> key) {
if (head != null) {
head.prepend(key);
if (tail == key) {
tail = key.next;
}
} else {
tail = key;
}
head = key;
}
}
@tjulien
Copy link

tjulien commented Mar 4, 2012

looks good. I think line 84 should be tail = key.previous.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment