LRU Cache
Two ways to implement LRU Cache, one way is implementing our own double linked list,
the other is to make use of TreeMap
.
Implementing double linked list:
class DoubleLinkedListNode {
int key;
int value;
DoubleLinkedListNode prev;
DoubleLinkedListNode next;
DoubleLinkedListNode(int k, int v) {
key = k;
value = v;
}
}
public class LRUCache {
int capacity;
HashMap<Integer, DoubleLinkedListNode> map;
int size = 0;
DoubleLinkedListNode head = new DoubleLinkedListNode(0, -1);
DoubleLinkedListNode tail = new DoubleLinkedListNode(0, -1);
private void removeListNode(DoubleLinkedListNode node) {
DoubleLinkedListNode prev = node.prev;
DoubleLinkedListNode next = node.next;
prev.next = next;
next.prev = prev;
node.next = null;
node.prev = null;
size--;
}
private void addListNode(DoubleLinkedListNode node) {
while (size >= capacity) {
pollListNode();
}
node.next = tail;
node.prev = tail.prev;
tail.prev.next = node;
tail.prev = node;
size++;
}
private void pollListNode() {
if (size <= 0) return;
DoubleLinkedListNode firstNode = head.next;
removeListNode(firstNode);
map.remove(firstNode.key);
}
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
map = new HashMap<Integer, DoubleLinkedListNode>(capacity);
}
public int get(int key) {
if (map.containsKey(key)) {
DoubleLinkedListNode valNode = map.get(key);
removeListNode(valNode);
addListNode(valNode);
return valNode.value;
}
return -1;
}
public void set(int key, int value) {
if (get(key) < 0) {
DoubleLinkedListNode node = new DoubleLinkedListNode(key, value);
addListNode(node);
map.put(key, node);
} else {
map.get(key).value = value;
}
}
}
Using TreeMap
class Entry {
int key;
int value;
Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
public class LRUCache {
HashMap<Integer, Long> keyTimeMap;
TreeMap<Long, Entry> timeValueMap;
long time = 0;
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
keyTimeMap = new HashMap<Integer, Long>(capacity);
timeValueMap = new TreeMap<Long, Entry>();
}
public int get(int key) {
if (keyTimeMap.containsKey(key)) {
Entry entry = timeValueMap.remove(keyTimeMap.get(key));
keyTimeMap.put(key, ++time);
timeValueMap.put(time, entry);
return entry.value;
}
return -1;
}
private void removeLeastRecentlyUsed() {
while (timeValueMap.size() > capacity) {
Map.Entry<Long, Entry> first = timeValueMap.pollFirstEntry();
Entry entry = first.getValue();
keyTimeMap.remove(entry.key);
}
}
public void set(int key, int value) {
if (keyTimeMap.containsKey(key)) {
timeValueMap.remove(keyTimeMap.remove(key));
}
keyTimeMap.put(key, ++time);
timeValueMap.put(time, new Entry(key, value));
removeLeastRecentlyUsed();
}
}