原题链接在这里：https://leetcode.com/problems/lru-cache/
可以通过HashMap 和 Double LinkedList来完成。每个key, value用一个Node 来储存，按照添加顺序一个一个放在list 的head后面。同时把<key, node>放在HashMap中。
get时看HashMap中是否有这个key, 有的话就找到对应的node, 在node里取出对应的value. 同时更新该node 在list中的位置。
set时分三种情况：1. 看HashMap中是否有这个key, 有的话说明本来就有这个key对应的node, 只需要把原有node的value更改并且更新该node 在list中位置即可。
2. HashMap中没有这个key, 同时HashMap的size未达到capacity, 那么新建一个node, 加入HashMap 和 list中即可。
3. HashMap中没有这个key, 同时HashMap的size已经等于capacity, 多加就要招标了，所以按照2中完成添加后要从HashMap 和 list中都去掉最老的node.
AC Java:
class Node{ Node prev; Node next; int key; int value; Node(int key, int value){ this.key = key; this.value = value; } } public class LRUCache { Node head; Node tail; int capacity; HashMap<Integer, Node> hm; public LRUCache(int capacity) { head = new Node(-1,-1); tail = new Node(1,1); head.next = tail; tail.prev = head; this.capacity = capacity; hm = new HashMap<Integer, Node>(); } public int get(int key) { if(hm.containsKey(key)){ Node p = hm.get(key); //error putToHead(p); //put p to the newest position of list return p.value; } return -1; } public void set(int key, int value) { if(hm.containsKey(key)){ Node p = hm.get(key); p.value = value; putToHead(p); //update p‘s position in the list }else if(hm.size() < capacity){ Node p = new Node(key, value); hm.put(key,p); putToHead(p); }else{ Node p = new Node(key,value); hm.put(key,p); putToHead(p); int oldKey = removeOldest(); //remove oldest node from the list hm.remove(oldKey); //remove oldest node from hashmap } } private void putToHead(Node p){ if(p.prev != null && p.next != null){ p.prev.next = p.next; p.next.prev = p.prev; } p.prev = head; p.next = head.next; head.next.prev = p; head.next = p; } private int removeOldest(){ Node oldest = tail.prev; int oldKey = oldest.key; oldest.prev.next = tail; tail.prev = oldest.prev; return oldKey; } }
另一种方法是用LinkedHashMap, 这种数据结构本身已经把HashMap按照添加顺序放好了。
可以参见这个网页：http://www.tutorialspoint.com/java/java_linkedhashmap_class.htm
所以实现起来很简洁，get时需要更新位置，更新位置是通过删掉旧的，复制一下加回去。
set时参照上面的三种情况即可。
AC Java:
import java.util.LinkedHashMap; public class LRUCache { LinkedHashMap<Integer, Integer> linkedHM; int capacity; public LRUCache(int capacity) { linkedHM = new LinkedHashMap<Integer, Integer>(); this.capacity = capacity; } public int get(int key) { if(linkedHM.containsKey(key)){ int val = linkedHM.get(key); linkedHM.remove(key); linkedHM.put(key,val); return val; } return -1; } public void set(int key, int value) { if(linkedHM.containsKey(key)){ linkedHM.remove(key); linkedHM.put(key,value); }else if(linkedHM.size() < capacity){ linkedHM.put(key,value); }else{ int oldKey = linkedHM.keySet().iterator().next(); linkedHM.remove(oldKey); linkedHM.put(key,value); } } }
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4935048.html