How to Implement an LRU Cache in Java: LinkedHashMap vs. ConcurrentHashMap?

Developing an LRU Cache in Java

In this context, an LRU (Least Recently Used) cache makes the assumption that the least recently used entries hold less value and can be discarded when necessary to maintain cache capacity. To achieve this in Java, let's consider the following approaches:

1. LinkedHashMap with Synchronization

You have mentioned using LinkedHashMap with Collections#synchronizedMap. This is a valid approach, utilizing the built-in doubly-linked list structure of LinkedHashMap to maintain the LRU behavior, with synchronization safeguarding the cache in a multithreaded environment.

2. Concurrent Collections

While the new concurrent collections offer improved performance, they lack the built-in LRU functionality. Hence, extending the ConcurrentHashMap, by incorporating the logic of LinkedHashMap, could provide a highly concurrent LRU implementation.

Current Implementation

After considering the suggestions, you have opted for the LinkedHashMap Collections.synchronizedMap approach for now. Upon revisiting this in the future, extending ConcurrentHashMap might be a viable option.

Here's a snippet of your current implementation for reference:

<code class="java">private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    // Check if the cache exceeds its maximum size
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));</code>

This cache utilizes the removeEldestEntry method to remove the least recently used entry when the cache reaches its maximum size, maintaining the LRU behavior.

The above is the detailed content of How to Implement an LRU Cache in Java: LinkedHashMap vs. ConcurrentHashMap?. For more information, please follow other related articles on the PHP Chinese website!