146. LRU Cache

Reference: LeetCode
Difficulty: Medium

Problem

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Example:

LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4
// OR
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);  // 1 should be removed
// OR
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.put(2, 2);  // or cache.get(2);
cache.put(3, 3);  // 2 should be removed

Follow up: Could you do both operations in O(1) time complexity?

Analysis

Use LinkedHashMap

Reference: Java LinkedHashMap工作原理及实现

From official documentation:

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. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

Inside:

In HashMap, there are three callback methods that allow LinkedHashMap post-actions.

void afterNodeAccess(Node<K,V> p) { }
// after put() is called
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // if removeEldestEntry() is defined
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
void afterNodeRemoval(Node<K,V> p) { }

removeEldestEntry is a method that we can override. It is usually invoked after put operation. If it returns true, the first entry would be deleted; otherwise, nothing happens.

Then we can see how put and get work. In LinkedHashMap, put is not re-implemented, but all new features are implemented in afterNodeAccess and afterNodeInsertion callbacks.

// `get` is re-implemented
public V get(Object key) {
  Node<K, V> e;
  if ((e = getNode(hash(key), key)) == null)
    return null;
  if (accessOrder)
    afterNodeAccess(e);
  return e.value;
}

accessOrder:

accessOrder is a boolean that indicates two modes of structural modification, which are access-ordered and insertion-ordered modes.

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, merely querying the map with get is a structural modification.

In other words, when accessOrder is set as true, calls of put, get, and so on would trigger affection on iteration order. The accessed entry will be put at the end of the linked list.

Basic Usage:

accessOrder is false:

// Default mode is insertion-order mode
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.get(2); // no effect
// Output: [1, 2, 3, 4]

accessOrder is true:

// access-ordered mode
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(2, 0.75f, true);
// 2 and 0.75f (predictive capacity and load factor)
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
// Output: [1, 2, 3, 4]
map.get(1);
// Output: [2, 3, 4, 1]

Code for this problem:

We can make the class LRUCache extend from LinkedHashMap. get and put are overloaded, and removeEldestEntry is overridden. It means that we would delete the first entry when this.size() > capacity.

Note: capacity member is a fixed value, while the capacity passed into LinkedHashMap is for speculative purpose (just guessing? optimization?).

class LRUCache extends LinkedHashMap<Integer, Integer> {

  private int capacity;
  
  // true for access-order; false for insertion-order
  public LRUCache(int capacity) {
    super(capacity, 0.75f, true); // access-order
    this.capacity = capacity;
  }

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

  public void put(int key, int value) {
    super.put(key, value);
  }
  
  // removeEldestEntry is invoked every time we call put!
  
  @Override
  protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
    return this.size() > capacity;
  }
}

The second approach is similar to the object adapter pattern. A LinkedListMap object is wrapped inside LRUCache.

Note: See comments below.

class LRUCache {

  private Map<Integer, Integer> map;
  
  public LRUCache(int capacity) {
    map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) { // access-order mode
      @Override
      protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return map.size() > capacity; // can't use this.map since `this` is not the `this` of LRUCache
      }
    };
  }

  public int get(int key) {
    return map.getOrDefault(key, -1);
  }
  
  public void put(int key, int value) {
    map.put(key, value);
  }
}

Time: $O(1)$
Space: $O(capacity)$

Do It By Yourself

欣赏一下别人的代码。我稍微改了一下。自己写了好久还是有 bug，链表有毒。

public class LRUCache {

  private DLinkedNode head, tail;

  class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;
  }

  private void addFirst(DLinkedNode node) {
    node.prev = head;
    node.next = head.next;

    head.next.prev = node;
    head.next = node;
  }

  private void removeNode(DLinkedNode node){
    DLinkedNode prev = node.prev;
    DLinkedNode next = node.next;

    prev.next = next;
    next.prev = prev;
  }

  private void moveToHead(DLinkedNode node){
    removeNode(node);
    addFirst(node);
  }

  private DLinkedNode popTail() {
    DLinkedNode res = tail.prev;
    removeNode(res);
    return res;
  }

  private Map<Integer, DLinkedNode> cache = new HashMap<>();
  private int size;
  private int capacity;

  public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;
    head = new DLinkedNode();
    tail = new DLinkedNode();
    head.next = tail;
    tail.prev = head;
  }

  public int get(int key) {
    DLinkedNode node = cache.get(key);
    if (node == null) return -1;

    // move the accessed node to the head;
    moveToHead(node);

    return node.value;
  }

  public void put(int key, int value) {
    DLinkedNode node = cache.get(key);

    if(node == null) {
      DLinkedNode newNode = new DLinkedNode();
      newNode.key = key;
      newNode.value = value;

      cache.put(key, newNode);
      addFirst(newNode);

      ++size;

      if(size > capacity) {
        // pop the tail
        DLinkedNode tail = popTail();
        cache.remove(tail.key);
        --size;
      }
    } else {
      // update the value.
      node.value = value;
      moveToHead(node);
    }
  }
}

Time: $O(1)$
Space: $O(capacity)$