How to Implement a FIFO Cache Using LinkedHashMap in Java?

In this guide, we will walk you through how to implement a FIFO cache in Java using the powerful LinkedHashMap class. FIFO (First-In-First-Out) is a simple but widely used cache eviction strategy. By the end of this tutorial, you’ll have a complete understanding of how to build a custom FIFO cache system that maintains the order of insertion and evicts the oldest entries when the cache size limit is reached.

What is a FIFO Cache?

A FIFO cache is a data structure that stores a fixed number of elements and evicts the oldest elements when the cache reaches its capacity. FIFO stands for “First-In-First-Out,” which means that the element that was added first will be the first one to be removed when the cache overflows. This strategy is particularly useful when you need to store a limited amount of data and ensure that the most recently added data remains available.

Why Use LinkedHashMap for FIFO Cache?

Java’s LinkedHashMap is an excellent choice for implementing a FIFO cache due to its built-in capabilities to maintain insertion order. A LinkedHashMap is a hash table and linked list combination, meaning it offers constant-time performance for basic operations like get and put, while also maintaining the order of insertion. This makes it easy to access the first (oldest) element and evict it when necessary.

Steps to Implement a FIFO Cache Using LinkedHashMap

To implement a FIFO cache using LinkedHashMap, you will need to perform the following steps:

Create a custom cache class: Define a class that encapsulates the cache logic, including insertion, access, and eviction.
Set the cache capacity: Decide on the maximum size of the cache.
Override the removeEldestEntry method: This method will be used to evict the oldest entries once the cache exceeds its capacity.
Test the cache implementation: Use the cache and test it with various scenarios to ensure the eviction logic works as expected.

Code Example of FIFO Cache Implementation

        
// FIFO Cache using LinkedHashMap

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

public class FIFOCache extends LinkedHashMap {
    private final int capacity;

    // Constructor to initialize the cache with a given capacity
    public FIFOCache(int capacity) {
        super(capacity, 0.75f, true);  // Load factor 0.75 and accessOrder set to true
        this.capacity = capacity;
    }

    // Override removeEldestEntry to implement the eviction logic
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }

    // Method to display the cache content
    public void printCache() {
        System.out.println("Cache content: " + this);
    }

    public static void main(String[] args) {
        FIFOCache cache = new FIFOCache<>(3);

        // Add entries to the cache
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");

        // Print cache
        cache.printCache(); // Expected: {1=A, 2=B, 3=C}

        // Adding another entry will evict the oldest entry (key 1)
        cache.put(4, "D");
        cache.printCache(); // Expected: {2=B, 3=C, 4=D}

        // Adding more entries will keep evicting the oldest entries
        cache.put(5, "E");
        cache.printCache(); // Expected: {3=C, 4=D, 5=E}
    }
}

Explanation of the Code

Let’s break down the key components of the code:

FIFOCache Class: The FIFOCache class extends LinkedHashMap and defines the cache behavior. We pass the cache capacity to the constructor, which is used to set the maximum number of entries the cache can hold.
Constructor: The constructor of the class calls the parent constructor with the specified capacity, a load factor of 0.75, and true for access order. This ensures the map maintains the order of insertion.
removeEldestEntry Method: This method is overridden to implement the FIFO eviction logic. When the size of the cache exceeds the specified capacity, the eldest entry (i.e., the first inserted element) is removed automatically.
printCache Method: This is a utility method to print the cache contents for easy debugging.
Test Scenario: In the main method, we add elements to the cache and test how the cache evicts the oldest entry when the capacity is exceeded.

Cache Behavior and Eviction

In the example provided, we initialize the cache with a capacity of 3. When four elements are added to the cache, the first element (key 1) is evicted because it was the oldest. The cache will continue to evict the oldest entry whenever the size exceeds the capacity, ensuring that the most recent entries are always kept.

Advantages of Using LinkedHashMap for FIFO Cache

The main advantage of using LinkedHashMap for implementing a FIFO cache is its built-in support for maintaining the insertion order, which is a key requirement for FIFO caches. Furthermore, LinkedHashMap provides constant-time get and put operations, making it an efficient choice for cache management.

Conclusion

Implementing a FIFO cache using LinkedHashMap in Java is straightforward and efficient. By leveraging the built-in methods of LinkedHashMap, you can quickly create a cache system that automatically evicts the oldest elements when the cache exceeds its capacity. This solution is not only simple to implement but also offers excellent performance for typical cache operations.

Please follow and like us: