Implement an LRU cache with eviction of old values (basic implementation).

To implement an LRU cache in Java, a common approach is to use a combination of LinkedHashMap with an overridden removeEldestEntry method, which automatically removes the oldest element when the size limit is reached.

Here's a basic example of an LRU cache implementation in Java:

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

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

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

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

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        cache.get(1); // access element 1 to update order
        cache.put(4, "four"); // will evict element with key 2

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

In this example:

• LinkedHashMap with accessOrder=true stores elements in order of last access.
• The removeEldestEntry method automatically removes the oldest element when the size exceeds the limit.
• Calling get makes the element "new" in access order.

This is a simple and efficient solution for an LRU cache in Java.