LRU Cache : Java Implementation
LRU Cache (Page Replacement Scheme)
LRU Cache is designed for finding the location of desired page on disk. It maintains a cache of page number and its location on disk.
Whenever there is a request for new page number, Following operation will be performed.
– If it is present in cache, it is moved to front of the list and location is returned.
– If it is not present , a new page mapping is done. If cache is not full, a new entry is added to front otherwise least recently used entry is removed and then a new entry to front is added..
It should support two main operation.
set(int key, int value) -To add page number and disk location entry in cache. If cache is full, it should discard least recently used entry and add new one.
get(int key)– Return location on disk for given page number else return -1. If entry is present, reorder it to front.
Data Structures Used for LRU Cache Implementation
DoublyLinkedList
We will use DoublyLinkedList for maintaining LRU Cache queue. Least recently used item will be present at end of list and latest used item will be present in front of list. Size of list will be equal to capacity of cache.
HashMap
We will use HashMap for efficient reordering and removal of least recently used items. Key will be pageNumber and Value will be DoublyLinkedList node.
Complete Java Source Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
import java.util.HashMap; public class LRUCache { // Capacity of LRUCache private int capacity; // Current size of LRUCache private int currentSize; // To represent Node of DoublyLinkedList class DoublyLinkedListNode { DoublyLinkedListNode prev; DoublyLinkedListNode next; int key; int value; public DoublyLinkedListNode(int key, int value) { this.key = key; this.value = value; } } // First node of DoublyLinkedList private DoublyLinkedListNode start; // Last node of DoublyLinkedList private DoublyLinkedListNode end; // Map for key and DoublyLinkedList node mapping private HashMap<Integer, DoublyLinkedListNode> nodeMap; public LRUCache(int capacity) { this.capacity = capacity; currentSize = 0; nodeMap = new HashMap<Integer, DoublyLinkedListNode>(); } /* To print all current items in LRUCache */ private void printLRUCache() { DoublyLinkedListNode traverseNode = start; while (traverseNode != null) { System.out.print("key " + traverseNode.key + " value " + traverseNode.value + " "); traverseNode = traverseNode.next; } System.out.println(); } /* To add item in LRUCache */ private void set(int key, int value) { if (nodeMap.containsKey(key)) { DoublyLinkedListNode node = nodeMap.get(key); node.value = value; bringToFront(node); } else { DoublyLinkedListNode insertNode = new DoublyLinkedListNode(key, value); if (currentSize < capacity) { addToFront(insertNode); currentSize++; } else { removeLastNode(); addToFront(insertNode); } } } /* To get item value in LRUCache */ private int get(int key) { if (nodeMap.containsKey(key)) { DoublyLinkedListNode node = nodeMap.get(key); bringToFront(node); return node.value; } else { return -1; } } /* To remove last node from queue */ private void removeLastNode() { DoublyLinkedListNode lastNode = nodeMap.remove(end.key); end = end.prev; if (end != null) end.next = null; lastNode = null; // make it eligible for GC } /* To add node in front of queue */ private void addToFront(DoublyLinkedListNode insertNode) { insertNode.next = start; insertNode.prev = null; if (start != null) start.prev = insertNode; start = insertNode; if (end == null) end = insertNode; nodeMap.put(insertNode.key, insertNode); } /* To reorder existing node to front of queue */ private void bringToFront(DoublyLinkedListNode node) { // detach node from list DoublyLinkedListNode prevNode = node.prev; DoublyLinkedListNode nextNode = node.next; // handle next node if (prevNode != null) prevNode.next = nextNode; else start = nextNode; // hanlde prev node if (nextNode != null) nextNode.prev = prevNode; else end = prevNode; // add to front of ist addToFront(node); } } |
Driver program to check working of LRU Cache Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public static void main(String[] args) { LRUCache lru = new LRUCache(5); for (int i = 5; i < 11; i++) { lru.set(i, i * 2); } System.out.println("LRU Cache after creation"); lru.printLRUCache(); lru.get(7); System.out.println("LRU Cache after retrieving 7"); lru.printLRUCache(); lru.set(11, 11 * 2); System.out.println("LRU cache on adding one more item. It will replace last one"); lru.printLRUCache(); } |
Output for above driver program
LRU Cache after creation
key 10 value 20 key 9 value 18 key 8 value 16 key 7 value 14 key 6 value 12
LRU Cache after retrieving 7
key 7 value 14 key 10 value 20 key 9 value 18 key 8 value 16 key 6 value 12
LRU cache on adding one more item. It will replace last one
key 11 value 22 key 7 value 14 key 10 value 20 key 9 value 18 key 8 value 16
