Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
https://oj.leetcode.com/problems/lru-cache/
什么是cache？
Cache(高速缓存)， 一个在计算机中几乎随时接触的概念。
CPU中Cache能极大提高存取数据和指令的时间，让整个存储器(Cache+内存)既有Cache的高速度，又能有内存的大容量；
操作系统中的内存page中使用的Cache能使得频繁读取的内存磁盘文件较少的被置换出内存，从而提高访问速度；
数据库中数据查询也用到Cache来提高效率；
即便是Powerbuilder的DataWindow数据处理也用到了Cache的类似设计。
Cache的算法设计常见的有FIFO(first in first out)和LRU(least recently used)。根据题目的要求，显然是要设计一个LRU的Cache。
梳理一下思路：对于Cache的每个数据块，我们设计一个数据结构来储存Cache块的内容，并实现一个双向链表，其中属性next和prev时双向链表的两个指针，key用于存储对象的键值，val用户存储要cache块对象本身。
Cache的接口：
查询：
-
-
根据键值查询hashmap，若命中，则返回节点，否则返回null。
-
从双向链表中删除命中的节点，将其重新插入到表头。
-
所有操作的复杂度均为O(1)。
-
插入：
-
-
将新的节点关联到Hashmap
-
如果Cache满了，删除双向链表的尾节点，同时删除Hashmap对应的记录
-
将新的节点插入到双向链表中头部
-
更新：
-
-
和查询相似
-
删除：
-
- 从双向链表和Hashmap中同时删除对应的记录。
思路：实现一个LRUCache的类，主要是get和set方法要保证高效。需要一个hashmap 和一个双向链表结合。hashmap用于在O(1)的时间内查找指定元素是否在cache里，而双向链表则允许在O(1)的时间移动元素到表头和删除尾部节点。
第三遍更新：直接利用HashMap 和 LinkedList 结合。缺点：LinkedList 的remove方法是从头扫描的，不是O(1)的，所以还是建议自己实现双向链表。
import java.util.HashMap; import java.util.LinkedList; public class LRUCache { private static class Node { int key; int val; public Node(int k, int v) { key = k; val = v; } @Override public String toString() { return "Node [key=" + key + ", val=" + val + "]"; } } int capacity; LinkedList<Node> list = new LinkedList<Node>(); HashMap<Integer, Node> map = new HashMap<Integer, Node>(); public LRUCache(int capacity) { this.capacity = capacity; } public int get(int key) { if (map.containsKey(key)) { Node cur = map.get(key); list.remove(cur); list.addFirst(cur); return cur.val; } else return -1; } public void set(int key, int val) { if (map.containsKey(key)) { Node cur = map.get(key); list.remove(cur); cur.val = val; list.addFirst(cur); } else { if (list.size() >= capacity) { Node last = list.getLast(); map.remove(last.key); list.removeLast(); } Node newNode = new Node(key, val); list.addFirst(newNode); map.put(key, newNode); } } public static void main(String[] args) { LRUCache cache = new LRUCache(3); cache.set(1, 11); cache.set(2, 22); cache.set(3, 33); cache.set(4, 44); System.out.println(cache.get(1)); System.out.println(cache.get(2)); System.out.println(cache.get(3)); System.out.println(cache.get(4)); } }
自己实现双向链表。
import java.util.HashMap; public class LRUCache { private int capacity; private int len; private HashMap<Integer, DoubleLinkedListNode> map = new HashMap<Integer, DoubleLinkedListNode>(); private DoubleLinkedListNode head; private DoubleLinkedListNode tail; public LRUCache(int capacity) { this.capacity = capacity; len = 0; } public int get(int key) { if (map.containsKey(key)) { DoubleLinkedListNode cur = map.get(key); removeNode(cur); setHead(cur); return cur.val; } else return -1; } public void set(int key, int value) { if (map.containsKey(key)) { DoubleLinkedListNode cur = map.get(key); cur.val = value; removeNode(cur); setHead(cur); } else { DoubleLinkedListNode newNode = new DoubleLinkedListNode(key, value); if (len < capacity) { setHead(newNode); map.put(key, newNode); len++; } else { map.remove(tail.key); tail = tail.pre; if (tail != null) tail.next = null; setHead(newNode); map.put(key, newNode); } } } private void removeNode(DoubleLinkedListNode cur) { if (cur == null) return; DoubleLinkedListNode pre = cur.pre; DoubleLinkedListNode next = cur.next; if (pre != null) { pre.next = cur.next; } else head = next; if (next != null) next.pre = cur.pre; else tail = pre; } private void setHead(DoubleLinkedListNode cur) { cur.next = head; cur.pre = null; if (head != null) head.pre = cur; head = cur; if (tail == null) tail = cur; } public static void main(String[] args) { LRUCache cache = new LRUCache(1); cache.set(1, 11); cache.set(1, 111); System.out.println(cache.get(1)); cache.set(2, 22); System.out.println(cache.get(1)); System.out.println(cache.get(2)); } private static class DoubleLinkedListNode { public int key; public int val; public DoubleLinkedListNode pre; public DoubleLinkedListNode next; public DoubleLinkedListNode(int key, int val) { this.key = key; this.val = val; } } }
第四遍重写：
要自己实现双向链表，因为LinkedList没有O(1)时间删除当前节点的方法，只能自己实现。
head和tail都是dummy的，记得要初始化，有了dummy节点，删除和头上增加节点就简洁多了。
注意capacity,len,head,tail几个变量运用。
注意增加和删除时，map和链表同步操作。
import java.util.HashMap; public class LRUCache { private int capacity; private HashMap<Integer, Node> map; private Node head = new Node(-1, -1); private Node tail = new Node(-1, -1); private int len; public LRUCache(int c) { capacity = c; map = new HashMap<Integer, Node>(); len = 0; head.next = tail; tail.pre = head; } private static class Node { int key; int val; Node pre; Node next; public Node(int k, int v) { key = k; val = v; } public String toString() { return "[" + key + "," + val + "]"; } } private void removeNode(Node cur) { Node pre = cur.pre; Node post = cur.next; pre.next = post; post.pre = pre; cur.pre = null; cur.next = null; len--; } private void addFirst(Node cur) { Node post = head.next; head.next = cur; post.pre = cur; cur.pre = head; cur.next = post; len++; } public int get(int key) { if (map.containsKey(key)) { Node cur = map.get(key); removeNode(cur); addFirst(cur); return cur.val; } else { return -1; } } public void set(int key, int val) { if (map.containsKey(key)) { Node cur = map.get(key); removeNode(cur); cur.val = val; addFirst(cur); } else { if (len >= capacity) { Node toDel = tail.pre; map.remove(toDel.key); removeNode(toDel); } Node newNode = new Node(key, val); map.put(key, newNode); addFirst(newNode); } } public static void main(String[] args) { LRUCache cache = new LRUCache(1); cache.set(1, 11); cache.set(1, 111); System.out.println(cache.get(1)); cache.set(2, 22); cache.set(3, 33); System.out.println(cache.get(2)); System.out.println(cache.get(1)); System.out.println(cache.get(3)); } }
参考：
http://www.programcreek.com/2013/03/leetcode-lru-cache-java/