Удаление связанного списка элемента формы в java, неожиданное поведение - PullRequest
Новая
       65

Удаление связанного списка элемента формы в java, неожиданное поведение

0 голосов
/ 20 июня 2020

Я пытаюсь реализовать кеш lru в java, используя hashmap и связанный список: 

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;
    }

}

В приведенной выше функции ссылки для условия 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), значения it и 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();
}

Ответы [ 2 ]

0 голосов
/ 20 июня 2020

Не вдаваясь в подробности вашего кода, существует очень большая разница между , который метод вызывается при вызове ll.remove(page), и при вызове ll.remove(it).

При вызове ll.remove(it), тип it - Integer, поэтому вызываемый метод - LinkedList.remove(Object). Из документации этого метода:

Удаляет первое вхождение указанного элемента из этого списка, если он присутствует ....

Пока при вызове ll.remove(page), тип page - int, поэтому вы фактически звоните: LinkedList.remove(int). Из документации этого метода:

Удаляет элемент в указанной позиции в этом списке ....

Один из методов - удаление индекса в page, в то время как другой удаляет совпадение значений it.

Я думаю, что вы, возможно, захотите сделать при вызове ll.remove(page) для достижения аналогичного поведения ll.remove(new Integer(page))

Вот простой код , демонстрирующий эту проблему: 

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));
}
0 голосов
/ 20 июня 2020

Хранить две коллекции дорого для кеша, почему бы вам не использовать одну коллекцию. Linkedhashmap сохраняет порядок вставки. Также вы должны помнить о параллелизме. Возможно, два удара одновременно будут стоить вам потери данных. Просто оберните карту с помощью Collections.synchronizedMap. Linkedhashmap может хранить длинный тип ключа. В качестве ключа можно указать время в миллисекундах. Затем вы можете найти последний использованный элемент с помощью поиска по ключу или просто удалив последний вставленный элемент.

...