页面置换算法-最久未被使用算法模拟java

页面置换算法 - 最久未被使用（Least Recently Used, LRU）是一种常用的计算机内存管理策略，它基于这样的假设：最近使用的数据在未来更有可能再次被访问。在Java中，LRU通常用于缓存系统，如`java.util.LinkedHashMap`。

在这种算法中，当系统需要释放物理内存空间以容纳新的页面时，它会淘汰最近最少使用的页面。LinkedHashMap内部维护了一个链表和哈希表结构，链表按照访问顺序排列，而哈希表则便于快速查找。当缓存满时，新插入的数据会替换掉链表头部的元素（即最近最少使用的），然后将被替换出去的节点移除并放入链表尾部。

模拟LRU算法在Java中，可以创建一个自定义类，包含一个双向链表（最近访问的在前头）和一个哈希表，每次添加、删除和查询操作都要更新这两个数据结构：

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private final int capacity;
    private Map<Integer, Node> map;
    private DoublyLinkedList dll;

    // 定义节点类，包含引用值、访问时间和指向前一后一个节点
    class Node {
        int key;
        Object value;
        Node prev;
        Node next;
        long accessTime;

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
            this.accessTime = System.currentTimeMillis();
        }
    }

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

    // 添加/替换操作
    public Object get(int key) {
        if (map.containsKey(key)) {
            updateAccessTime(map.get(key));
            dll.moveToFront(map.get(key));
            return map.get(key).value;
        } else {
            return null;
        }
    }

    public void put(int key, Object value) {
        if (map.containsKey(key)) {
            updateAccessTime(map.get(key));
            dll.moveToFront(map.get(key));
        } else {
            if (dll.size() >= capacity) {
                Node removedNode = dll.removeLast();
                map.remove(removedNode.key);
            }
            Node newNode = new Node(key, value);
            dll.addFirst(newNode);
            map.put(key, newNode);
        }
    }

    // 私有方法更新访问时间并在链表中移动节点
    private void updateAccessTime(Node node) {
        node.accessTime = System.currentTimeMillis();
        dll.update(node);
    }

    // 省略了 DoublyLinkedList 类的定义...
}