LRU Cache

In computers, cache memory provides fast access to processor by storing frequently used computer programs, data and applications; However size of cache memory is relatively small. Because of the size constraint, it is required to invalidate data from cache and store new data frequently when it is full.So, algorithms are required to decide which data should be removed from cache.

One of the algorithm to decide what to remove from cache is Least Recently Used (LRU). In this algorithm, least recently used data is removed from cache.

Example:

Imagine cache size is 4. Initially data D1,D2 and D3 requested by some program.

– As initially cache is empty, all three data elements inserted in cache sequentially.

-Then D1 and D2 data access requested. As, it is already in cache, D1 and D2 will be accessed directly from cache.

-Now new data D4 requested by program ,as it is not in cache, D4 added in cache.

-Now new data D4 requested by program. As cache does not have D5 stored ,D5 needs to be added in cache.

However, cache is already full, so we need to replace data in cache. As per LRU algorithm, we will find least recently used data in cache. For current scenario it is D3. Though, D3 inserted in cache after D1 and D2, data D1 and D2 accessed after insertion however D3 not, so we will remove D3 from cache and insert D5 in cache.

Input : Cache capacity and <key,value> pair as data.

Problem statement:(Leetcode problem no. 146)

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

To keep track of recently used data, we will use LinkedHashSet data structure and input data will be stored in HashMap as input is in the form of key, value.

Logic:

– Whenever new data is put in cache(HashMap) using set function check if cache is completely filled, if not add that value to cache. Insert key value in LinkedHashSet. Else, extract oldest element from LinkedHashSet (which will be first element in hashSet) and remove that from HashMap and then insert new <key,value>.

– If get function called which is accessing data already present in cache, value for the key is returned from HashMap if present, else -1. Requested key removed from LinkedHashSet and inserted again. Removal of required as LinkedHashSet keep keys in order of access.

– If set function called however that key is already present in the cache (HashMap), we need to update value of that key and make it most recently used by removing key from HashSet and inserting it again.

Code:

import java.util.HashMap;
import java.util.LinkedHashSet;

public class LRUCache {
    
     private HashMap<Integer,Integer> valueDict;
     private LinkedHashSet<Integer> list;
     private int cap;
	
    public LRUCache(int capacity) {
        cap = capacity;
		valueDict = new HashMap<Integer,Integer>();
		list = new LinkedHashSet<Integer>();
    }
    
    public int get(int key) {
      if(valueDict.containsKey(key))
	{
            list.remove(key);
            list.add(key);
	    return valueDict.get(key);
	}
       return -1;
    }
    
    public void set(int key, int value) {
        if(valueDict.containsKey(key))
     	   valueDict.put(key, value);
    	else
    	{
    	   if(valueDict.size() < cap)
    	      valueDict.put(key, value);
    	   else
    	     {
    		int first = 0;
    		for(int k : list)
    		 {
    		  first = k;
    		  break;
    		}
    		list.remove(first);
    		valueDict.remove(first);
    		valueDict.put(key, value);
    	      }
    	}
       if(list.contains(key))
          list.remove(key);
       list.add(key);
    }
}

import java.util.HashMap;

import java.util.LinkedHashSet;

public class LRUCache {

private HashMap<Integer,Integer> valueDict;

private LinkedHashSet<Integer> list;

private int cap;

public LRUCache(int capacity) {

cap = capacity;

valueDict = new HashMap<Integer,Integer>();

list = new LinkedHashSet<Integer>();

}

public int get(int key) {

if(valueDict.containsKey(key))

{

list.remove(key);

list.add(key);

return valueDict.get(key);

}

return -1;

}

public void set(int key, int value) {

if(valueDict.containsKey(key))

valueDict.put(key, value);

else

{

if(valueDict.size() < cap)

valueDict.put(key, value);

else

{

int first = 0;

for(int k : list)

{

first = k;

break;

}

list.remove(first);

valueDict.remove(first);

valueDict.put(key, value);

}

if(list.contains(key))

list.remove(key);

list.add(key);

}

Recent Posts

Algotutor