LRU Cache

Intro

A LRU cache is "a cache with a fixed maximum size, evicting items that were used least-recently".

Question (LC.146)

LRU supports two regular hash operations - get(key) and put(key, value). But the cache will operate under a limited capacity. The least recently used item will be deleted when running out of space.

Analysis

This is a cache data structure, we should keep get and put in O(1) time. We'll need a HashMap internally.

Q1: How to keep track of the recentness?

We want to keep the pairs in a relative order. We also want insert/delete to be O(1) so linked list!!

Q2: How do we implement insert/delete? Do we need a DLL?

A DDL will make deletion a lot easier b/c you have the reference to the previous node. But then a SLL can just get a ref to the previous node then perform the same action.

Using Java Build-in API

From Java doc, LinkedHashMap is a "Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries."

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.

public class LRUCache {
    private final int maxSize;
    Map<Integer, Integer> linkedHash;

    public LRUCache(int capacity) {
        maxSize = capacity;
        linkedHash = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) 
        {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > maxSize;
            }
        };
    }

    public int get(int key) {
        return linkedHash.getOrDefault(key, -1);
    }

    public void set(int key, int value) {
        linkedHash.put(key, value);
    }
}

DLL Implementation

/**
 * This is a standard implementation of Least Recently Used (LRU) cache.
 * It supports two regular hash operations - get(key) and put(key, value) in O(1) time.
 * The least recently used item will be deleted when reaching the capacity.
 */
public class LRUCache {
    private class DLLNode {
        DLLNode prev;
        DLLNode next;
        int key;
        int value;
        DLLNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private DLLNode dummyHead;
    private DLLNode dummyTail;
    private Map<Integer, DLLNode> map;

    /**
     * Initialize the LRU cache with a specified capacity
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead = new DLLNode(0, 0);
        dummyTail = new DLLNode(0, 0);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        map = new HashMap<Integer, DLLNode>(capacity);
    }

    /**
     * Return the value of the key if the key exists, otherwise return -1
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        updateRecent(key);
        return map.get(key).value;
    }

    /**
     * Put in a new (key, value) pair to the cache.
     * Only update the value of that key if the key already exists.
     * The least recently used cache will be removed before inserting the new pair 
     * when the cache reaches its capacity.
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).value = value;
            updateRecent(key);
            return;
        }
        if (map.size() >= capacity) {
            deleteOldest();
        }
        DLLNode newNode = new DLLNode(key, value);
        insertNewest(newNode);
        map.put(key, newNode);
    }

    private void deleteCurrent(DLLNode current) {
        DLLNode prevNode = current.prev;
        prevNode.next = current.next;
        current.next.prev = prevNode;       
    }

    private void deleteOldest() {
        map.remove(dummyHead.next.key);
        dummyHead.next = dummyHead.next.next;
        dummyHead.next.prev = dummyHead;
    }

    private void insertNewest(DLLNode newNode) {
        DLLNode secRecent = dummyTail.prev;
        newNode.next = dummyTail;
        newNode.prev = secRecent;
        secRecent.next = newNode;
        dummyTail.prev = newNode;
    }

    // move the most recently used node to the end
    private void updateRecent(int key) {
        DLLNode recent = map.get(key);
        deleteCurrent(recent);
        insertNewest(recent);       
    }
}

Reference

• Java Doc LinkedHashMap

• Twitter API DOCs LRUCache