LRU Cache Key, Value, Node.Value Интерпретация реального мира - PullRequest
Новая
       36

LRU Cache Key, Value, Node.Value Интерпретация реального мира

0 голосов
/ 26 февраля 2020

Я понимаю, как в принципе работает LRU-кеш. Например, см. Здесь: https://java2blog.com/lru-cache-implementation-java/

Однако мне очень трудно понять, как это интерпретируется в условиях реального мира. Например, если я хочу сохранить объекты (которые не имеют естественной нумерации / порядка), я понимаю, что значение (в хэш-карте) является просто указателем на узел в связанном списке, но что представляет собой ключ?

Кроме того, что представляет собой node.value? Я думаю, что это фактический объект, который кэшируется. Однако как это соответствует ключу в хэш-карте?

1 Ответ

1 голос
/ 27 февраля 2020

Типичная хэш-карта имеет ключ и значение произвольного типа. Ключ - это то, чем вы хотите индексировать структуру, а значение - это то, что вы хотите сохранить и получить. Рассмотрим нормальную хэш-карту в Java: 

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 в эталонной реализации не должен быть представлен в методах publi c. Таким образом, в этой эталонной реализации 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) {
      ...
    }
...