java - LRU缓存: linkedhashmap and iterator implementation not working

Question

我正在尝试使用 LinkedHashMap 和迭代器创建 LRU 缓存。它适用于许多测试用例。但对于一些大型测试用例，它会为 get() 生成一些不正确的输出。

对我来说，这段代码非常有意义。也许，我遗漏了一些东西，或者我对 linkedHashMap 的理解不完整。

有人能发现实现中的错误吗？不幸的是，我无法发布测试用例，因为它太大了。您可以尝试在 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);
    }
}

Answer 1

我可能会遗漏一些东西，但看起来你的 put 函数没有删除最近最少使用的项目。相反，它似乎从前面删除了第二项(您获得迭代器，调用 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);
    }`