删除 java 中的元素形式链表，意外行为

Question

我正在尝试使用 hashmap 和链表在 java 中实现 lru 缓存：

public static class LRUCache{
    LinkedList<Integer> ll;
    HashMap<Integer, Integer> map;
    //HashSet<Integer> map;
    int size;
    LRUCache(int n){
        ll = new LinkedList<>();
        map = new HashMap<>();
        size=n;
    }

    int refer(int page){
        
        if(map.containsKey(page)){
            Integer it = map.get(page);
            //System.out.println("m.get(page)= " + map.get(page));
            //System.out.println(it + " it+page " + page);
            ll.remove(it);
        } else{
            if(map.size() >= size){
                map.remove(ll.getLast());
                ll.removeLast();
            }
        }
        ll.addFirst(page);
        //System.out.println(page + " page+peek " + ll.peekFirst());
        map.put(page, ll.peekFirst());
        return page;
    }

}

在上面的 refer 函数中，对于在地图中找到页面的 if 条件，值已成功从链表中删除，我认为这不应该起作用，因为我只保留地图中的页面值. 现在有趣的是，当我把 ll.remove(page);在上面的代码中，它中断了，尽管页面的值和它是相同的。

int refer(int page){

        if(map.containsKey(page)){
            Integer it = map.get(page);
            //System.out.println("m.get(page)= " + map.get(page));
            //System.out.println(it + " it+page " + page);
            ll.remove(page);
        } else{
            if(map.size() >= size){
                map.remove(ll.getLast());
                ll.removeLast();
            }
        }
        ll.addFirst(page);
        //System.out.println(page + " page+peek " + ll.peekFirst());
        map.put(page, ll.peekFirst());`enter code here`
        return page;
    }

我对这种行为感到非常惊讶。

对于下面的测试用例，代码的第一个价格有效但第二个无效，唯一的区别是 ll.remove(it) 和 ll.remove(page) ，它的值和页面相同。

        void printCache(){
        System.out.print("| ");

        for(int i=0;i<ll.size();i++){
            System.out.print(ll.get(i) + " |" + " ");
        }
        System.out.println();
    }

}

public static void main(String[] args) {
    LRUCache lruCache = new LRUCache(4);


    lruCache.refer(11);
    lruCache.refer(12);
    lruCache.refer(13);
    lruCache.printCache();
    lruCache.refer(11);
    lruCache.printCache();
    lruCache.refer(14);
    lruCache.printCache();
    lruCache.refer(13);
    lruCache.printCache();
    lruCache.refer(15);
    lruCache.printCache();
}

Answer 1

保留两个集合对于缓存来说成本很高，为什么不使用单个集合。 Linkedhashmap 保持插入顺序。您还必须牢记并发性。也许同时命中两个会使您丢失数据。只需用 Collections.synchronizedMap 包裹地图。 Linkedhashmap 可以保留长类型的键。您可以将以毫秒为单位的时间作为键。然后你可以通过键搜索找到最后使用的元素或者只是简单地删除最后插入的元素。

Answer 2

在不深入研究代码的太多细节的情况下，在调用 ll.remove(page) 和调用 [=12= 时调用哪个方法之间存在很大差异].

调用ll.remove(it)时，it的类型是Integer，所以调用的方法是LinkedList.remove(Object)。来自此方法的文档：

Removes the first occurrence of the specified element from this list, if it is present....

而当你调用ll.remove(page)时，page的类型是int，所以你实际调用的是：LinkedList.remove(int)。来自此方法的文档：

Removes the element at the specified position in this list....

一种方法是删除 page 处的索引，而另一种方法是删除匹配 it.

的值

我认为您在调用 ll.remove(page) 时可能想做的是 ll.remove(new Integer(page))

这里有一个 simple code 演示了这个问题：

public static void foo(int x) {
    System.out.println("Called foo(int)");
}
public static void foo(Integer x) {
    System.out.println("Called foo(Integer)");
}
public static void main (String[] args) throws java.lang.Exception
{
    int page = 5;
    Integer it = new Integer(10);
    foo(page);
    foo(it);
    foo(new Integer(page));
}

删除 java 中的元素形式链表，意外行为

Removing an element form linked list in java, unexpected behavior

java

intellij-idea

lru

data-structures