用Java实现请求页式存储管理中页面置换算法LRU

在页式存储管理中，当物理内存中已经存放了所有的页面时，需要将某些页面从内存中置换出去，以给新的页面腾出空间。页面置换算法就是处理这个问题的算法。

LRU（Least Recently Used）是一种常见的页面置换算法，它的思想是将最近最少使用的页面置换出去。具体实现时，可以维护一个时间戳，每次访问某个页面时，更新该页面的时间戳，当需要置换页面时，选择时间戳最早的页面进行置换。

下面是用Java实现LRU页面置换算法的示例代码：

import java.util.HashMap;
import java.util.LinkedHashSet;

public class LRUCache {
    private HashMap<Integer, Integer> cache;
    private LinkedHashSet<Integer> set;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.set = new LinkedHashSet<>();
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            set.remove(key);
            set.add(key);
            return cache.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            set.remove(key);
        }
        if (cache.size() == capacity) {
            int leastUsed = set.iterator().next();
            set.remove(leastUsed);
            cache.remove(leastUsed);
        }
        cache.put(key, value);
        set.add(key);
    }
}

这里用了HashMap和LinkedHashSet来实现LRU页面置换算法。HashMap用于存储键值对，LinkedHashSet用于维护页面的访问时间顺序。具体实现中，get方法用于获取某个页面的值，如果该页面存在，则将其从LinkedHashSet中移除并添加到末尾，以更新访问时间。put方法用于插入一个键值对，如果该键已经存在，则将其从LinkedHashSet中移除；如果cache已经满了，则需要将最久未使用的页面从cache和LinkedHashSet中移除；最后将新的键值对添加到cache和LinkedHashSet中。