I have solved this LeetCode problem. Depending (perhaps) on the server load, I once scored the following performance figures:
My code follows:
class LRUCache {
private static final class LinkedListNode {
final int key;
int value;
LinkedListNode next;
LinkedListNode prev;
LinkedListNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private static final class LinkedList {
private LinkedListNode head;
private LinkedListNode tail;
// Unlinks the given node from its possible predecessor and
// successor:
void unlink(LinkedListNode node) {
if (head == null) {
return;
}
LinkedListNode prev = node.prev;
LinkedListNode next = node.next;
if (prev == null) {
head = next;
} else {
prev.next = next;
node.prev = null;
}
if (next == null) {
tail = prev;
} else {
next.prev = prev;
node.next = null;
}
}
// Adds the given node after the tail of this list:
void append(LinkedListNode node) {
if (tail == null) {
tail = node;
head = node;
} else {
tail.next = node;
node.prev = tail;
node.next = null;
tail = node;
}
}
}
private static final class HashTableNode {
LinkedListNode linkedListNode;
HashTableNode next;
HashTableNode prev;
HashTableNode(LinkedListNode node) {
this.linkedListNode = node;
}
}
private static final class HashTable {
private int size;
private final LinkedList list;
private final HashTableNode[] table;
HashTable(int capacity) {
table = new HashTableNode[capacity];
list = new LinkedList();
}
int size() {
return size;
}
// Adds the given node to this map. If it is already present in the
// map, the node value is updated. Otherwise, a new mapping is
// created:
void put(LinkedListNode linkedListNode) {
HashTableNode hashTableNode = getNode(linkedListNode.key);
if (hashTableNode != null) {
// Just update the value:
hashTableNode.linkedListNode.value = linkedListNode.value;
return;
}
hashTableNode = new HashTableNode(linkedListNode);
int index = linkedListNode.key % table.length;
if (table[index] != null) {
table[index].prev = hashTableNode;
hashTableNode.next = table[index];
}
table[index] = hashTableNode;
size++;
}
// Attempts to read a value associated with the given key. Returns
// -1 if there is no given key in the map:
int get(int key) {
HashTableNode node = getNode(key);
if (node == null) {
return -1;
}
// Relink the node to the tail of the internal linked list:
list.unlink(node.linkedListNode);
list.append(node.linkedListNode);
return node.linkedListNode.value;
}
// Removes the mapping wiith the given key:
private void remove(int key) {
HashTableNode node = getNode(key);
if (node == null) {
// Nothing to remove:
return;
}
int hash = key % table.length;
if (node.prev == null) {
// The node to remove is the collision chain head. Advance
// the collision chain head to the successor node:
table[hash] = node.next;
} else {
// Unlink from the collision chain:
node.prev.next = node.next;
}
// Deal with the removed node successor:
if (node.next != null) {
node.next.prev = node.prev;
}
--size;
}
// Fetches the map node with the given key, or 'null' if there is no
// such:
private HashTableNode getNode(int key) {
int hash = key % table.length;
for (HashTableNode node = table[hash];
node != null;
node = node.next) {
if (node.linkedListNode.key == key) {
return node;
}
}
return null;
}
}
private final int capacity;
private final HashTable table;
/**
* Constructs a new cache object.
*
* @param capacity the maximum number of key/value -pairs accepted.
*/
public LRUCache(int capacity) {
this.capacity = capacity;
table = new HashTable(capacity);
}
/**
* Reads the value associated with the given key.
*
* @param key the key whose value to read.
* @return the value associated with {@code key}.
*/
public int get(int key) {
return table.get(key);
}
/**
* Creates or updates a key/value -mapping.
*
* @param key the key.
* @param value the value.
*/
public void put(int key, int value) {
HashTableNode hashTableNode = table.getNode(key);
if (hashTableNode == null) {
// No 'key' in this cache, create one:
LinkedListNode linkedListNode = new LinkedListNode(key, value);
table.list.append(linkedListNode);
table.put(linkedListNode);
} else {
// Update existing mapping with the new value:
hashTableNode.linkedListNode.value = value;
table.list.unlink(hashTableNode.linkedListNode);
table.list.append(hashTableNode.linkedListNode);
return;
}
if (table.size() > capacity) {
// Here, the cache is too big (by one mapping), remove LRU:
removeLRU();
}
}
// Removes the head element (that is least recently used) from the
// cache:
private void removeLRU() {
table.remove(table.list.head.key);
table.list.unlink(table.list.head);
}
}
Critique request
Please tell me anything that comes to mind.
