Java中带有Generics和O(1)操作的LRU缓存

Question

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

LRU缓存删除最近使用最少的条目以插入新条目。因此，考虑到以下情况：

 A - B - C - D - E

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

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

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

这与可能出现的重复不同，因为它关注的是效率(O(1) ops)和实现数据结构本身，而不是扩展Java的。

Answer 1

从问题本身可以看出，在查询链接列表时会出现O(n)操作的问题。因此，我们需要另一种数据结构。我们需要能够在不进行搜索的情况下从HashMap更新项的最后访问时间。

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

例如，我们的双链接列表可以如下所示：

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

我们需要保持一个指向LRU和MRU项目的指针。条目的值将存储在列表中，当我们查询HashMap时，我们将得到一个指向列表的指针。在get()上，我们需要将项目放在列表的最右边。在put(键，值)上，如果缓存已满，我们需要从列表和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++;
        }
    }
}

Answer 2

实现，它使用简单的单元测试通过 leetcode问题 的测试

我在这里提出了一个拉请求：https://github.com/haoel/leetcode/pull/90/files --这个代码后来在accessOrder = true的答案中得到了改进，而且我也不想再提出一个拉请求，所以这里的代码现在稍微好一些。

LRUCache.java

import java.util.Iterator;
import java.util.LinkedHashMap;

public class LRUCache {

    private int capacity;
    private LinkedHashMap<Integer,Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(16, 0.75f, true);
    }

    public int get(int key) {
        Integer value = this.map.get(key);
        if (value == null) {
            value = -1;
        }
        return value;
    }

    public void put(int key, int value) {
        if (
            !this.map.containsKey(key) &&
            this.map.size() == this.capacity
        ) {
            Iterator<Integer> it = this.map.keySet().iterator();
            it.next();
            it.remove();
        }
        this.map.put(key, value);
    }
}

LRUCacheTest.java

public class LRUCacheTest {
    public static void main(String[] args) {
        LRUCache c;

        // Starts empty.
        c = new LRUCache(2);
        assert c.get(1) == -1;

        // Below capcity.
        c = new LRUCache(2);
        c.put(1, 1);
        assert c.get(1) == 1;
        assert c.get(2) == -1;
        c.put(2, 4);
        assert c.get(1) == 1;
        assert c.get(2) == 4;

        // Above capacity, oldest is removed.
        c = new LRUCache(2);
        c.put(1, 1);
        c.put(2, 4);
        c.put(3, 9);
        assert c.get(1) == -1;
        assert c.get(2) == 4;
        assert c.get(3) == 9;

        // get renews entry
        c = new LRUCache(2);
        c.put(1, 1);
        c.put(2, 4);
        assert c.get(1) == 1;
        c.put(3, 9);
        assert c.get(1) == 1;
        assert c.get(2) == -1;
        assert c.get(3) == 9;

        // Double put does not remove due to capacity.
        c = new LRUCache(2);
        assert c.get(2) == -1;
        c.put(2, 6);
        assert c.get(1) == -1;
        c.put(1, 5);
        c.put(1, 2);
        assert c.get(1) == 2;
        assert c.get(2) == 6;
    }
}

removeEldestEntry() 替代实现

不确定它是否值得，因为它需要相同的行数，但这里是为了完整性：

import java.util.LinkedHashMap;
import java.util.Iterator;
import java.util.Map;

import java.io.*;

class LinkedhashMapWithCapacity<K,V> extends LinkedHashMap<K,V> {
    private int capacity;

    public LinkedhashMapWithCapacity(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

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

public class LRUCache {

    private LinkedhashMapWithCapacity<Integer,Integer> map;

    public LRUCache(int capacity) {
        this.map = new LinkedhashMapWithCapacity<>(capacity);
    }

    public int get(int key) {
        Integer value = this.map.get(key);
        if (value == null) {
            value = -1;
        }
        return value;
    }

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

在Ubuntu20.10，OpenJDK 11.0.10上测试。

Answer 3

考虑到这一点而设计的LinkedHashMap

来自javadocs：

提供了一个特殊的构造函数来创建一个链接的散列映射，其迭代顺序是最近一次访问其条目的顺序，从最近访问到最近访问(访问顺序)。这种地图非常适合于建立LRU缓存。调用put、putIfAbsent、get、getOrDefault、compute、computeIfAbsent、computeIfPresent或merge方法将导致对相应条目的访问(假设它在调用完成后存在)。如果替换该值，则替换方法只会导致对该项的访问。putAll方法根据指定映射的条目集迭代器提供键值映射的顺序，为指定映射中的每个映射生成一个条目访问。没有其他方法生成条目访问。特别是，对集合视图的操作不影响支持映射的迭代顺序。 可以重写removeEldestEntry(Map.Entry)方法，以便在向映射中添加新映射时强制强制执行自动删除陈旧映射的策略。