LRU Cache Example

Question

Please check the following the LRU cache implementation.

Thanks for the valuable comments

import java.util.HashMap;
import java.util.Map;
public class LRUCache {
 HashMap<Integer, Node> lruHashMap = new HashMap<>();
 private final int DEFAULT_CACHE_SIZE =5;
 int capacity = 0;
 class Node{
 int value;
 Node prev, next;
 public Node(int value, Node prev, Node next){
 this.value = value;
 this.prev = prev;
 this.next = next;
 }
 public Node(int value){
 this.value = value;
 this.prev = null; this.next = null;
 }
 }
 Node head;
 Node tail;
 public void addData(int value){
 if(head == null) {
 head = new Node(value);
 tail = head;
 capacity++;
 lruHashMap.put(value, head);
 return;
 }
 if( lruHashMap.containsValue(value)) {
 // Item already at the linkedList and map
 // Delete node first
 Node deleteNode = lruHashMap.get(value);
 deleteNode.next.prev = deleteNode.prev;
 deleteNode.prev.next = deleteNode.next;
 deleteNode = null;
 }
 Node newNode = new Node(value,null,head);
 // Add item to head
 head.prev = newNode;
 head = head.prev;
 lruHashMap.put(value,newNode);
 ++capacity;
 checkSize(capacity);
 }
 private void checkSize(int capacity) {
 if(capacity > DEFAULT_CACHE_SIZE) {
 // remove last element
 removeLast();
 }
 }
 private void removeLast() {
 int value = tail.value;
 tail = tail.prev;
 tail.next = null;
 --capacity;
 lruHashMap.remove(value);
 }
 private void getDataOfLRUCache(){
 for(Map.Entry<Integer,Node> entry: lruHashMap.entrySet()){
 System.out.print (entry.getKey() + " - " );
 System.out.println(entry.getValue() );
 }
 }
 public boolean isEmpty() {
 return capacity == 0;
 }
 public static void main(String args[]){
 LRUCache lruCache = new LRUCache();
 lruCache.addData(5);
 lruCache.addData(6);
 lruCache.addData(7);
 lruCache.addData(8);
 lruCache.addData(9);
 // lruCache.getDataOfLRUCache();
 lruCache.addData(11);
 lruCache.addData(12);
 lruCache.getDataOfLRUCache();
 }
}

• Dani Mesejo: You could use a LinkedHashMap is specially useful for implementing an LRUCache, as it maintains a double-linked list for you

Answer 1

I have some advices for you.

• Add the static keyword to the DEFAULT_CACHE_SIZE variable (all cap snake case = constant).

Use the size of the map instead of using the capacity variable

You can use java.util.HashMap#size. In my opinion, it will be less error-prone to do so (If you forget to update it, ect).

Avoid using C-style array declaration

In the main method, you declared a C-style array declaration with the args variable.

before

String args[]

after

String[] args

In my opinion, this style is less used and can cause confusion.

Potential issues

Never expose directly Arrays / Collections / Maps to external classes

In this case, the lruHashMap map is exposed to any other instances, I highly suggest that you put the private keyword to hide the instance. If you don’t do so, any other classes can edit the map directly and your class will lose control over its own data.

Always compare objects of the same type

In the method LRUCache#addData, when you are checking if the lruHashMap contains the value, you are comparing java.lang.Integer with Node. You probably wanted to use the java.util.HashMap#containsKey instead.

//[...]
if (lruHashMap.containsValue(value)) { // Bug, will always return false
//[...]

By setting the object null, when coming from a collection, it does not delete it from the collection.

In this case, in the LRUCache#addData method, you set the object null to delete it ? This will only affect the current reference of the variable deleteNode; not the object in the map.

// Item already at the linkedList and map
// Delete node first
Node deleteNode = lruHashMap.get(value);
deleteNode.next.prev = deleteNode.prev;
deleteNode.prev.next = deleteNode.next;
deleteNode = null; // Set the `deleteNode` to null

Refactored code

 public class LRUCache {
 private HashMap<Integer, Node> lruHashMap = new HashMap<>();
 private static final int DEFAULT_CACHE_SIZE = 5;
 private Node head;
 private Node tail;
 class Node {
 int value;
 Node prev, next;
 public Node(int value, Node prev, Node next) {
 this.value = value;
 this.prev = prev;
 this.next = next;
 }
 public Node(int value) {
 this.value = value;
 this.prev = null;
 this.next = null;
 }
 }
 public void addData(int value) {
 if (head == null) {
 head = new Node(value);
 tail = head;
 lruHashMap.put(value, head);
 return;
 }
 if (lruHashMap.containsKey(value)) {
 // Item already at the linkedList and map
 // Delete node first
 Node deleteNode = lruHashMap.get(value);
 deleteNode.next.prev = deleteNode.prev;
 deleteNode.prev.next = deleteNode.next;
 // lruHashMap.remove(value); uncomment if you want to remote the item from the map
 }
 Node newNode = new Node(value, null, head);
 // Add item to head
 head.prev = newNode;
 head = head.prev;
 lruHashMap.put(value, newNode);
 checkSize();
 }
 private void checkSize() {
 if (lruHashMap.size() > DEFAULT_CACHE_SIZE) {
 // remove last element
 removeLast();
 }
 }
 private void removeLast() {
 int value = tail.value;
 tail = tail.prev;
 tail.next = null;
 lruHashMap.remove(value);
 }
 private void getDataOfLRUCache() {
 for (Map.Entry<Integer, Node> entry : lruHashMap.entrySet()) {
 System.out.print(entry.getKey() + " - ");
 System.out.println(entry.getValue());
 }
 }
 public boolean isEmpty() {
 return lruHashMap.isEmpty();
 }
 public static void main(String[] args) {
 LRUCache lruCache = new LRUCache();
 lruCache.addData(5);
 lruCache.addData(6);
 lruCache.addData(7);
 lruCache.addData(8);
 lruCache.addData(9);
 // lruCache.getDataOfLRUCache();
 lruCache.addData(11);
 lruCache.addData(12);
 lruCache.getDataOfLRUCache();
 }
 }
```