Monday, December 15, 2014

LRU Cache

I always joke about myself that my brain is partially an LRU cache with small capacity......

1. The cache is implemented by a doubly linked list and a hash map.
2. The cache has fixed capacity.
3. The constructor initialize a cache with head (-1, -1 )links to tail (-1, -1).
4. All nodes are inserted between head and tail and stored in the hash map with key equals to its key value.
5. Get the node from the map takes O(1) time, then moves the node before tail since it's the most recently accessed node.
6. If the map contains the node that needs to be set, alter the value of the node. Otherwise insert the node before the tail and remove the node next to head if the capacity of the cache is full.


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;
            this.prev = null;
            this.next = null;
        }
    }
    private int capacity;
    private HashMap hm = new HashMap();
    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 (!hm.containsKey(key))
            return -1;
        Node curr = hm.get(key);
        curr.prev.next = curr.next;
        curr.next.prev = curr.prev;
        MoveToTail(curr);
        return hm.get(key).val;
    }
    
    public void set(int key, int value) {
        if (get(key) != -1)
        {
            hm.get(key).val = value;
            return;
        }
        if (hm.size() == capacity)
        {
            hm.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }
        Node newNode = new Node(key, value);
        hm.put(key, newNode);
        MoveToTail(newNode);
    }
    private void MoveToTail(Node node)
    {
        node.prev = tail.prev;
        tail.prev = node;
        node.next = tail;
        node.prev.next = node;
    }
}

No comments:

Post a Comment