设计并实现一个LRU Cache_

陈木木

下面是一个参考思路
• 重要数据结构：key-value存储、LRU存储；
• key-value存储：hash_table/map，LRU：链表，因为可以快速实现增加、删除
• 如何更新Cache: 找到key在链表中的位置，删除并将它插到表头，同时更新key到链表位置的映射
• 快速找到最不常访问的元素：链表尾

发表于 2015-05-05 14:50:46 回复(0)

包子·陳V

解题思路：题目让设计一个LRU Cache，即根据LRU算法设计一个缓存。在这之前需要弄清楚LRU算法的核心思想，LRU全称是Least

Recently Used，即最近最久未使用的意思。在操作系统的内存管理中，有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来更新和访问其中的元素。下面说一下LRU算法的核心思想，LRU算法的设计原则是： 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小 。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

而用什么数据结构来实现LRU算法呢？可能大多数人都会想到：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。

这种实现思路很简单，但是有什么缺陷呢？需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。

那么有没有更好的实现办法呢？

那就是利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

总结一下：根据题目的要求，LRU Cache具备的操作：

1）set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。

2）get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。


	
	
		#include <iostream>
	

	
		#include <map>
	

	
		#include <algorithm>
	

	
		#include <list>
	

	
		usingnamespacestd;
	

	
		 
	

	
		structNode
	

	
		{
	

	
		    intkey;
	

	
		    intvalue;
	

	
		};
	

	
		 
	

	
		 
	

	
		classLRUCache{
	

	
		private:
	

	
		    intmaxSize ;
	

	
		    list<Node> ***List;
	

	
		    map<int, list<Node>::iterator > mp;
	

	
		public:
	

	
		    LRUCache(intcapacity) {
	

	
		      maxSize = capacity;
	

	
		    }
	

	
		     
	

	
		    intget(intkey) {
	

	
		        map<int, list<Node>::iterator >::iterator it = mp.find(key);
	

	
		        if(it==mp.end())     //没有命中
	

	
		        {
	

	
		            return-1;
	

	
		        }
	

	
		        else //在***中命中了
	

	
		        {
	

	
		            list<Node>::iterator listIt = mp[key];
	

	
		            Node newNode;
	

	
		            newNode.key = key;
	

	
		            newNode.value = listIt->value;
	

	
		            ***List.erase(listIt);              //先删除命中的节点      
	

	
		            ***List.push_front(newNode);  //将命中的节点放到链表头部
	

	
		            mp[key] = ***List.begin();
	

	
		        }
	

	
		        return***List.begin()->value;
	

	
		    }
	

	
		     
	

	
		    voidset(intkey,intvalue) {
	

	
		        map<int, list<Node>::iterator >::iterator it = mp.find(key);
	

	
		        if(it==mp.end())  //没有命中
	

	
		        {
	

	
		            if(***List.size()==maxSize) //***满了
	

	
		            {
	

	
		                mp.erase(***List.back().key);    
	

	
		                ***List.pop_back();
	

	
		            }
	

	
		            Node newNode;
	

	
		            newNode.key = key;
	

	
		            newNode.value = value;
	

	
		            ***List.push_front(newNode);
	

	
		            mp[key] = ***List.begin();
	

	
		        }
	

	
		        else //命中
	

	
		        {
	

	
		            list<Node>::iterator listIt = mp[key];
	

	
		            ***List.erase(listIt);              //先删除命中的节点          
	

	
		            Node newNode;
	

	
		            newNode.key = key;
	

	
		            newNode.value = value;
	

	
		            ***List.push_front(newNode);  //将命中的节点放到链表头部
	

	
		            mp[key] = ***List.begin();
	

	
		        }
	

	
		    }
	

	
		};
	

	
		 
	

	
		 
	

	
		intmain(void)
	

	
		{
	

	
		    LRUCache ***(3);
	

	
		    ***.set(1,1);
	

	
		     
	

	
		    ***.set(2,2);
	

	
		     
	

	
		    ***.set(3,3);
	

	
		     
	

	
		    ***.set(4,4);
	

	
		     
	

	
		    cout<<***.get(4)<<endl;
	

	
		     
	

	
		    cout<<***.get(3)<<endl;
	

	
		    cout<<***.get(2)<<endl;
	

	
		    cout<<***.get(1)<<endl;
	

	
		     
	

	
		    ***.set(5,5);
	

	
		     
	

	
		    cout<<***.get(1)<<endl;
	

	
		    cout<<***.get(2)<<endl;
	

	
		    cout<<***.get(3)<<endl;
	

	
		    cout<<***.get(4)<<endl;
	

	
		    cout<<***.get(5)<<endl;
	

	
		     
	

	
		    return0;
	

	
		}

编辑于 2016-09-05 10:12:02 回复(1)

M00N

package other;

import java.util.HashMap;
import java.util.LinkedList;
/**
LRU Cache
题目描述：
Design and implement a data structure for Least Recently Used (LRU) ***. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the ***, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the *** reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?

思路：
双向链表和hashmap。
1.当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，
如果不存在，则新建一个节点，放到链表头部
若缓存满了，则把链表最后一个节点删除即可。
2.在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。
这样一来在链表尾部的节点就是最近最久未访问的数据项。

*/
//leetcode pass
public class LRUCache {

	private int capacity;
	private LinkedList<Integer> list;
	private HashMap<Integer, Integer> map;
	
    public LRUCache(int capacity) {
        this.capacity = capacity;
        list = new LinkedList<>();
        map = new HashMap<>();
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
        	list.removeFirstOccurrence(key);
        	list.addFirst(key);
        	return map.get(key);
        } else {
        	return -1;
        }
    }
    
    public void put(int key, int value) {
        if (!map.containsKey(key)) {
        	if (list.size() == capacity) {
        		int last = list.removeLast();
        		map.remove(last);
        	}
        	list.addFirst(key);
    		map.put(key, value);
        } else {
        	list.removeFirstOccurrence(key);
        	list.addFirst(key);
    		map.put(key, value);
        }
    }
}

发表于 2017-04-06 22:12:25 回复(1)

流夜


	importjava.util.HashMap;



	importjava.util.LinkedList;



	/**



	LRU Cache



	题目描述：



	Design and implement a data structure for Least Recently Used (LRU) ***. It should support the following operations: get and put.



	 



	get(key) - Get the value (will always be positive) of the key if the key exists in the ***, otherwise return -1.



	put(key, value) - Set or insert the value if the key is not already present. When the *** reached its capacity, it should invalidate the least recently used item before inserting a new item.



	Follow up:



	Could you do both operations in O(1) time complexity?



	 



	思路：



	双向链表和hashmap。



	1.当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，



	如果不存在，则新建一个节点，放到链表头部



	若缓存满了，则把链表最后一个节点删除即可。



	2.在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。



	这样一来在链表尾部的节点就是最近最久未访问的数据项。



	 



	*/



	//leetcode pass



	publicclassLRUCache {



	 



	    privateintcapacity;



	    privateLinkedList<Integer> list;



	    privateHashMap<Integer, Integer> map;



	     



	    publicLRUCache(intcapacity) {



	        this.capacity = capacity;



	        list = newLinkedList<>();



	        map = newHashMap<>();



	    }



	     



	    publicintget(intkey) {



	        if(map.containsKey(key)) {



	            list.removeFirstOccurrence(key);



	            list.addFirst(key);



	            returnmap.get(key);



	        } else{



	            return-1;



	        }



	    }



	     



	    publicvoidput(intkey, intvalue) {



	        if(!map.containsKey(key)) {



	            if(list.size() == capacity) {



	                intlast = list.removeLast();



	                map.remove(last);



	            }



	            list.addFirst(key);



	            map.put(key, value);



	        } else{



	            list.removeFirstOccurrence(key);



	            list.addFirst(key);



	            map.put(key, value);



	        }



	    }



	}

发表于 2018-09-04 20:50:53 回复(1)

晚安丶胖不啦叽

双端队列+hashmap

发表于 2017-08-21 22:01:39 回复(1)

dark_flash

没有这么麻烦吧，只要维护一个队列，每次读取一个新的页面时候，弹出队列的首部选取不就行了

发表于 2016-08-07 17:03:08 回复(1)

设计并实现一个LRU Cache

问题信息

热门推荐

相关试题