Lru- Java实现

思想：
LRU 是操作系统中常用的页面置换策略。叫做最近最少使用。根据使用的最后调用时间作为判断来淘汰页面。
手写
比如说有一个页面序列[6,1,0,5,2,3,1,5,0,8,7,3,9],内存有四个页面存储块，其步骤以及各步的页面存储块情况如下：
第一步： 获取页面6，此时页面块为空，所以缺失，并存入页面块中。所以页面块情况：【6】【null】 【null】 【null】
第二步：请求获取1，同上
所以页面块情况：【6】【1】 【null】 【null】
第三步： 获取0，同上
所以页面块情况：【6】【1】 【0】 【null】
第四步：获取5 ，同上
所以页面块情况：【6】【1】 【0】 【5】
第五步：获取2，存储中没有，而且存储块已满，选择最近最少使用的替换掉，根据存储的顺序，页面6最早存入一直未使用，所以替换掉
所以页面块情况：【2】【1】 【0】 【5】
第六步：获取3，已满，选择最近最少使用的页面1 替换
所以页面块情况：【2】【3】 【0】 【5】
第七步：获取1，已满，选择0替换
所以页面块情况：【2】【3】 【1】 【5】
第八步：获取5，此时存储块中有，未缺页，更新5的使用时间。
所以页面块情况：【2】【3】 【1】 【5】
第八步 ：获取0，缺页，此时最近最少使用的是2，
所以页面块情况：【0】【3】 【1】 【5】
第九步：（类似以上的操作，只给出每步答案，可以自己对照）
页面块情况：【0】【8】 【1】 【5】
第十步：页面块情况：【0】【8】 【7】 【5】
第十一步：页面块情况：【0】【8】 【7】 【3】
第十二步：页面块情况：【9】【8】 【7】 【3】

代码实现并验证

思路：从刚才的计算可以看到，需要计算最近最少被使用的页面并将其删除并添加新的页面。
在这里，我使用的是HashMap作为存储的结构， key为页面号，value是一个递增的计数值（最小的表示最近最少被使用）

结构cap，模拟存储块，一共可以存四个页面 ，（方法有详细的注解，可以看代码理解）

class  Cap {
    HashMap<Integer,Integer> map = new HashMap<>();
    static final int  size = 4;
    static int  sum = 0;

    /**
     * 页面存入页面块的逻辑操作
     * @param value
     */
    public void put(int value){
        if(map.size()<size){
            map.put(value,sum);
        }else {
            if(map.containsKey(value)){
                map.put(value,sum);
            }else{
                int min = getMinKey();
                map.remove(min);
                map.put(value,sum);
            }
        }
        sum++;
    }


    public void show(){
        Set keys = map.keySet();
        System.out.print("此时存储情况为 "+map.size()+"：");
        for (Object key : keys) {
            System.out.print(key + " ");
        }
        System.out.println();
    }
    /**
     * 找到最小的value对应的key，及找到最近最少使用的页面
     * @return
     */
    private int getMinKey(){
        int min = Integer.MAX_VALUE;
        int retKey = 0;
        Iterator<Integer> iterator = map.keySet().iterator();
        while(iterator.hasNext()){
            int key = iterator.next();
            if(min>map.get(key)){
                min = map.get(key);
                retKey = key;
            }
        }
        return retKey;
    }
}

主方法测试，我这个偷懒把Cap类和测试方法写到一个java文件中了，使用了输入流Scanner 进行输入，输入的参数要用空格隔开

public class Lru2 {
    public static void main(String[] args) {
        Cap cap = new Cap();
        Scanner sca = new Scanner(System.in);
        System.out.println("输入页面访问序列");
        String str = sca.nextLine();
        String [] strs = str.split(" ");
        for (String s : strs) {
            cap.put(Integer.parseInt(s));
            cap.show();
        }
    }
}

以下为输出，由于hashMap是无序的，所以输出时与输入顺序不同，但这里我只想表示下内存块中的存储内容。