How to Implement LRU Cache in Java

How to Implement LRU Cache in Java

A Least Recently Used (LRU) cache is a type of data structure that stores frequently used items for fast access. It has a fixed capacity, and when the capacity is reached, it removes the least recently used item in order to make room for the new item. The idea behind this is that more recently used items are more likely to be used again soon.

Implementing an LRU cache in Java can be done using the LinkedHashMap class. This class provides an implementation of a hash table with a doubly-linked list running through it. The linked list allows entries to be efficiently removed when they exceed the maximum capacity.

Steps to Create LRU Cache in Java

1. Create a LinkedHashMap.
2. Override the removeEldestEntry() method.
3. Implement the removeEldestEntry() method.
4. Initialize the LinkedHashMap.
5. Use the put() method to add elements to the LRU cache.
6. Use the get() method to retrieve elements from the LRU cache.

Example

Here’s an example of how to create an LRU cache in Java using the LinkedHashMap class. We’re setting the initial capacity to 10 and specifying that the access order should be “true”, which means that the entries will be stored in the order in which they were last accessed.

// Create LinkedHashMap with specified capacity and access order
LinkedHashMap<Integer, Integer> lruCache = 
    new LinkedHashMap<Integer, Integer>(10, 0.75f, true) { 

  // Override the removeEldestEntry() method
  public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) 
  { 
    // Remove the eldest element whenever size of cache exceeds the capacity 
    return size() > CAPACITY; 
  } 
}; 

// Put elements to the LRU cache
lruCache.put(1, 10); 
lruCache.put(2, 20); 
lruCache.put(3, 30); 
lruCache.put(4, 40); 

// Retrieve elements from the LRU cache
System.out.println(lruCache.get(1)); 
System.out.println(lruCache.get(2)); 

// Output: 
// 10 
// 20

Conclusion

In this tutorial, we learned how to implement an LRU cache in Java using the LinkedHashMap class. We discussed the steps required to create an LRU cache and also provided an example.