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