Использовать LinkedHashMap для реализации кеша LRU

Я пытался реализовать кеш LRU с помощью LinkedHashMap. В документации LinkedHashMap (http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html) говорится:

Обратите внимание, что порядок вставки не изменяется, если ключ повторно вставлен в карту.

Но когда я делаю следующие puts

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int size;

    public static void main(String[] args) {
        LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(1, 1);
        cache.put(3, 3);

        System.out.println(cache);
    }

    private LRUCache(int size) {
        super(size, 0.75f, true);
        this.size = size;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > size;
    }

    public static <K, V> LRUCache<K, V> newInstance(int size) {
        return new LRUCache<K, V>(size);
    }

}

Выходной сигнал

{1=1, 3=3}

Что указывает на то, что повторно вставленный код повлиял на порядок. Кто-нибудь знает какие-либо объяснения?

Ответ 1

Как указано @Jeffrey, вы используете accessOrder. Когда вы создали LinkedHashMap, третий параметр определяет порядок изменения порядка.

"true for access-order, false for insertion-order"

Для более подробной реализации LRU вы можете посмотреть http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

Ответ 2

Но вы не используете порядок вставки, вы используете порядок доступа.

порядок итераций - это порядок, в котором его записи были последними доступ к ним, с самого последнего доступа к самому недавнему (порядок доступа)

...

Вызов метода put или get приводит к доступу к соответствующая запись

Итак, это состояние вашего кеша при его изменении:

    LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);
    cache.put(1, 1); // { 1=1 }
    cache.put(2, 2); // { 1=1, 2=2 }
    cache.put(1, 1); // { 2=2, 1=1 }
    cache.put(3, 3); // { 1=1, 3=3 }

Ответ 3

Вот моя реализация, используя LinkedHashMap в AccessOrder. Он переместит последний элемент доступа на передний план, который наносит только O (1), потому что базовые элементы организованы в двусвязном списке, а также индексируются хэш-функцией. Таким образом, операции get/put/top_newest_one все стоят O (1).

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int maxSize;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.maxSize = capacity;
    }

    //return -1 if miss
    public int get(int key) {
        Integer v = super.get(key);
        return v == null ? -1 : v;
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return this.size() > maxSize; //must override it if used in a fixed cache
    }
}