LRU 缓存键、值、Node.Value 真实世界解释

Question

我理解 LRU 缓存的原理原理。例如，参见此处：https://java2blog.com/lru-cache-implementation-java/

但是，我很难理解这在现实世界中是如何解释的。比如我要存储对象（没有自然的numbering/order），我理解value（在hashmap中）只是指向链表中节点的指针，但是key代表什么？

另外，node.value代表什么？我认为这是被缓存的实际对象。但是，这个怎么对应hashmap中的key呢？

Answer 1

一个典型的 hashmap 有一个键和一个值，都是任意类型。键是您要为结构编制索引的内容，值是您要存储和检索的内容。考虑 Java:

中的普通 hashmap

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

您可以将 UUID 传递给 .get 方法并获取与该 UUID 关联的人（如果存在）。

现实世界中使用的LRU缓存也是这样的：

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

UUID 是键，Person 是值。

您链接到的参考实现不使用泛型，它只支持 int 到 int，相当于 Map<Integer, Integer>。参考实现中的 Node class 不应该在 public 方法中公开。所以在那个参考实现中，Node 应该被隐藏，delete(Node) 和 setHead(Node) 应该是私有的，否则它们会暴露缓存的实现细节。

更好的实现应该是这样的（出于我的头脑，可能会出现编译错误，仅供说明）：

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 缓存键、值、Node.Value 真实世界解释

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

caching

linked-list

hashmap

lru

data-structures