在lru缓存java实现中遇到未命中时设置操作

n3schb8v  于 2021-07-09  发布在  Java
关注(0)|答案(1)|浏览(396)

我使用自己的doublylinkedlist实现在java中实现lru缓存,其中一个节点具有整数键和值,其中键表示页面标识符,值表示其在磁盘上的位置。另外,我使用hashmap进行o(1)访问。我知道以下实施的基本知识:
如果请求的键是缓存命中,则返回其值(即其位置)并将此节点移动到doublylinkedlist的前面。
我在另一个重要的方面有疑问,当它是一个错过。根据各种资源,当它是一个失误,然后在我的情况下的关键页码设置为linkedlist的头,而在这样做的时候,如果我们遇到的能力是充分的,那么我们删除的元素在最后,然后输入到前面。现在为了实现的目的,当我将页号(即键)放入缓存时,它的“值”应该是什么?我应该把它变成垃圾吗?在我下面介绍的“get”方法的实现中,我正在返回-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) {

   }
}
u1ehiz5o

u1ehiz5o1#

术语cache通常标识具有有限容量的键值对Map。当达到容量时,尝试添加新的键值对将导致现有键值对之一被逐出,而新的键值对将被添加。通常,一对的添加也是隐式进行的,作为尝试检索当前未存储在缓存中的密钥的值的函数(即缓存执行逐出、加载新对并返回值)。
lru(最近最少使用)是选择要逐出的对的可能策略之一,而不是唯一的策略。处理器数据高速缓存是在硬件中实现的高速缓存的示例,其中密钥是从地址(通常仅考虑特定数量的最高有效位)获得的,并且值是包含这种地址的存储器的一部分在这种情况下,高速缓存线包含驻留在存储器中的数据的副本。另一个例子是,在支持虚拟内存的操作系统中,操作系统分页实现为操作系统内核中硬件(mmu)和软件的组合。在本例中,更接近于您所描述的,该对的值是托管虚拟页的内存页的物理地址。
所以当你问“同样,在lru缓存的实际生产代码中,缓存是否包含页码或存储在这些页码处的实际值?答案可能取决于我们在说什么。在您的情况下,不清楚缓存是由什么支持的。我假设它是某个文件中的偏移量。在这种情况下,我希望您的值是表示文件一部分的字节数组或字符串。对文件中偏移量x的访问将Map到key=offset/page\u size;如果表中不存在键,并且表有容量,则可以“回收”最后一个节点,设置替换现有键,读取字节缓冲区中偏移量(键、键+页大小-1)处的文件内容,最后将页作为第一个移动。

相关问题