在 LRU 缓存 java 实现中遇到未命中时的 SET 操作

Question

我在 Java 中使用我自己的 DoublyLinkedList 实现实现 LRU 缓存，该节点具有整数键和值，其中键表示页面标识符，值表示它在磁盘上的位置。此外，我正在使用 Hashmap 进行 O(1) 访问。我知道以下实施基础知识：

如果请求的键是缓存命中，那么return它的值（即它的位置）并将这个节点移动到 DoublyLinkedList 的前面。

我对另一个重要的方面有疑问，当它错过时。根据各种资源，当它未命中时，在我的案例中是关键的页码被设置为 LinkedList 的头部，同时这样做，如果我们遇到容量已满，那么我们删除末尾的元素，然后把它输入到前面。现在为了实现目的，当我将它放入缓存时，这样的页码（即键）的'value'应该是什么？我应该把它设置为垃圾吗？在我下面介绍的 'get' 方法的实现中，我正在 returning -1 当前未命中。

另外，在LRU缓存的实际生产代码中，缓存中包含的是页码还是这些页码处存储的实际值？ T

请帮我清除这方面的问题。谢谢

import java.util.HashMap;


public class LRU {

private static class Node {

    Node previous;
    Node next;
    int key;
    int value;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

Node head = null;
Node tail = null;

HashMap<Integer, Node> hmap = new HashMap<>();

public int get(int key) {
    if (hmap.containsKey(key)) {
        Node n = hmap.get(key);
        remove(n);
        moveToFront(n);
        return n.value;
    }
    return -1;
}

public void remove(Node n) {
    // if n is head
    if (n.previous == null) {
        head = head.next;
    } else {
        n.previous.next = n.next;
    }

    //if n is tail
    if (n.next == null) {
        tail = n.previous;
    } else {
        n.next.previous = n.previous;

    }
}

public void moveToFront(Node n) {
    if(n==head)
        return;
    if(n.next==null)
    {
        n.previous.next=n.next;
        tail = n.previous;                    
        n.previous = null;
        n.next = head;
        head = n;
    }
    else {
        n.previous.next=n.next;
        n.next.previous=n.previous;
    }
}

public void set(int key, int value) {

   }
}

Answer 1

术语缓存通常表示容量有限的键值对映射。在达到容量时尝试添加新的键值对将导致现有键值对之一被逐出，并添加新的键值对。通常，添加一对也是隐式发生的，作为尝试检索当前未存储在缓存中的键的值的函数（即缓存执行逐出，加载新对，并且 returns 值).

LRU（最近最少使用）是 select 要驱逐的对的可能策略之一，而不是唯一的策略。处理器数据高速缓存是高速缓存的一个例子，在硬件中实现，其中密钥是从一个地址获得的（通常只考虑一定数量的最高有效位），而值是包含该地址的内存的一部分。在这种情况下，缓存行包含驻留在内存中的数据副本。另一个例子是，在 OS 支持虚拟内存中， OS 分页在 OS 内核中作为硬件（MMU）和软件的组合实现。在此示例中，更接近您的描述，该对的值是托管虚拟页面的内存页面的物理地址。

所以当您问 "Also, in practical production code of LRU cache, does the cache contain the page numbers or actual values stored at those page numbers? T" 时，答案可能取决于我们谈论的是什么缓存。在您的情况下，尚不清楚缓存由什么支持。我假设它是某个文件中的偏移量。在那种情况下，我希望您的值是一个字节数组或代表文件一部分的字符串。对文件中偏移量 x 的访问将映射到键 = offset/PAGE_SIZE;如果 table 中不存在密钥，并且 table 已满，则最后一个节点可能是 "recycled"，设置替换现有密钥，读取文件内容在字节缓冲区中的偏移量 (key, key + PAGE_SIZE-1) 处，最后将页面作为第一个移动。

在 LRU 缓存 java 实现中遇到未命中时的 SET 操作

SET action upon encountering miss in LRU cache java implementation

java

caching

hashmap

lru

doubly-linked-list