2014
11-18

# LeetCode-LRU Cache[链表]

### LRU Cache

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.

\begin{itemize}
\item{哈希表保存每个节点的地址，可以基本保证在$O(1)$时间内查找节点}
\item{双向链表插入和删除效率高，单向链表插入和删除时，还要查找节点的前驱节点}
\end{itemize}

\begin{itemize}
\item{越靠近链表头部，表示节点上次访问距离现在时间最短，尾部的节点表示最近访问最少}
\item{访问节点时，如果节点存在，把该节点交换到链表头部，同时更新hash表中该节点的地址}
\item{插入节点时，如果cache的size达到了上限capacity，则删除尾部节点，同时要在hash表中删除对应的项；新节点插入链表头部}
\end{itemize}

Java代码:

import java.util.LinkedHashMap;
private int capacity;
public LRUCache(int capacity) {
super(16, 0.75f, true);
this.capacity = capacity;
}
public Integer get(Object key) {
Integer v = super.get(key);
if(v != null) return v;
else return -1;
}
public boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
return size()>capacity;
}
public void set(int key, int value) {
super.put(key, value);
}
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

3. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。