LRUCache学习渐进

package lrucache.tow; import java.util.HashMap; import java.util.Map; /** *LRUCache链表+HashMap实现 *@author wxisme *@time 2015-10-18 下午12:34:36 */ public class LRUCache<k v=""> { private final int initialCapacity; //容量 private Node head; //头结点 private Node tail; //尾结点 private Map<K, Node<k v="">> map; public LRUCache(int initialCapacity) { this.initialCapacity = initialCapacity; map = new HashMap<K, Node<k v="">>(); } /** * 双向链表的节点 * @author wxisme * * @param <k> * @param <v> */ private class Node<k v=""> { public Node pre; public Node next; public K key; public V value; public Node(){} public Node(K key, V value) { this.key = key; this.value = value; } } /** * 向缓存中添加一个K,V * @param key * @param value */ public void put(K key, V value) { Node<k v=""> node = map.get(key); //node不在缓存中 if(node == null) { //此时，缓存已满 if(map.size() >= this.initialCapacity) { map.remove(tail.key); //在map中删除最久没有use的K,V removeTailNode(); } node = new Node(); node.key = key; } node.value = value; moveToHead(node); map.put(key, node); } /** * 从缓存中获取一个K,V * @param key * @return v */ public V get(K key) { Node<k v=""> node = map.get(key); if(node == null) { return null; } //最近访问，移动到头部。 moveToHead(node); return node.value; } /** * 从缓存中删除K,V * @param key */ public void remove(K key) { Node<k v=""> node = map.get(key); map.remove(key); //从hashmap中删除 //在双向链表中删除 if(node != null) { if(node.pre != null) { node.pre.next = node.next; } if(node.next != null) { node.next.pre = node.pre; } /*只是为了保存头结点和尾结点。相当于给头尾结点做个标示，并不是真正的操作头尾节点(刚开始分析到这的时候，一直纳闷为将head.next赋值给head后，为何没有操作 head.next.pre=head.pre 。其实head和tail只是为了保存头尾结点便于后面的操作)*/ if(node == head) { head = head.next; } if(node == tail) { tail = tail.pre; } //除去node的引用 node.pre = null; node.next = null; node = null; } } /** * 把node移动到链表头部 * @param node */ private void moveToHead(Node node) { //切断node if(node == head) return ; if(node.pre !=null) { node.pre.next = node.next; } if(node.next != null) { node.next.pre = node.pre; } if(node == tail) { tail = tail.pre;/*因为是双链表不是 循环双链表，所以不用考虑tail.next*/ } if(tail == null || head == null) { tail = head = node; return ; } //把node移送到head node.next = head; head.pre = node; head = node; node.pre = null; } /** * 删除链表的尾结点 */ private void removeTailNode() { if(tail != null) { tail = tail.pre; tail.next = null; } } @Override public String toString() { StringBuilder cacheStr = new StringBuilder(); cacheStr.append("{"); //因为元素的访问顺序是在链表里维护的，这里要遍历链表 Node<k v=""> node = head; while(node != null) { cacheStr.append("[" + node.key + "," + node.value + "]"); node = node.next; } cacheStr.append("}"); return cacheStr.toString(); } } </k></k></k></k></k></v></k></k></k></k>本文为对这篇博客的学习(代码部分添加注释)http://www.cnblogs.com/wxisme/p/4889846.html