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

Question

这是一个在求职面试中经常出现的问题。这个想法是定义一个数据结构，而不是使用 Java 内置的 LinkedHashMap。

LRU 缓存会删除最近最少使用的条目以插入新条目。所以，给定以下场景:

 A - B - C - D - E

其中 A 是最近最少使用的项目，如果我们要插入 F，我们需要删除 A。

如果我们通过 (key,value) 保存一个带有缓存条目的 HashMap 和一个包含元素键和使用时间的单独列表，这可以很容易地实现。但是，我们需要查询列表以找到最近最少使用的项目，这具有潜在的 O(n) 时间复杂度。

如何在 Java 中为通用对象和 O(1) 操作实现这种结构？

这不同于可能的重复，因为它侧重于效率(O(1) 操作)和实现数据结构本身，而不是扩展 Java。

Answer 1

从问题本身，我们可以看出查询链表时出现了O(n)运算的问题。因此，我们需要一种替代的数据结构。我们需要能够在不搜索的情况下从 HashMap 更新项目的最后访问时间。

我们可以保留两个独立的数据结构。一个带有 (Key,Pointer) 对的 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, null);
        mostRecentlyUsed = leastRecentlyUsed;
        cache = new HashMap<K, Node<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, null, 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++;
        }
    }
}