LeetCode - LRU Cache by rodde

Question

I have solved this LeetCode problem. Depending (perhaps) on the server load, I once scored the following performance figures: Funky results

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.

Answer 1

• get returning -1 on failure is always dubious. It essentially forbids the client to put a value of -1. I recommend to return a pair of bool, value, STL style.

• It also doesn't feel right that HashTable.remove and HashTable.getNode operate on the list directly. Consider making the appropriate LinkedList methods. After all, the LinkedList is already aware of the kay field of its nodes.

• To expand on the above bullet, the elements of HashTable.table are linked lists. It is worth an effort to provide a unified implementation of a linked list, one and forever.

• Both branches of LinkedList.append do tail = node;. Lift if out of the conditional.

• Inline comments like // No 'key' in this cache, create one or // Update existing mapping with the new value indicate that you failed to express yourself clearly in the code. Consider making the commented block a method with a proper name.

• Tamoghna Chowdhury: Why not use a java.util.Optional for getting a value that doesn't exist?
• vnp: @TamoghnaChowdhury You are absolutely correct. Missed it.
• coderodde: First bullet: it's part of the "API" for the given LeetCode task.