LRU置换算法（Java）
题目:
2 表示页面的容量
1 1 表示第一个位置处的key=1 value=1
2 2 表示第二个位置处的key=2 value=3
3 3 通过LRU算法置换策略 最近最少使用 那么就将key=1 value=1 置换为 key=3 value=3
1 查找key等于1的value
-1 -1表示不能存在
使用集合表示页，使用类对象来表示页面。
| 时间戳 | t1 |
t2 |
t3 | t4 | t5 | t6 | t7 | t8 | t9 |
| 页面序列 | (1,1) | (2,2) | (3,3） | （4,4） | （5,5） | （2,6） | （7,7） | （3,8） | （9,9） |
| (1,1)(t1) | (1,1)(t1) | (3,3)(t3) | (3,3)(t3) | (5,5)(t5) | (5,5)(t5) | (7,7)(t7) | (7,7)(t7) | (9,9)(t9) | |
| (2,2)(t2) | (2,2)(t2) | (4,4)(t4) | (4,4)(t4) | (2,6)(t6) | (2,6)(t6) | (3,8)(t8) | (3,8)(t8) |
站在Java的角度简单的分析一下：
我们可以采用集合来表示页，集合中的类对象表示页面，集合的容量（实际控制的长度）为页的容量。此时我们设计的类需要以下几个属性：时间戳，键，值。
在这里我们把时间戳设置成整数自增 表示时间自增。
大体思路就是：
{
首先我们设计的是无限循环，而且题目要求的使单行输入一个数字时结束输入，此时在页中查找时候存在key等于最后一个数字 的值 如果存在那么 就输出这个值。
就是这个终止条件我也思考了半天， 首先输入一行 用空格拆分成字符串数组，如数组的长度不等于2 那就循环结束，并且记录最后一个key值。
}
1.首先有一个页面需要缓存。
这个页面在页中存在，如果存在那么就更改时间戳为当前时间戳
这个页面在页中不存在，结果就是置换或者添加到页中。
如果这个页此时已经饱和了，那么就需要置换出最近最少使用的页，根据时间戳排序，将标号最小的时间戳与当前信息置换
否则，向页中继续添加就可以了。
2. 将之前记录的key值 与页中的key值比较存在返回value 否则返回-1；
package 算法;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
/**
* 时间戳作为key值 页面，页面序列作为value值
* @author NullChen
*/
public class LRU置换算法的设计 {
class Record implements Comparable<Record>{
private int tmp;
private int key;
private int value;
public Record(int tmp, int key, int value) {
super();
this.tmp = tmp;
this.key = key;
this.value = value;
}
public int getTmp() {
return tmp;
}
public void setTmp(int tmp) {
this.tmp = tmp;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
//比较键值 来比较时候包含
@Override
public boolean equals(Object obj) {
return this.getKey()==((Record)obj).getKey();
}
@Override
public int compareTo(Record o) {
return this.tmp-o.tmp;
}
@Override
public String toString() {
return "Record [tmp=" + tmp + ", key=" + key + ", value=" + value + "]";
}
}
public static void main(String[] args) {
LRU置换算法的设计 lru = new LRU置换算法的设计();
//使用list集合来模仿页面 list集合的大小来表示缓存的容量
//LRU 就是最近最少使用策略 如果这个key不存在 那么就添加到集合中或者替换最近最远使的 否在就替换已经存在的key
Scanner scnner =new Scanner(System.in);
//输入缓存的容量
int capy = scnner.nextInt();
//时间锤
int tmp = 0;
//页面
List<Record> page = new ArrayList<Record>();
//要查询的key
int checkKey = 0;
while(true) {
tmp++;
//如果要满足终止条件 那么就应该 输入一行
Scanner scanner =new Scanner(System.in);
String data = scanner.nextLine();
//拆分
String[] keyValue = data.split(" ");
int key = 0,value=0;
if(keyValue.length == 2) {
key = Integer.parseInt(keyValue[0]);
value = Integer.parseInt(keyValue[1]);
}else {
checkKey = Integer.parseInt(keyValue[0]);
break;
}
//判断在页面中是否存在
Record record = lru.new Record(tmp, key, value);
boolean isContain = page.contains(record);
//在集合中存在 那么就需要替换时间戳
if(isContain) {
Record isEx = page.get(page.indexOf(record));
isEx.setTmp(tmp);
}else {
//在集合中不存在
if(tmp<=capy) {
//页面没有被填充满
page.add(record);
}else {
//根据时间戳给list集合排序 将最小的调制第1个 每次替换第一个就行了
Collections.sort(page);
//替换时间戳最小的
Record re = page.get(0);
re.setKey(key);
re.setValue(value);
re.setTmp(tmp);
}
}
}
//查看一下 page 中此时的集合
for (Record record : page) {
System.out.println(record);
}
boolean isHaving = false ;
String msg ="";
//在 集合中 查找键为checkKey的值 没有返回-1 存在 返回值
for (Record record : page) {
if(record.getKey() == checkKey) {
isHaving = true;
msg=""+record.getValue();
break;
}
}
if(isHaving) {
System.out.println(msg);
}else {
System.out.println(""+(-1));
}
}
}