Data structure that supports efficient kick-out policy based on recently accessed items

Question

I need a data structure that would support the most efficient kick-out policy for items that are were requested the longest time ago. e.g I have bunch of items that are being requested time to time. when I run out of memory I want to kick out the oldest items in my data structure (hash map).

I was thinking about FIFO ds smth like Queue, but I am not sure how to deal with this situation:

--> a b c d a -->

a is both oldest and newest item. If on adding "a" again I need to search entire queue to delete it. It is very inefficient, but I cannot think of any efficient way of doing it. Maybe some kind of a tree structure that keeps the least accessed one at the top?

Are there any implementation of such data structure in Java already?

Answer 1

LinkedHashMap is the structure you're after. From the docs:

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

So you should just use the appropriate constructor:

Map<K, V> map = new LinkedHashMap<>(CAPACITY, LOAD_FACTOR, true);

The boolean argument determines if the map is access-order or insertion-order. true means access-order.

Furthermore, if you want your map to work as a LRU cache, you can create your own class that extends LinkedHashMap and overrides the removeEldestEntry method. Again, from the docs:

The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

This means that you could create your own class for the cache:

public class Cache<K, V> extends LinkedHashMap<K, V> {

    private static final int MAX_ENTRIES = 100;

    public Cache() {
        super(SOME_INITIAL_CAPACITY, SOME_LOAD_FACTOR, true);
    }

    protected boolean removeEldestEntry(Entry<K, V> entry) {
        return size() > MAX_ENTRIES;
    }
}

Usage:

Map<K, V> map = new Cache<>();

Answer 2

EDIT: LinkedHashMap has built-in functionality for this, see the other answer.

You could wrap a LinkedHashSet (or LinkedHashMap, depending on your use case) and re-insert items on access, moving them to the end. If you run out of memory, start deleting at the front.

class LruMap<K, V> {
  LinkedHashMap<K, V> map = new LinkedHashMap<>()

  V get(K key) {
    V result = map.remove(key);
    map.put(key, result);
    return result;
  }

  void put(K key, V value) {
    map.put(key, value);
  }

  void removeEldest() {
    if (map.size() > 0) {
      map.remove(map.keySet().iterator().next());
    }
  }
}