LRUキャッシュのJavaインプリメンテーションでミスが発生した場合のSETアクション

Question

私は、DoublyLinkedListの独自の実装を使用してJavaでLRUキャッシュを実装していますが、整数のキーと値を持つノードでキーがページ識別子を示し、ディスク。また、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) { 

    } 
} 

Answer 1

キャッシュという用語は、一般に、容量が制限されたキーと値のペアマップを識別します。容量に達したときに新しいペアを追加しようとすると、既存のキーと値のペアの1つが追い出され、新しいものが追加されます。通常、ペアの追加は、キャッシュに現在格納されていないキーの値を取得しようとする（つまり、キャッシュが追い出しを実行し、新しいペアをロードして値を返す）ための関数として暗黙的に発生します。

LRU（Least Recently Used）は、排除されるペアを選択するためのポリシーの1つで、唯一のものではありません。プロセッサデータキャッシュは、ハードウェアに実装されたキャッシュの一例であり、キーはアドレス（通常は特定の数の最上位ビットのみを考慮する）から得られ、その値はそのようなアドレスを含むメモリの一部であるキャッシュラインには、メモリに存在するデータのコピーが含まれています。 もう1つの例は、仮想メモリをサポートするOSで、OSカーネル内にHW（MMU）とソフトウェアの組み合わせとして実装されたOSページングです。この例では、説明に近いものの、ペアの値は、仮想ページをホストするメモリページの物理アドレスです。

「LRUキャッシュの実用的な生産コードでは、キャッシュにページ番号または実際の値が格納されていますか？」という質問に対しては、私たちが話しているキャッシュ。あなたの場合、キャッシュが裏付けされているものは明確ではありません。私はそれがいくつかのファイルのオフセットだと仮定します。その場合、私はあなたの値がバイト配列またはファイルの一部を表す文字列であることを期待します。ファイル内のオフセットxへのアクセスは、key = offset/PAGE_SIZEにマップされます。キーがテーブルに存在せず、テーブルの容量がある場合は、最後のノードを「リサイクル」することができます。既存のキーの置き換え、オフセット時のファイルの内容の読み取り（key、key + PAGE_SIZE-1 ）をバイトバッファに格納し、最後にページを最初に移動します。