General

LRU cache

1. Use HashMap and DoubleLinkedList,

   Put the latest item to the tail of DoubleLinkedList

public class LRUCache {

    private class Node{
        Node prev;
        Node next;
        int key;
        int val;

        public Node(int key, int val){
            this.key = key;
            this.val = val;
            prev = null;
            next = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> cache = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)){
            return -1;
        }

        // remove cur
        Node cur = cache.get(key);
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;

        // move cur to tail        
        moveToTail(cur);
        return cache.get(key).val;
    }

    public void set(int key, int value) {
        if (get(key) != -1){
            cache.get(key).val = value;
            return;
        }

        if (cache.size() == capacity){
            cache.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);
        cache.put(key, insert);
        moveToTail(insert);
    }

    private void moveToTail(Node cur){
        cur.prev = tail.prev;
        cur.next = tail;
        tail.prev = cur;
        cur.prev.next = cur;
    }
}

1. Use the LinkedHashMap

   • LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

     If access order, the latest entry will be updated Override the removeEldestEntry method

public class LruCache extends LinkedHashMap{

  private int capacity;

  LruCache(final int capacity) {n
    super(capacity, 1, true); // true if access order, false if insertion order
    this.capacity = capacity;
  };

  @Override
  protected boolean removeEldestEntry(Map.Entry e) {
    return this.size() > capacity;
  }

  public Integer lookup(Integer key) {
    if (this.containsKey(key)){
      return (Integer)this.get(key);
    }else{
      return null;
    }
  }

  public void insert(Integer key, Integer value) {
    if (!this.containsKey(key)){
      this.put(key, value);
    }
  }

  public Boolean erase(Object key) {
    if (this.containsKey(key)){
      this.remove(key);
      return true;
    }else{
      return false;
    }
  }
}