> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-4/advanced_data_structures/cache-replacement/lru-cache.md).

# LRU Cache

## Intro

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

## Question ([LC.146](https://leetcode.com/problems/lru-cache/description/))

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.
```

```java
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

```java
/**
 * 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](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html)
* Twitter API DOCs [LRUCache](https://twitter.github.io/commons/apidocs/com/twitter/common/util/caching/LRUCache.html)