LeetCode:LRU Cache

57 阅读 0 评论 38 点赞

我是靠谱客的博主谨慎树叶，最近开发中收集的这篇文章主要介绍LeetCode:LRU Cache，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这题我个人感觉非常经典，虽然我们再操作系统上学过FIFO，random，LRU等好几种替换算法，但是实际上我们只是知道它的原理，却不知道怎么实现。我以前一直以为这种Cache是很难实现的一个东西，没想到看了两三个小时就可以做出来了，其实过程还是很简单的，一步一步来就好了。

先说LRU的原理，LRU是Least Recently Used 近期最少使用算法。

内存管理的一种页面置换算法，对于在内存中但又不用的数据块（内存块）叫做LRU，Oracle会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。
什么是LRU算法？ LRU是Least Recently Used的缩写，即最少使用页面置换算法，是为虚拟页式存储管理服务的。如果cache不满，新来的放第一个，如果满了，在cache里面就把里面那个放到第一个，如果不在就删除最后一个，然后把新元素放第一个。

      例子：

物理块有3个则

假设序列为 4 3 4 2 3 1 4 2

首轮 4调入内存 4

次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
之后 4调入内存 4 1 3（原理同上）

最后 2调入内存 2 4 1

然后再说我的思路，因为你要保存key-value的值，且需要一个前后的排序，必然是双链表无疑了，但是双链表结构查找是在太麻烦了所以加上一个hashmap。

以前我一直搞不懂hashmap跟map优势劣势在哪里，今天下午查了一下终于搞清楚了。就是我们以前学过的数据结构，map是以一个红黑树的数据结构存储，查找时是相当于二分查找不断比较，所以时间复杂度是O（logN）。但是hashmap用哈希散列存储，通过hash函数直接根据key就可以找到value，只要O（1），更详细的可以看这篇博客hash_map与map区别。

struct Node{    //双向链表存储cache信息 
	Node* pre;
	int key;
	int val;
	Node* next;
	Node(int x,int y):key(x),val(y),pre(NULL),next(NULL){
	}
};


class LRUCache{
	unordered_map<int,Node*> mp;	//设置map是为了方便查找节点，不用遍历链表 
	Node* head;
	Node* tail;
	int cap;
	int size;
	
public:
    LRUCache(int capacity) { //给cache赋值时的初始化 
        if(capacity<=0)return;
        head=new Node(0,0);
        tail=new Node(0,0);
        head->next=tail;
        tail->pre=head;
        mp.clear();
        size=0;
        cap=capacity;
    }
    
    int get(int key) {
    	if(cap<1)return -1;
        unordered_map<int,Node*>::iterator it=mp.find(key);
        if(it==mp.end())return -1;//没找到 
        else{
        	cutNode(it->second);  //将节点抽出 
        	pushToHead(it->second);//讲节点压到链表表头 
        	return it->second->val;
        }
    }
    
    void set(int key, int value) {
        if(cap<1)return;
        unordered_map<int,Node*>::iterator it=mp.find(key);
        if(it==mp.end()){//没找到 
        	Node* tmp=new Node(key,value);
        	pushToHead(tmp);//讲新的节点压到首部 
        	size++;
        	mp[key]=tmp;//在mp里赋值，方便查找节点 
			if(size>cap){//如果空间不够 
				popNode();//删除最后的节点 
			}
        }
        else{
          it->second->val=value;	//如果在map里找到节点，赋值后，做抽出节点在压到表头就好 
          cutNode(it->second);
          pushToHead(it->second);	
        }
        
    }
    void cutNode(Node* p){//从链表中抽出节点(不是删除，是为了方便在插入节点) 
    	p->pre->next=p->next;
    	p->next->pre=p->pre;
    }
    void pushToHead(Node *p){//压到表头 
    	head->next->pre=p;
    	p->next=head->next;
    	head->next=p;
    	p->pre=head;
    }
    
    void popNode(){//删除链表末端节点 
    	Node* p=tail->pre;
    	p->pre->next=tail;
		tail->pre= p->pre;
		unordered_map<int,Node*>::iterator it=mp.find(p->key);
		mp.erase(it);
		delete p;
		size--;
    }  
};