LRUアルゴリズムの簡単な実現

package com.hanchao.test0809;

import java.util.Hashtable;

public class LRUCache {  
    /** 
     *      
     * @author Administrator 
     * 
     */  
    class CacheNode {  
        CacheNode prev;//      
        CacheNode next;//      
        Object value;//   
        Object key;//   
        CacheNode() {  
        }  
    }  
    
    private int cacheSize;  
    private Hashtable nodes;//      
    private int currentSize;  
    private CacheNode first;//     
    private CacheNode last;//     
  
    public LRUCache(int i) {  
        currentSize = 0;  
        cacheSize = i;  
        nodes = new Hashtable(i);//      
    }  
      
    /** 
     *         
     * @param key 
     * @return 
     */  
    public Object get(Object key) {  
        CacheNode node = (CacheNode) nodes.get(key);  
        if (node != null) {  
            moveToHead(node);  
            return node.value;  
        } else {  
            return null;  
        }  
    }  
      
    /** 
     *      
     * @param key 
     * @param value 
     */  
    public void put(Object key, Object value) {  
        CacheNode node = (CacheNode) nodes.get(key);  
          
        if (node == null) {  
            //            .  
            if (currentSize >= cacheSize) {  
                if (last != null)//          
                    nodes.remove(last.key);  
                removeLast();  
            } else {  
                currentSize++;  
            }  
              
            node = new CacheNode();  
        }  
        node.value = value;  
        node.key = key;  
        //             ，       .  
        moveToHead(node);  
        nodes.put(key, node);  
    }  
  
    /** 
     *       
     * @param key 
     * @return 
     */  
    public Object remove(Object key) {  
        CacheNode node = (CacheNode) nodes.get(key);  
        if (node != null) {  
            if (node.prev != null) {  
                node.prev.next = node.next;  
            }  
            if (node.next != null) {  
                node.next.prev = node.prev;  
            }  
            if (last == node)  
                last = node.prev;  
            if (first == node)  
                first = node.next;  
        }  
        return node;  
    }  
  
    public void clear() {  
        first = null;  
        last = null;  
    }  
  
    /** 
     *          
     *                 
     */  
    private void removeLast() {  
        //      ,       null.      （           ）  
        if (last != null) {  
            if (last.prev != null)  
                last.prev.next = null;  
            else  
                first = null;  
            last = last.prev;  
        }  
    }  
      
    /** 
     *       ，              
     * @param node 
     */  
    private void moveToHead(CacheNode node) {  
        if (node == first)  {
        	//            ，    
        	return;  
        }
        if (node.prev != null)  {
        	//              null,                      
        	node.prev.next = node.next;  
        }
        if (node.next != null)  {
        	//              null,                      
        	node.next.prev = node.prev;  
        }
        if (last == node)  {
        	//             ，                   
        	last = node.prev;  
        }
        if (first != null) { 
        	//        null,                    
        	//                    
            node.next = first;  
            first.prev = node;  
        }  
        first = node;  
        node.prev = null;  
        if (last == null)  {
        	last = first;  
        }
    }  

}

参考:http://gogole.iteye.com/blog/692103 
http://blog.chinaunix.net/uid-26147414-id-3435752.html 
http://dennis-zane.iteye.com/blog/128278