What is LRU cache and how to implement it in scala?

Reading Time: 2 minutes

In this blog, we are going to know about LRU Cache and how to implement it in Scala Language.

LRU CACHE implementation in scala

What is LRU Cache?

Least Recently Used Cache is an algorithm used for cache eviction. As the name is suggesting Least Recently Used item will be evicted here. Basically, it removes the least recently used page/frame when the capacity or size of the cache is full and a new page is added which is not there in the cache.

LRU explained

How we can implement LRU Cache?

Here we will use LinkedHashSet which is a scala collection.LinkedHashSet allows us to store elements that are not repeatable, and it stores elements in the order they were inserted into it.

FlowChart :

This is the flow chart showing how our code will run.

LRU cache flowchart

Code :

This is the code for how we can implement it in scala language using LinkedHashSet.

import scala.collection.mutable
class LRUCache {
  val  hashSet =mutable.LinkedHashSet.empty[String]
  def manipulatePage(page: String,capacity:Int): mutable.LinkedHashSet[String] = {
    if (hashSet contains page) {
      hashSet.remove(page)
      hashSet.addOne(page)
      hashSet
    } else { if (hashSet.size == capacity) {
      hashSet.remove(hashSet.head)
      hashSet.add(page)
      hashSet
    } else {
      hashSet.add(page)
      hashSet
    }
    }
  }
}

object LRUCache extends App {
  var Obj = new LRUCache()
  val Pages = Array(1,5,5,3,8,9,7,4,2,4,3,9,5,0,5)
  val capacity = 3
  for(i <- 0 to 14){
    val Page = Pages(i).toString
    println(Obj.manipulatePage(Page,capacity))
  }
}
OUTPUT:
                              
LinkedHashSet(1)
LinkedHashSet(1, 5)
LinkedHashSet(1, 5)
LinkedHashSet(1, 5, 3)
LinkedHashSet(5, 3, 8)
LinkedHashSet(3, 8, 9)
LinkedHashSet(8, 9, 7)
LinkedHashSet(9, 7, 4)
LinkedHashSet(7, 4, 2)
LinkedHashSet(7, 2, 4)
LinkedHashSet(2, 4, 3)
LinkedHashSet(4, 3, 9)
LinkedHashSet(3, 9, 5)
LinkedHashSet(9, 5, 0)
LinkedHashSet(9, 0, 5)

Conclusion

Here we have understood what Least Recently Used Cache is and how we can implement that in scala language. If you want to see how to implement it in other languages you can check: Geek for Geeks

Written by 

Divyansh Devrani is a Software Consultant having experience in the Scala Ecosystem. He has worked on technologies like Scala, Akka, Play, and Postgre. He is recognized as a good team player who wants to interact with new technologies. He loves to learn new things His hobbies include listening to muisc, watching movies and anime.