Implementation of LRU Cache

Caching 

 Caches take advantage of the locality of reference principle: recently requested data is likely to be requested again. They are used in almost every layer of computing: hardware, operating systems, web browsers, web applications and more. A cache is like short-term memory: it has a limited amount of space, but is typically faster than the original data source and contains the most recently accessed items. Caches can exist at all levels in architecture but are often found at the level nearest to the front end, where they are implemented to return data quickly without taxing downstream levels.

Eviction policy

When the cache is full, we need to remove existing items for new resources. In fact, deleting the least recently used item is just one of the most common approaches. So are there other ways to do that?

As mentioned above, the strategy is to maximum the chance that the requesting resource exists in the cache. I’ll briefly mention several approaches here:

• Random Replacement (RR) – As the term suggests, we can just randomly delete an entry.
• Least frequently used (LFU) – We keep the count of how frequent each item is requested and delete the one least frequently used.
• W-TinyLFU – I’d also like to talk about this modern eviction policy. In a nutshell, the problem of LFU is that sometimes an item is only used frequently in the past, but LFU will still keep this item for a long while. W-TinyLFU solves this problem by calculating frequency within a time window. It also has various optimizations of storage.

Implementation of LRU-Cache

Least Recently Used Cache

package com.lrucache;

import java.util.HashMap;

/* Reference-https://www.programcreek.com/2013/03/leetcode-lru-cache-java/

 * The LRU cache is a hash table of keys and double linked nodes.

The hash table makes the time of get() to be O(1).

The list of double linked nodes make the nodes adding/removal operations O(1).

Data Structures used 1) HashMap 2) Doubly Linked List

*/

public class LRUCache {

     int capacity;

     Node head = null;

     Node end = null;

     HashMap<Integer, Node> map = new HashMap<Integer, Node>();

     public LRUCache(int capacity) {

          System.out.println("LRUCache of size 3 created");

          this.capacity = capacity;

     }

     /*

      * Check if resource exists in Map or not If Exist a) Remove resource from

      * DLL b) Set resource on head of DLL c) Return Resource value If doesn't if

      * exist , return -1

      */

     public int get(int key) {

          if (map.containsKey(key)) {

              Node n = map.get(key);

              remove(n);

              setHead(n);

              return n.value;

          }

          return -1;

     }

     public void remove(Node n) {

          System.out.println("Node " + n + "removed from DLL");

          if (n.pre != null) {

              n.pre.next = n.next;

          } else {

              head = n.next;

          }

          if (n.next != null) {

              n.next.pre = n.pre;

          } else {

              end = n.pre;

          }

     }

     public void setHead(Node n) {

          System.out.println("Node " + n + "  set at Head of DLL");

          n.next = head;

          n.pre = null;

          if (head != null)

              head.pre = n;

          head = n;

          if (end == null)

              end = head;

     }

     public void set(int key, int value) {

          /*

           * If resource exist, we need to fetch old value, Update it and remove

           * it from older location in DLL and set it as head.

           */

          if (map.containsKey(key)) {

              System.out.println("Entry already exist in 

              Cache,replacing older value to newer value");

              Node oldNode = map.get(key);

              oldNode.value = value;

              remove(oldNode);

              setHead(oldNode);

          } else {

              System.out.println("New key generated: " + key);

              Node newNode = new Node(key, value);

              /*

               * if Queue full, remove LRU resouce Remove it from map as well, Set

               * new Resouce at Head , Insert in HashMap as well

               */

              if (map.size() >= capacity) {

                   System.out.println("Space not available in Cache , hence deleting older nodes");

                   remove(end);

                   map.remove(end.key);

                   setHead(newNode);

              } else {

                   System.out.println("Enough space available, hence adding in DLL");

                   setHead(newNode);

              }

              map.put(key, newNode);

          }

     }

     public static void main(String[] args) {

          LRUCache lruCache = new LRUCache(3);

          lruCache.set(1, 10);

          lruCache.set(2, 20);

          lruCache.set(1, 30);

          System.out.println("Get node based on key 2: " + lruCache.get(2));

          System.out.println("Get node based on key 8: " + lruCache.get(8));

          lruCache.set(4, 40);

          lruCache.set(5, 50);

     }

}

Output

LRUCache of size 3 created

New key generated: 1

Enough space available, hence adding in DLL

Node Key: 1 Value: 10  set at Head of DLL

New key generated: 2

Enough space available, hence adding in DLL

Node Key: 2 Value: 20  set at Head of DLL

Entry already exist in Cache , thus replacing older value to newer value

Node Key: 1 Value: 30removed from DLL

Node Key: 1 Value: 30  set at Head of DLL

Node Key: 2 Value: 20removed from DLL

Node Key: 2 Value: 20  set at Head of DLL

Get node based on key 2: 20

Get node based on key 8: -1

New key generated: 4

Enough space available, hence adding in DLL

Node Key: 4 Value: 40  set at Head of DLL

New key generated: 5

Space not available in Cache , hence deleting older nodes

Node Key: 1 Value: 30removed from DLL

Node Key: 5 Value: 50  set at Head of DLL