Least Recently Used (LRU)

It discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping “age bits” for cache-lines and track the “Least Recently Used” cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes.

Basic requirement to build a LRU cache
Fixed size: The cache needs to have some bounds to limit memory usage.
Fast access: The cache insert and lookup operations need to be fast preferably O(1) time.
Entry replacement algorithm: When the cache is full, the less useful cache entries are purged from cache. The algorithm to replace these entries is Least .

Recently Used (LRU) – or the cache entries which have not been accessed recently will be replaced.

More deep insight -

Fixed Size : – This scenario occurs when your data size is very huge and it is not possible to put the huge data into the memory. So, your cache would have a fixed sized memory allocation.

Fast access : – When you write algorithm to maintain least recently used cache, it must not effect much into the performance of insertion or retrieval operation which is the basic and primary goal which needs to be achieved.

Least Recently Used (LRU) :- It is the way you maintain your cache system. you probably would need some kind of mechanism or algorithm which finds the least used element in your cache when your fixed size catch is filled.

Lets try it out in Java.

In cache system we maintain a map where values will be internally linked so basically we will maintain a linked list around the values.

Algorithm : – We will crate a doubly linked list Node and keep the value into node. We will create two dummy nodes head and tail and at the time of node insertion we will insert after head and if the value exists into the cache we remove the node from linked list and again insert after head. So least used value will always remain at last or just before of tail node.

/**
*
* @author www.itguphup.com
* This is a wrapper class ove cacher data and internally a doubly link list.
* @param <K> – key
* @param <V> – value
*/
public class Node<K,V> {

  public Node<K,V> prev;
  public Node<K,V> next;
  public K key;
  public V data;

  public Node() {}

  public Node(K key, V data) {
    this.key = key;
    this.data = data;
  }
}

import java.util.HashMap;
import java.util.Map;

/**
*
* @author Subhrajyoti
*
* @param <K> – key
* @param <V> – value
*/
public class LRUSampleCache<K,V> {
  private Node<K, V> head;
  private Node<K, V> tail;
  private final int maxSize;
  private Map<K, Node<K,V>> map = null;
  private DAOInterface<K, V> daoInterface = new

  DAOInterfaceImpl();

  public LRUSampleCache(int maxSize) {
    this.maxSize = maxSize;
  //dummy Nodes
    head = new Node<K, V>(null, null);
    tail = new Node<K, V>(null, null);
    head.next = tail;
    tail.prev = head;
    map = new HashMap<K, Node<K, V>>                 (maxSize);
  }

  public Object get(Object key) {
    Node<K, V> node = map.get(key);
    if (node == null){
      node = daoInterface.getData(key);
      if(node==null)
        return null;
      addNodeToListAtHead(node);
      return node.data;
    }
    if (map.size() == 1)
      return node.data;
    removeNodeFromList(node);
    addNodeToListAtHead(node);
    return node.data;
  }

  public void put(K key, V data) {
    if (maxSize <= 0)return;
    Node<K, V> node = map.get(key);
    if (node != null) {
      removeNodeFromList(node);
      addNodeToListAtHead(node);
      node.data = data;
    } else {
      node = new Node<K, V>(key, data);
      map.put(key, node);
      addNodeToListAtHead(node);
    if (map.size() > maxSize) {
      map.remove(tail.prev.key);
      removeNodeFromList(tail.prev);
    }
  }
}

/**
* Adding element Node next to head
* @param node
*/
  private synchronized void addNodeToListAtHead(Node<K, V> node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
  }

/**
* remove the node from doubly linked list.
* @param node
*/
  private synchronized void removeNodeFromList(Node<K, V> node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    }
}

Download the java file – LRUSampleCache