Caching technique for performance improvement.

Abstract:

In computing, cache algorithms (also frequently called cache replacement algorithmsor cache replacement policies) are optimizing instructions—or algorithms—that a computer program or a hardware-maintained structure can follow in order to manage a cache of information stored on the computer. When the cache is full, the algorithm must choose which items to discard to make room for the new ones.

 

Solution:

The cache is composed of the map and linkedlist. The map stores the unique identifier for each entry and the value is stored in the linked list.Every new entry is added to the tail of the list ,till the cache is full.Once the cache is full the LRU(least recently used) eviction policy is used to add the new entry.To perform this the old entry is removed from head and the new entry is added to tail of the list.

public class Cache {
private Map<Object, Node> map;
private MyLinkedList list;
private int cacheSize;
public Cache(int cacheSize) {
    this.cacheSize = cacheSize;
    this.map = new HashMap<Object, Node>();
    this.list = new MyLinkedList();
 }
public void invalidateCache() {
    this.cacheSize = cacheSize;
    this.map = new HashMap<Object, Node>();
    this.list = new MyLinkedList();
 }
public void invalidateEntry(Object key) {
    this.map.remove(key);
 }
public void put(Object key, Object val) {
    // check if pruning is needed
    if (map.size() == this.cacheSize) {
        this.prune();
    }
    Node node = new Node(val);
    node.setKeyRef(key);
    this.map.put(key, node);
    this.list.addLast(node);
 }
public boolean contains(Object key) {
    return this.map.containsValue(key);
 }
public Object get(Object key) {
    Node resObj = map.get(key);
    if (resObj != null) {
        this.list.addLast(resObj);
        return resObj.getObject();
    }
    return null;
 }
private void prune() {
    Node node = this.list.getHead();
    Node tempNode = node.getNext();
    tempNode.setPrev(null);
    this.list.setHead(tempNode);
    this.map.remove(node.getKeyRef());
  }
}

public class Node {
private Node next;
private Node prev;
private T object;
private T keyRef;
}

public class MyLinkedList {
private Node head;
private Node tail;
private AtomicInteger count= new AtomicInteger(0) ;

public MyLinkedList(Node head) {
    this.head = head;
    getCount().getAndIncrement();
    //count++;
}
public Node addLast(Node newNode) {
        if (this.getHead() != null) {
            Node lastNode = this.getTail();
            if (lastNode != null) {
                lastNode.setNext(newNode);
                newNode.setPrev(lastNode);
                this.setTail(newNode);
            } else {
                this.getHead().setNext(newNode);
                newNode.setPrev(this.getHead());
                this.setTail(newNode);
            }
            getCount().getAndIncrement();
            return this.getHead();
        } else {
            this.setHead(newNode);
            this.setTail(newNode);
            getCount().getAndIncrement();
            return this.getHead();
        }
 }
public Node addFirst(Object obj) {
        Node headNode = this.getHead();
        Node newNode = new Node(obj);
        newNode.setNext(headNode);
        headNode.setPrev(newNode);
        this.setHead(newNode);
        getCount().getAndIncrement();
        return this.getHead();
 }
public Node removeFirst() {
        Node newHead = this.getHead().getNext();
        this.setHead(newHead);
        getCount().getAndDecrement();
        return this.getHead();
 }
}

Cache Technique — Results