Какая польза от map.remove () в методе get следующей реализации LRU? - PullRequest
Новая
       11

Какая польза от map.remove () в методе get следующей реализации LRU?

0 голосов
/ 16 мая 2018


Я изучаю LRU и использую приведенный ниже фрагмент кода для понимания его реализации. Пожалуйста, дайте мне знать, как использовать вызов метода map.remove(key) в get(int key). Разве мы не можем просто использовать map.put(key,value), что обновит запись на карте для ключа.
Я ссылаюсь на код ниже. 

class LRUMap<K, V> extends LinkedHashMap<K, V>{
    private final int MAX_NUM;
    public LRUMap(int capacity) {
        super(capacity);
        MAX_NUM = capacity;
    }
    protected boolean removeEldestEntry(Map.Entry eldest) {
       return /*true*/ size() > MAX_NUM;
    }
}
public class LRU {
    LRUMap<Integer, Integer> map;
    public LRU(int capacity) {
        map = new LRUMap<Integer, Integer>(capacity);
    }
    public int get(int key) {
        if (map == null || map.get(key) == null)
           return -1;
        int value = map.get(key);
        map.remove(key);
        map.put(key, value);
        return value;
    }
    public void set(int key, int value) {
        if (map == null) return;
        get(key);
        map.put(key, value);
    }
}

Ответы [ 2 ]

0 голосов
/ 16 мая 2018

LRU = Наименее недавно использованный кеш.

Когда вы используете Key, оно должно стать последним использованным. Простое обновление не сделает его наиболее используемым за последнее время , поскольку оно не меняет индекс в базовом LinkedList.
Таким образом remove и положить его обратно. Таким образом, он становится самым последним.

0 голосов
/ 16 мая 2018

Это LRUMap расширяет LinkedHashMap, в котором содержится связанный список записей Map в порядке, в котором были вставлены ключи (первый ключ является первым ключом, добавленным к Map).

Когда вы реализуете структуру данных, которая использовалась в последнее время, вы хотите знать, какой элемент использовался в последнее время.Это элемент, который вы сначала удалите, когда исчерпаете пространство.

Теперь, если мы посмотрим на LinkedHashMap Javadoc:

Эта реализация отличается от HashMap тем, что онаподдерживает двусвязный список, проходящий через все его записи.Этот связанный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (порядок вставки). Обратите внимание, что порядок вставки не изменяется, если ключ повторно вставлен в карту.(Ключ k повторно вставляется в карту m, если m.put (k, v) вызывается, когда m.containsKey (k) возвращает true непосредственно перед вызовом.)

Мы видим, что вызов put(k,v) для ключа, уже присутствующего в Map, не влияет на порядок вставки.

Поэтому, когда вы получаете доступ к ключу Map, вы должны сначала удалить егоиз LinkedHashMap, а затем снова добавьте его, переместив его в конец связанного списка и фактически пометив его как последний использованный ключ (который является последним вставленным ключом).

Обратите внимание, чтометод set() также вызывает get(), что означает, что он также перемещает ключ в конец связанного списка, если он уже был в Map.

...