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

Question

这是一个在求职面试中出现的问题.我们的想法是定义一个数据结构,而不是使用Java内置的LinkedHashMap.

LRU高速缓存删除最近最少使用的条目以插入新条目.因此,给出以下场景:

 A - B - C - D - E

如果A是最近最少使用的项目,如果我们要插入F,我们需要删除A.

如果我们通过(键,值)保存带有缓存条目的HashMap以及包含元素的键和使用时间的单独列表,则可以轻松实现这一点.但是,我们需要查询列表以找到最近最少使用的项目,具有潜在的O(n)时间复杂度.

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

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

Answer 1

从问题本身,我们可以看到在查询链表时出现O(n)操作的问题.因此,我们需要一种替代数据结构.我们需要能够在不搜索的情况下从HashMap更新项目的上次访问时间.

我们可以保留两个独立的数据结构.一个与(关键,指针)的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++;
        }
    }
}

Answer 2

通过leetcode questiton +简单单元测试的测试的实现如下.

我已经通过以下方式提出了拉取请求:https://github.com/haoel/leetcode/pull/90/files

LRUCache.java

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

public class LRUCache {

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

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

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

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

LRUCacheTest.java:

import java.util.ArrayList;

import org.junit.Test;
import static org.junit.Assert.*;

public class LRUCacheTest {

    private LRUCache c;

    public LRUCacheTest() {
        this.c = new LRUCache(2);
    }

    @Test
    public void testCacheStartsEmpty() {
        assertEquals(c.get(1), -1);
    }

    @Test
    public void testSetBelowCapacity() {
        c.set(1, 1);
        assertEquals(c.get(1), 1);
        assertEquals(c.get(2), -1);
        c.set(2, 4);
        assertEquals(c.get(1), 1);
        assertEquals(c.get(2), 4);
    }

    @Test
    public void testCapacityReachedOldestRemoved() {
        c.set(1, 1);
        c.set(2, 4);
        c.set(3, 9);
        assertEquals(c.get(1), -1);
        assertEquals(c.get(2), 4);
        assertEquals(c.get(3), 9);
    }

    @Test
    public void testGetRenewsEntry() {
        c.set(1, 1);
        c.set(2, 4);
        assertEquals(c.get(1), 1);
        c.set(3, 9);
        assertEquals(c.get(1), 1);
        assertEquals(c.get(2), -1);
        assertEquals(c.get(3), 9);
    }
}

removeEldestEntry()替代实现

不确定它是否值得,因为它需要相同数量的行,但这里是完成:

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

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

    public LinkedhashMapWithCapacity(int capacity) {
        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;
        } else {
            this.set(key, value);
        }
        return value;
    }

    public void set(int key, int value) {
        if (this.map.containsKey(key))
            this.map.remove(key);
        this.map.get(key);
    }
}

Answer 3

该LinkedHashMap的设计考虑到这一点

来自javadocs:

提供了一个特殊的构造函数来创建链接的哈希映射,其迭代顺序是其条目最后一次访问的顺序,从最近访问到最近(访问顺序).这种地图非常适合构建LRU缓存.调用put,putIfAbsent,get,getOrDefault,compute,computeIfAbsent,computeIfPresent或merge方法会导致访问相应的条目(假设它在调用完成后存在).如果替换值,则replace方法仅导致访问条目.putAll方法为指定映射中的每个映射生成一个条目访问,按照指定映射的条目集迭代器提供键 - 值映射的顺序.没有其他方法可以生成入口访问.特别是,对集合视图的操作不会影响后备映射的迭代顺序.

可以重写removeEldestEntry(Map.Entry)方法,以强制在将新映射添加到映射时自动删除过时映射的策略.

Answer 4

使用Stack和HashMap:

import java.util.HashMap;
import java.util.Stack;
public class LRU {
    private HashMap<String,Object> lruList;
    private Stack<String> stackOrder;
    private int capacity;
    LRU(int capacity){
      this.capacity = capacity;
      this.lruList = new HashMap<String, Object>(capacity);
      this.stackOrder = new Stack<String>();
    }
    public void put(String key, Object value){
      if(lruList.containsKey(key) || this.capacity < lruList.size() + 1) {
        if(lruList.containsKey(key)){
            String remove = key;
        }else{
            String remove = this.stackOrder.firstElement();
        }
        this.stackOrder.removeElement(remove);
        this.lruList.remove(remove);
      }
      this.lruList.put(key, value);
      this.stackOrder.add(key);
    }
    public Stack<String> get(){
      return this.stackOrder;
    }
    public Object get(String key){
      Object value = lruList.get(key);
      put(key, value);
      return value;
    }
}

public static void main(String[] args) {
    LRU lru = new LRU(3);
    lru.put("k1","v1");
    lru.put("k2","v2");
    lru.put("k3","v3");
    System.out.println(lru.get());
    lru.get("k1");
    System.out.println(lru.get());
    lru.put("k4","v4");
    System.out.println(lru.get());
}

输出:

[k1,k2,k3]

[k2,k3,k1]

[k3,k1,k4]