操作系统中的页面置换算法—LRU置换算法

链表和散列表实现：

import java.util.HashMap;

/**
 * LRU算法——least Recently Used（最近最久未使用）
 *    他是一个按照非常著名的计算机操作系统基础理论得来的,所有的页面置换算法都是以**最佳置换算法**作为参考的：
 *   最近使用的页面数据在未来一段时间内仍然会被使用，已经很久没有使用的页面数据可能在很长   的一段时间内仍然不会被访问主要衡量的指标是使用时间。
 * @author zc
 *
 */
public class LRUSroted<K,V> {
	private int currentSize;//当前的大小 
    private int capcity;//总的容量
    private HashMap<K,Node> caches;//所有的Node结点【放入到一个HashMap缓冲区】
	private Node first;//头结点
	private Node last;//尾结点
	//构造器
	public LRUSroted(int size){
		this.currentSize = 0;//初始化为0
		this.capcity = size;
		this.caches = new HashMap<K, Node>(size);
	}
	/**
	 * 添加元素
	 * @param key
	 * @param value
	 */
	public void put(K key,V value) {
		Node node =caches.get(key);
		if(node == null) {//node不存在
			if(caches.size() >= capcity) {//当前容量达最大值，需要移除掉最后一个元素
				caches.remove(last.key);
			}
			node = new Node(key, value);
		}	
		//node存在
		node.val = value;//覆盖原来的值
		moveToHead(node);//移动到头部
		caches.put(key, node);
	}
	/**
	 * 根据key取得结点
	 * @param key
	 * @return
	 */
	public Object get(K key) {
		Node node = caches.get(key);
		if(node == null) {
			return null;
		}
		moveToHead(node);
		return node.val;
	}
	/**
	 * 把当前结点移动到链表头部
	 * @param node
	 */
	public void moveToHead(Node node) {
		//当前结点就是第一个节点
		if(first == node) {
			return;//直接返回
		}
		/*
		 * 以下步骤就是移除这个节点，把这个节点放到链表的头部
		 */
		//当前结点是中间节点
		if(node.next != null) {//当前结点的下一个节点不为空
			//就把当前结点的下一个节点的pre指针指向当前结点的上一个结点
			node.next.pre = node.pre;
		}
		if(node.pre != null) {//当节点的上一个指针不为空
			//就把当前结点的上一个节点的下一个指针指向当前结点的下一个节点
			node.pre.next = node.next;
		}
		//当前结点是最后一个节点
		if(node == last) {
			last = node.pre;
		}
		//当前链表只有一个结点
		if(first == null  || last == null) {
			first = last = node;
		}
		node.next = first;//当前结点的下一个指针指向原来的头节点
		first.pre = node;//原来的的头节点的pre指针指向当前结点
		first = node;//把node覆盖掉原来的头节点【相当于改个名字】
		first.pre = null;//在把当前头节点的pre指针置空
	}
	/**
	 * 根据key移除结点
	 * @param node
	 * @return
	 */
	public Object removeByKey(K key) {
		Node node = caches.get(key);
		if(node == null) {//结点为空，直接返回为空
			return null;
		}else {//结点不为空
			//待删除节点是头节点
			if(first == node) {
				first = node.next;
			}
			//待删除节点是尾结点
			if(last == node) {
				last = node.pre;
			}
			//待删除及诶按是中间节点
			if(node.next != null) {
				node.next.pre = node.pre;
			}
			if(node.pre != null) {
				node.pre.next = node.next;
			}
		}
		//在HashMap容器中消除
		return caches.remove(key);
	}
	/**
	 * 移除尾部的结点
	 * @return
	 */
	public void removeLast() {
		//链表只有一个节点
		if(first == last) {
			first = last = null;
		}
		//有多个节点
		last = last.pre;
	    last.next = null;
	  
	}
	/**
	 * 移除全部的结点，即是清链表
	 */
	public void clear() {
		first = null;
		last = null;
		caches.clear();
	}
	
    @Override
	public String toString() {
		return  "first="
				+ first + ", last=" + last + "]";
	}
	public static void main(String[] args) {
    	LRUSroted<Integer, String> lru = new LRUSroted<Integer, String>(5);
        lru.put(1, "a");
        lru.put(2, "b");
        lru.put(3, "c");
        lru.put(4,"d");
        lru.put(5,"e");
        System.out.println("原始链表为:"+lru.toString());
//      System.out.println("原始链表为:"+lru.last.toString());
        System.out.println(lru.caches);
        
//        lru.get(4);
//        System.out.println("获取key为4的元素之后的链表:"+lru.toString());
// 
//        lru.put(6,"f");
//        System.out.println("新添加一个key为6之后的链表:"+lru.toString());
// 
//        lru.removeByKey(3);
//        System.out.println("移除key=3的之后的链表:"+lru.toString());
	}
	

}
/**
 * 内部Node类
 * @author zc
 *
 */
class Node{
	//键
	public Object key;
	//值
	public Object val;
	//前一个结点
	Node pre;
	//后一个结点
	Node next;
	//构造方法
	public Node(Object key,Object val) {
		this.key = key;
		this.val = val; 
	}
	@Override
	public String toString() {
		return "Node [key=" + key + ", val=" + val + "]";
	}
	
}