LRU-кеш: связанная реализация hashmap и итератора не работает - PullRequest
Новая
       35

LRU-кеш: связанная реализация hashmap и итератора не работает

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

Я пытаюсь создать кэш LRU, используя LinkedHashMap и итератор. Это работает для многих тестовых случаев. Но для некоторых больших тестовых случаев он выдает несколько неправильных выходных данных для get ().

Для меня код имеет смысл. Возможно, я что-то упустил или, возможно, мое понимание связанного с HashMap неполно.

Может кто-нибудь найти ошибку в реализации? К сожалению, я не могу опубликовать контрольный пример, так как он слишком большой. Вы можете попробовать запустить этот код на https://leetcode.com/problems/lru-cache/. 

class LRUCache {
    private LinkedHashMap<Integer, Integer> map;
    private int maxCap;

    public LRUCache(int capacity) {
        this.map = new LinkedHashMap<>();
        this.maxCap = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            int val = map.get(key);
            map.remove(key);
            map.put(key, val);
            return val;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (maxCap == map.size()) {
            Integer val = map.get(key);
            if (val != null) {
                map.remove(key);
            } else {
                Iterator<Integer> itr = map.keySet().iterator();
                if (itr.hasNext()) {
                    itr.next();
                    itr.remove();
                }
            }
        }
        map.put(key, value);
    }
}

1 Ответ

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

Я мог что-то упустить, но похоже, что ваша функция пут не удаляет наименее использованный элемент. Вместо этого он, кажется, удаляет второй элемент спереди (вы получаете итератор, вызываете next () один раз и удаляете). Вы хотите что-то вроде того, что у меня ниже?

`

public void put(int key, int value) {
        if (maxCap == map.size()) {
            Integer val = map.get(key);
            if (val != null) {
                map.remove(key);
            } else {
                Iterator<Integer> itr = map.keySet().iterator();
                // call next until we have the last value
                while (itr.hasNext()) {
                    // not the last value, so skip it
                    itr.next();
                }
                // remove the last value
                itr.remove()
            }
        }
        map.put(key, value);
    }`
...