具有泛型和O(1)操作的Java中的LRU缓存

我们可以保留两个单独的数据结构.具有(键,指针)对的HashMap和双向链表,将作为删除和存储值的优先级队列.从HashMap中,我们可以指向双向链表中的一个元素,并更新其检索时间.因为我们直接从HashMap到列表中的项目,所以我们的时间复杂度保持在O(1)

例如,我们的双向链表可能如下所示：

least_recently_used  -> A <-> B <-> C <-> D <-> E <- most_recently_used

我们需要保留指向LRU和MRU项目的指针.条目值将存储在列表中,当我们查询HashMap时,我们将获得一个指向列表的指针.在get()上,我们需要将该项目放在列表最右侧.在put(key,value)上,如果缓存已满,我们需要从列表和HashMap中删除列表最左侧的项.

以下是Java中的示例实现：

public class LRUCache<K,V>{

    // Define Node with pointers to the previous and next items and a key,value pair
    class Node<T,U> {
        Node<T,U> previous;
        Node<T,U> next;
        T key;
        U value;

        public Node(Node<T,U> previous,Node<T,U> next,T key,U value){
            this.previous = previous;
            this.next = next;
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<K,Node<K,V>> cache;
    private Node<K,V> leastRecentlyUsed;
    private Node<K,V> mostRecentlyUsed;
    private int maxSize;
    private int currentSize;

    public LRUCache(int maxSize){
        this.maxSize = maxSize;
        this.currentSize = 0;
        leastRecentlyUsed = new Node<K,V>(null,null,null);
        mostRecentlyUsed = leastRecentlyUsed;
        cache = new HashMap<K,V>>();
    }

    public V get(K key){
        Node<K,V> tempNode = cache.get(key);
        if (tempNode == null){
            return null;
        }
        // If MRU leave the list as it is
        else if (tempNode.key == mostRecentlyUsed.key){
            return mostRecentlyUsed.value;
        }

        // Get the next and previous nodes
        Node<K,V> nextNode = tempNode.next;
        Node<K,V> previousNode = tempNode.previous;

        // If at the left-most,we update LRU 
        if (tempNode.key == leastRecentlyUsed.key){
            nextNode.previous = null;
            leastRecentlyUsed = nextNode;
        }

        // If we are in the middle,we need to update the items before and after our item
        else if (tempNode.key != mostRecentlyUsed.key){
            previousNode.next = nextNode;
            nextNode.previous = previousNode;
        }

        // Finally move our item to the MRU
        tempNode.previous = mostRecentlyUsed;
        mostRecentlyUsed.next = tempNode;
        mostRecentlyUsed = tempNode;
        mostRecentlyUsed.next = null;

        return tempNode.value;

    }

    public void put(K key,V value){
        if (cache.containsKey(key)){
            return;
        }

        // Put the new node at the right-most end of the linked-list
        Node<K,V> myNode = new Node<K,V>(mostRecentlyUsed,key,value);
        mostRecentlyUsed.next = myNode;
        cache.put(key,myNode);
        mostRecentlyUsed = myNode;

        // Delete the left-most entry and update the LRU pointer
        if (currentSize == maxSize){
            cache.remove(leastRecentlyUsed.key);
            leastRecentlyUsed = leastRecentlyUsed.next;
            leastRecentlyUsed.previous = null;
        }

        // Update cache size,for the first added entry update the LRU pointer
        else if (currentSize < maxSize){
            if (currentSize == 0){
                leastRecentlyUsed = myNode;
            }
            currentSize++;
        }
    }
}