LC146, LRU Cache 2

A revisit on LRU Cache.

Why using a LinkedHashMap?

3 operations:

1. Get key/ Check if key exists
2. Put key
3. Delete the first added key

LinkedHashMap

1 & 2: HashMap; 3: Linked List ==> LinkedHashMap

LinkedHashMap keeps elements the order they are inserted.

private LinkedHashMap<Integer, Integer> map;
private int size;

public LRUCache(int capacity) {
    map = new LinkedHashMap<>();
    size = capacity;
}

public int get(int key) {
    if (map.containsKey(key)) {
        int value = map.remove(key);
        map.put(key, value);
        return value;
    }
    return -1;
}

// remove, re-insert to keep fresh
public void put(int key, int value) {
    if (map.containsKey(key)) {
        map.remove(key);
    } else if (map.size() + 1 > size) {
        map.remove(map.keySet().iterator().next());
    }
    map.put(key, value);
}

⚠️注意: map的不同种类的set都有各自的iterator, 调用iterator()获取到iterator, 然后调用next()获取set对应的东西; remove(key)方法中传递的参数是key然后删掉的是entry.

Or cheating:

class LRUCache extends LinkedHashMap<Integer, Integer> {
    
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Integer val = super.get(key);
        return val == null ? -1 : val;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }
}

HashMap: Integer(key) -> Doubly linked list

1. One interesting property about double linked list is that the node can remove itself without other reference
2. create a pseudo head and tail to mark the boundary, so that we don’t need to check the NULL node during the update.

import java.util.Hashtable;


public class LRUCache {

class DLinkedNode {
  int key;
  int value;
  DLinkedNode pre;
  DLinkedNode post;
}

/**
 * Always add the new node right after head;
 */
private void addNode(DLinkedNode node) {
    
  node.pre = head;
  node.post = head.post;

  head.post.pre = node;
  head.post = node;
}

/**
 * Remove an existing node from the linked list.
 */
private void removeNode(DLinkedNode node){
  DLinkedNode pre = node.pre;
  DLinkedNode post = node.post;

  pre.post = post;
  post.pre = pre;
}

/**
 * Move certain node in between to the head.
 */
private void moveToHead(DLinkedNode node){
  this.removeNode(node);
  this.addNode(node);
}

// pop the current tail. 
private DLinkedNode popTail(){
  DLinkedNode res = tail.pre;
  this.removeNode(res);
  return res;
}

private Hashtable<Integer, DLinkedNode> 
  cache = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
  this.count = 0;
  this.capacity = capacity;

  head = new DLinkedNode();
  head.pre = null;

  tail = new DLinkedNode();
  tail.post = null;

  head.post = tail;
  tail.pre = head;
}

public int get(int key) {

  DLinkedNode node = cache.get(key);
  if(node == null){
    return -1; // should raise exception here.
  }

  // move the accessed node to the head;
  this.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;

    this.cache.put(key, newNode);
    this.addNode(newNode);

    ++count;

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

}