How to Implement LRU Cache in Java?

Introduction

LRU cache is a type of cache that evicts the least recently used items when the cache is full. It’s widely used in various applications to reduce latency and improve response times. Implementing an LRU cache can be achieved using different data structures, but LinkedHashMap is a popular choice due to its ability to maintain insertion order. This article will guide you through the process of creating an LRU cache using LinkedHashMap.

Prerequisites

Before we start, make sure you have a basic understanding of Java and data structures. You should also have a Java development environment set up on your machine. Familiarity with LinkedHashMap and its properties will be beneficial.

Implementation Steps

Here are the steps to implement an LRU cache in Java using LinkedHashMap:

• Create a class that extends LinkedHashMap.
• Override the removeEldestEntry method to evict the least recently used item.
• Define the cache's capacity.
• Implement get and put methods to interact with the cache.

Code Example

Here’s a sample code snippet that demonstrates how to implement an LRU cache:

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(3);
        cache.put("1", "one");
        cache.put("2", "two");
        cache.put("3", "three");
        System.out.println(cache.keySet()); // [1, 2, 3]

        cache.get("1");
        System.out.println(cache.keySet()); // [2, 3, 1]

        cache.put("4", "four");
        System.out.println(cache.keySet()); // [3, 1, 4]
    }
}

Explanation

In the code example, we extend LinkedHashMap and override the removeEldestEntry method. The constructor initializes the cache with a specified capacity and sets the access order to true, which ensures that the least recently accessed items are moved to the end of the map. The removeEldestEntry method is called automatically when a new entry is added, and it removes the eldest entry if the cache exceeds its capacity.

Conclusion

Implementing an LRU cache in Java using LinkedHashMap is a straightforward process. By following the steps outlined in this article, you can easily create an LRU cache that improves the performance of your applications. LRU caches are a valuable tool in software development, helping to reduce latency and improve response times.