TRy HArD aT aNY TimE

LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。该算法的初衷是有内存管理而被提出来的，其目的是为解决“如何节省利用容量不大的内存为最多的进程提供资源”时如何减少过多的让进程去读取外存。
这里以链表法来实现LRU:
一点介绍
操作系统为每个进程维护一条链表，链表的每个结点记录一张页面的地址。调用一次页面，则把该页面的结点从链中取出，放到链尾；要装入新页，则把链头的页面调出，同时生成调入页面的结点，放到链尾。
LRU算法的理论基础是:局部性原理

/*
 *Created on 2008-7-24
 */
import java.io.Serializable;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Vector;

/**
 * @author anwx<a href="mailto:luckyanzi@china.com.cn">An Weixiao</a>
 * @version $Id$
 */
public class LRUTest {
    protected HashMap<Object, Serializable> cache;
    protected Vector<Object> cacheList;
    protected int capacity = 3;
    
    private int getCapacity(){
        return this.capacity;
    }
    
    private int getSize(){
        return cache.size();
    }
    public LRUTest(){
        this.cache = new HashMap<Object, Serializable>();
        this.cacheList = new Vector<Object>();
    }
    private void moveToTop(Object identifier) {
        cacheList.insertElementAt(identifier,0);
        if ( getSize() >= getCapacity() ) {
            String toBeDeleted = (String)cacheList.lastElement();
            cache.remove(toBeDeleted);
            int lastElement = cacheList.size();
            cacheList.remove(lastElement-1);
        }
    }
    public Object get(Object identifier) {
        if ( cache.containsKey(identifier) ) {
            moveToTop(identifier);
            Serializable co = (Serializable)cache.get(identifier);
            return co;
        }
        else {
            return null;
        }
    }
    
    public void put(Object identifier, Serializable value) { 
        if (  getSize() < getCapacity() ) {            
            if ( !cache.containsKey(identifier) ) {             
                cacheList.insertElementAt(identifier,0);
            }            
            cache.put(identifier,value);
        }
        else {
            cache.put(identifier,value);
            moveToTop(identifier);
        }
    }
    private void print(){
        System.out.println("data, key in cache");
        Object key = null;
        Serializable value = null;
        for(Iterator it = cache.keySet().iterator(); it.hasNext();){
            key = it.next();
            System.out.println(String.format("[%s, %s]", cache.get(key), key));
        }
        System.out.println("key info sequence");
        for(Object o: cacheList){
            System.out.println(o);
        }
    }
    public static void main(String args[]){
        LRUTest test = new LRUTest();
        test.put("1", "a");
        test.put("2", "b");
        test.put("3", "c");
        test.print();
        test.put("4", "d");
        test.put("5", "e");
        test.print();
    }
}