Improve the LRU cache implementation so that eviction occurs based on the time of last access, not the time of addition.

To implement an LRU cache where eviction occurs based on the last access time rather than the insertion time, you can use a LinkedHashMap with access order set to true in Java.

Example implementation of an LRU cache with eviction based on last access:

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) {
        // true for access order, false for insertion order
        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<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        cache.get(1); // access key 1
        cache.put(4, "four"); // key 2 will be evicted as it was least recently used

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

In this example:

• LinkedHashMap with accessOrder=true maintains the order of elements based on the last access time.
• The removeEldestEntry method is called after inserting a new element and removes the oldest element based on access time if the size exceeds capacity.

Thus, eviction occurs based on the last access time, not the insertion time.