一个LRUCache实现
我写的一个LRUCache的实现
import java.util.Hashtable;public class LRUCache { class CacheNode { CacheNode prev; CacheNode next; Object key; Object value; } private int cacheSize; private int currentSize; private Hashtable<Object,CacheNode> nodes; private CacheNode first; private CacheNode last; public LRUCache(){} public LRUCache(int size){ this.cacheSize = size; this.nodes = new Hashtable<Object,CacheNode>(size); this.currentSize = 0; } public void moveToHead(CacheNode node){ if(first == node){ return; } if(node.prev != null){ node.prev = node.prev.next; } if(node.next != null){ node.next.prev = node.prev; } if(last == node){ last = node.prev; } if(first != null){ first.prev = node; node.next = first; } first = node; node.prev = null; if(last == null){ last = first; } } public void removeLast(){ if(last != null){ if(last.prev != null){ last.prev.next = null; } else { first = null; } last = last.prev; nodes.remove(last.key); currentSize--; } } public void put(Object key, Object value){ CacheNode node = nodes.get(key); if(node == null){ if(currentSize >= cacheSize){ if(last != null){ nodes.remove(key); } removeLast(); } else { currentSize++; } node = new CacheNode(); } node.key = key; node.value = value; moveToHead(node); nodes.put(key, node); } public Object get(Object key){ CacheNode node = nodes.get(key); if(node != null){ moveToHead(node); return node.value ; } return null; } public Object remove(Object key){ CacheNode node = nodes.get(key); if(node != null){ if(node.prev != null){ node.prev.next = node.next; } else { first = null; } if(node.next != null){ node.next.prev = node.prev; } if(first == node){ first = node.next; } if(last == node){ last = node.prev; } nodes.remove(key); currentSize--; return node.value; } return null; }}