# LeetCode：146_LRU cache | LRU缓存设计 | Hard

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.

LRU是一种应用在操作系统上的缓存替换策略，和我们常见的FIFO算法一样，都是用于操作系统中内存管理中的页面替换，其全称叫做Least Recently Used（近期最少使用算法），算法主要是根据数据的历史访问记录来进行数据的淘汰，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

LRU算法设计

4，7，0，7，1，0，1，2，1，2，6

/************************************************************************/
/* 单链表版本
/************************************************************************/
struct Node {
int        m_nKey;
int        m_nValue;
Node*    m_pNext;
};

class LRUCache {
public:
LRUCache(int capacity) {
m_nSize        = capacity;
m_nCount    = 0;
m_lruList    = NULL;
}

int get(int key) {
if (NULL == m_lruList)
return -1;
map<int, Node *>::iterator it = m_lruMap.find(key);
if (it == m_lruMap.end()) //没有找到
return -1;
else {
Node *p = it->second;
//把节点移到链表的开头
pushFront(p);
}
return m_lruList->m_nValue;
}

void set(int key, int value) {
if (NULL == m_lruList) {
m_lruList = new Node();
m_lruList->m_nKey = key;
m_lruList->m_nValue = value;
m_lruList->m_pNext = NULL;
m_nCount ++;
m_lruMap[key] = m_lruList;
}
else {
map<int, Node *>::iterator it = m_lruMap.find(key);
if (it == m_lruMap.end()){ //没有命中,将链表的最后一个节点删除
if (m_nSize == m_nCount) { //cache已满
}
m_nCount --;
else
pTemp->m_pNext = NULL;
}
Node *p = new Node(); //插入新的节点于头部
p->m_nKey = key;
p->m_nValue = value;
p->m_pNext = m_lruList;
m_lruList = p;
m_lruMap[key] = m_lruList;
m_nCount ++;
}
else { //命中，则将该命中的节点移至链表头部
Node *pCur = it->second;
pCur->m_nValue = value;
pushFront(pCur);
}
}
}

void pushFront(Node *pCur) {  //把节点移动到链表头部，时间复杂度O(n)
if (NULL == pCur)
return;
if (m_nCount == 1 || pCur == m_lruList)
return;
pCur->m_pNext = m_lruList;
m_lruList = pCur;
}

void printCache() {
Node *p = m_lruList;
while (p) {
cout << p->m_nKey << ":" << p->m_nValue << " ";
p = p->m_pNext;
}
}

private:
int                    m_nSize;
int                    m_nCount;
map<int, Node *>    m_lruMap;
Node*                m_lruList;
};

1 /************************************************************************/
2 /* 双链表版本
3 /************************************************************************/
4 struct Node {
5     int        m_nKey;
6     int        m_nValue;
7     Node*    m_pNext;
8     Node*   m_pPre;
9 };
10
11 class LRUCache {
12 public:
13     LRUCache(int capacity) {
14         m_nSize            = capacity;
15         m_nCount        = 0;
17         m_lruListTail    = NULL;
18     }
19
20     int get(int key) {
22             return -1;
23         map<int, Node *>::iterator it = m_lruMap.find(key);
24         if (it == m_lruMap.end()) //没有找到
25             return -1;
26         else {
27             Node *p = it->second;
28             //把节点移到链表的开头
29             pushFront(p);
30         }
32     }
33
34     void set(int key, int value) {
35         if (NULL == m_lruListHead) {
42             m_nCount ++;
44         }
45         else {
46             map<int, Node *>::iterator it = m_lruMap.find(key);
47             if (it == m_lruMap.end()){ //没有命中,将链表的最后一个节点删除
48                 if (m_nSize == m_nCount) { //cache已满
49                     if (m_lruListHead == m_lruListTail) {//只有一个节点
54                     }
55                     else {
56                         Node *p = m_lruListTail;
57                         m_lruListTail->m_pPre->m_pNext = NULL;
58                         m_lruListTail = m_lruListTail->m_pPre;
59                         m_lruMap.erase(p->m_nKey);
60
61                         p->m_nKey = key;
62                         p->m_nValue = value;
64                         p->m_pPre = NULL;
68                     }
69                 }
70                 else {
71                     Node *p = new Node(); //插入新的节点于头部
72                     p->m_nKey = key;
73                     p->m_nValue = value;
75                     p->m_pPre = NULL;
79                     m_nCount ++;
80                 }
81             }
82             else { //命中，则将该命中的节点移至链表头部
83                 Node *pCur = it->second;
84                 pCur->m_nValue = value;
85                 pushFront(pCur);
86             }
87         }
88     }
89
90     void pushFront(Node *pCur) {  //把节点移动到链表头部，时间复杂度O(1)
91         if (NULL == pCur)
92             return;
93         if (m_nCount == 1 || pCur == m_lruListHead)
94             return;
95         if (pCur == m_lruListTail) { //假如是尾节点
96             pCur->m_pPre->m_pNext = NULL;
98             m_lruListTail = pCur->m_pPre;
101         }
102         else {
103             pCur->m_pPre->m_pNext = pCur->m_pNext;
104             pCur->m_pNext->m_pPre = pCur->m_pPre;
105
109         }
110     }
111
112     void printCache() {
114         while (p) {
115             cout << p->m_nKey << ":" << p->m_nValue << " ";
116             p = p->m_pNext;
117         }
118     }
119
120 private:
121     int                    m_nSize;
122     int                    m_nCount;
123     map<int, Node *>    m_lruMap;
125     Node*                m_lruListTail;
126 };

#include <iostream>
#include <hash_map>
#include <list>
#include <utility>
using namespace std;
using namespace stdext;

class LRUCache{
public:
LRUCache(int capacity) {
m_capacity = capacity ;
}
int get(int key) {
int retValue = -1 ;
hash_map<int, list<pair<int, int> > :: iterator> ::iterator it = cachesMap.find(key) ;
//如果在Cashe中，将记录移动到链表的最前端
if (it != cachesMap.end())
{
retValue = it ->second->second ;
//移动到最前端
list<pair<int, int> > :: iterator ptrPair = it -> second ;
pair<int, int> tmpPair = *ptrPair ;
caches.erase(ptrPair) ;
caches.push_front(tmpPair) ;
//修改map中的值
cachesMap[key] = caches.begin() ;
}
return retValue ;
}
void set(int key, int value) {
hash_map<int, list<pair<int, int> > :: iterator> ::iterator it = cachesMap.find(key) ;
if (it != cachesMap.end()) //已经存在其中
{
list<pair<int, int> > :: iterator ptrPait = it ->second ;
ptrPait->second = value ;
//移动到最前面
pair<int , int > tmpPair = *ptrPait ;
caches.erase(ptrPait) ;
caches.push_front(tmpPair) ;
//更新map
cachesMap[key] = caches.begin() ;
}
else //不存在其中
{
pair<int , int > tmpPair = make_pair(key, value) ;

if (m_capacity == caches.size()) //已经满
{
int delKey = caches.back().first ;
caches.pop_back() ; //删除最后一个

//删除在map中的相应项
hash_map<int, list<pair<int, int> > :: iterator> ::iterator delIt = cachesMap.find(delKey) ;
cachesMap.erase(delIt) ;
}

caches.push_front(tmpPair) ;
cachesMap[key] = caches.begin() ; //更新map
}
}

private:
int m_capacity ;                                               //cashe的大小
list<pair<int, int> > caches ;                                 //用一个双链表存储cashe的内容
hash_map< int, list<pair<int, int> > :: iterator> cachesMap ;  //使用map加快查找的速度
};

0 条评论

## 相关文章

1622

2135

2935

### 百度面试总结

http://blog.csdn.net/zhaojinjia/article/details/12649823

3102

2832

3.1K6

### 4.1、苏宁百万级商品爬取 代码讲解 索引建立

Lucene是一款高性能的、可扩展的信息检索（IR）工具库。信息检索是指文档搜索、文档内信息搜索或者文档相关的元数据搜索等操作。

1503

### flying-saucer + iText + Freemarker实现pdf的导出， 支持中文、css以及图片

项目中有个需求，需要将合同内容导出成pdf。上网查阅到了 iText ， iText 是一个生成PDF文档的开源Java库，能够动态的从XML或者数...

3881

9753

3074