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

Table of contents

Reading Time: 2 minutes

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

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.

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.

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