LRU Cache Key, Value, Node.Value Real World Interpretation

Question

I understand how in principle an LRU cache works. For example, see here: https://java2blog.com/lru-cache-implementation-java/

However, I am having great difficulty understanding how this is interpreted in a real world setting. For example, if I want to store objects (which have no natural numbering/order), I understand that the value (in the hashmap) is just a pointer to a node in the linked list, but what does the key represent?

Furthermore, what does the node.value represent? I think this the actual object which is being cached. However, how does this correspond to the key in the hashmap?

Welbog Welbog · Accepted Answer · 2020-02-26T21:06:42

A typical hashmap has a key and a value, both of arbitrary type. The key is the thing you want to index the structure by, and the value is the thing you want to store and retrieve. Consider a normal hashmap in Java:

Map<UUID, Person> peopleById = new HashMap<>();

You can pass in a UUID to a .get method and get the person associated with that UUID, if it exists.

The LRU caches used in the real world are like that as well:

Map<UUID, Person> cachedPeopleById = new LRUCache<>(10);

The UUID is the key, and the Person is the value.

The reference implementation you linked to doesn't use generics, it only supports int to int, which is the equivalent of Map<Integer, Integer>. The Node class in the reference implementation isn't something that ought to be exposed in public methods. So in that reference implementation, Node should be hidden, and delete(Node) and setHead(Node) should be private, because otherwise they expose implementation details of the cache.

A better implementation would be something more like this (doing this off the top of my head, might have compilation errors, for illustrative purposes only):

public class LRUCache <KeyType, ValueType> implements Map<KeyType, ValueType> {

    private static class Node <KeyType, ValueType> {
      KeyType key;
      ValueType value;
      Node prev;
      Node next;

      public Node(KeyType key, ValueType value){
        this.key = key;
        this.value = value;
      }
    }

    int capacity;
    HashMap<KeyType, Node> map = new HashMap<>();
    Node head=null;
    Node end=null;

    public LRUCache(int capacity) {
      this.capacity = capacity;
    }

    public ValueType get(KeyType key) {
      ...
    }

    public set(KeyType key, ValueType value) {
      ...
    }

    private void delete(Node<KeyType, ValueType> node) {
      ...
    }

    private void setHead(Node<KeyType, ValueType> node) {
      ...
    }

LRU Cache Key, Value, Node.Value Real World Interpretation

1 Answers