首页 > ACM题库 > LeetCode > LeetCode-LRU Cache[链表]
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.

标签: Data Structure
分析

为了使查找、插入和删除都有较高的性能,我们使用一个双向链表({std::list})和一个哈希表({std::unordered_map}),因为:
\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;
public class LRUCache extends LinkedHashMap<Integer,Integer>{
    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作为参数。