Наименее недавно использованный кэш без использования LinkedHashMap - PullRequest
Новая
       26

Наименее недавно использованный кэш без использования LinkedHashMap

0 голосов
/ 28 февраля 2019

При попытке сделать наименьший недавно использованный кэш, как ожидается, сохранит все элементы, которые использовались самыми последними, и откажется от тех, которые не использовались в течение наибольшего времени, по мере его заполнения.Метод get () должен возвращать ноль в тех случаях, когда он не возвращает объект.Кроме того, предположим, что getMaxSize () вернет максимальное количество элементов, которые могут находиться в кэше.Мы не беспокоимся об объеме памяти или чем-то подобном - просто о количестве элементов.

Я знаю, что с LinkedHashMap это намного проще, но вы не можете использовать LinkedHashMap здесь.

Пока я это сделал, любая помощь будет оценена. 

import java.util.HashMap;
  class Entry {
    int value;
    int key;
    Entry left;
    Entry right;
}
public class LRUCache {

    HashMap<Integer, Entry> hashmap;
    Entry start, end;
    int LRU_SIZE = 4; // Here i am setting 4 to test the LRU cache
                        // implementation, it can make be dynamic
    public LRUCache() {
        hashmap = new HashMap<Integer, Entry>();
    }

    public int getEntry(int key) {
        if (hashmap.containsKey(key)) // Key Already Exist, just update the
        {
            Entry entry = hashmap.get(key);
            removeNode(entry);
            addAtTop(entry);
            return entry.value;
        }
        return -1;
    }

    public void putEntry(int key, int value) {
        if (hashmap.containsKey(key)) // Key Already Exist, just update the value and move it to top
        {
            Entry entry = hashmap.get(key);
            entry.value = value;
            removeNode(entry);
            addAtTop(entry);
        } else {
            Entry newnode = new Entry();
            newnode.left = null;
            newnode.right = null;
            newnode.value = value;
            newnode.key = key;
            if (hashmap.size() > LRU_SIZE) // We have reached maxium size so need to make room for new element.
            {
                hashmap.remove(end.key);
                removeNode(end);                
                addAtTop(newnode);

            } else {
                addAtTop(newnode);
            }

            hashmap.put(key, newnode);
        }
    }
    public void addAtTop(Entry node) {
        node.right = start;
        node.left = null;
        if (start != null)
            start.left = node;
        start = node;
        if (end == null)
            end = start;
    }

    public void removeNode(Entry node) {

        if (node.left != null) {
            node.left.right = node.right;
        } else {
            start = node.right;
        }

        if (node.right != null) {
            node.right.left = node.left;
        } else {
            end = node.left;
        }
    }
    public static void main(String[] args) throws java.lang.Exception {

        LRUCache lrucache = new LRUCache();
        lrucache.putEntry(1, 1);
        lrucache.putEntry(10, 15);
        lrucache.putEntry(15, 10);
        lrucache.putEntry(10, 16);
        lrucache.putEntry(12, 15);
        lrucache.putEntry(18, 10);
        lrucache.putEntry(13, 16);

        System.out.println(lrucache.getEntry(1));
        System.out.println(lrucache.getEntry(10));
        System.out.println(lrucache.getEntry(15));

}
...