java - 不使用 LinkedHashMap 的最近最少使用缓存

Question

尝试做最近最少使用的缓存预计将保留所有最近使用的项目，并丢弃在最长时间内未使用的项目，因为它已满。get() 方法在不返回 Object 的情况下应返回 null。此外，假设 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));

}

标签： javahashmaplru