【高阶数据结构】LRU Cache

什么是LRU Cache

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法

什么是Cache

狭义的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术,广义上的Cache指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache， 内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等

---

Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉

其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容

---

LRU Cache的实现

实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)的put和get，那么使用双向链表和哈希表的搭配是最高效和经典的

使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表的增删查改也是O(1)

---

LRU缓存OJ：

https://leetcode.cn/problems/lru-cache/

---

结构设计分析

实现结构1:

private:
	unordered_map<int,int> _hashMap; //hash能做到查找get更新是O(1)
	
	list<pair<int,int>> _LRUList;//假设尾部数据就是最近少用的,最近使用的放在头部
	size_t _capacity;//标记容量,满了就弹出链表尾的元素+在哈希表删除该元素的键值对
1
2
3
4
5

此时:

int get(int key) {}
void put(int key, int value) {}
1
2

get: 直接查map,时间复杂度是O(1)

put: 如果是新增元素就是O(1),直接插入, 但是如果是修改更新: 就是O(N), 因为要在map查找完成后,在_LRUList中找到该元素key所在位置 ,只能遍历查找,时间复杂度是O(N) ,然后把该元素key放在头部O(1)

---

破局点:找到key之后,就要找到key对应存储的数据在链表中的位置

所以: hashMap中可以存list的迭代器！ 我们实现过list,所以知道list的迭代器本质是节点的指针

typedef list<pair<int,int>>::iterator LtIter;
private:
	unordered_map<int,LtIter> _hashMap; //key:值  Value:list的迭代器,即key对应在list的位置
	list<pair<int,int>> _LRUList;
	size_t _capacity;//标记容量,满了就弹出链表尾的元素+在哈希表删除该元素的键值对
1
2
3
4
5

这个结构,相当于真正的数据在list里面！在map中查找key,就可以直接在链表中找到这个节点, 然后把这个节点转移到链表头部

---

list的splice函数介绍:

splice函数用于两个list容器之间的拼接(数据转移)，其有三种拼接方式：

1. 将整个容器拼接到另一个容器的指定迭代器位置。
2. 将容器当中的某一个数据拼接到另一个容器的指定迭代器位置。
3. 将容器指定迭代器区间的数据拼接到另一个容器的指定迭代器位置。

#include 
#include 
using namespace std;

int main()
{
	list<int> lt1(4, 2);
	list<int> lt2(4, 6);
	lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2 

	list<int> lt3(4, 2);
	list<int> lt4(4, 6);
	lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl; //6 2 2 2 2 

	list<int> lt5(4, 2);
	list<int> lt6(4, 6);
	lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头
	for (auto e : lt5)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

注意： 容器当中被拼接到另一个容器的数据在原容器当中就不存在了。（实际上就是将链表当中的指定结点拼接到了另一个容器当中）

当然也可以把节点转移到自己身上

例如:

#include
int main()
{
	list<int> lt{ 1,2,3,4,5 };
	lt.splice(lt.begin(), lt, --lt.end());//把尾部的数据放到头部
	for (auto e : lt)
	{
		cout << e << " "; // 5 1 2  3  4
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

---

我们待会要用这个函数来把节点转移到链表的头部!

get函数的实现:

1)在map中查找key是否存在 .如果不存在,返回-1

2)如果存在,把该key放到list的头部 -> 转移节点 ,然后返回key对应的值

元素存在list里面, _hashMap中的键:key 值:list的迭代器(LtIter),

---

如果key对应的值存在,则取出迭代器, 这里就可以看出hashmap的value存的是list的iterator的好处：找到key 也就找到key存的值在list中的iterator，也就直接删除，再进行头插，实现O(1)的数据挪动

int get(int key) 
{
    //_hashMap中的key:key value：list的迭代器(LtIter)

    auto ret = _hashMap.find(key);//先查找是否在哈希表中
    if(ret != _hashMap.end())
    {
        //更新当前元素到链表头部
        LtIter it= ret->second;//该元素在list中的位置
        _LRUList.splice(_LRUList.begin(),_LRUList,it);//把元素转移到链表头部,相当于头插,但是这这里不用更新迭代器,因为迭代器里面存的还是这个节点的指针
        
        //it:是链表的迭代器,调用operator->,返回数据的地址,list中的数据是pair,所以返回的是pair*
        //pair  我们要的是第二个成员的值  
        //本来应该是it->->second 但是省略了一个箭头 
        return it->second;//返回key对应的value 
    }
    else    //该元素不存在
    {
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

put函数的实现:

1)在map中查找key是否存在 .如果不存在,那就要新增

• 1.判断是否满了,如果满了,需要先删除list中尾部的数据. 然后在哈希表中也要删除该元素

  2.然后把该该 {key-value}头插到链表中 , 在哈希表中新增键值对{key-该位置在链表的迭代器}

注意点:判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)

2)如果已经存在了,那就修改数据, 然后把该key放到list的头部

void put(int key, int value)
{
    auto ret = _hashMap.find(key);
    //新增
    if(ret == _hashMap.end())
    {
        //判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)
        //if(_capacity == _LRUList.size()) 不建议
        if(_capacity == _hashMap.size()) //容量满了
        {
            pair<int,int> back = _LRUList.back();//取出链表尾部的数据
            //在哈希表中删除该数据 + 在链表弹出该元素
            _hashMap.erase(back.first);//back.first是key
            _LRUList.pop_back();
        }

        //头插入当前元素 + 哈希表新增键值对{key-该元素在list的位置(链表头部)}
        _LRUList.push_front(make_pair(key,value));
        _hashMap[key] = _LRUList.begin();
    }
    else
    {
        //修改节点的值 + 当前数据放到链表头部
        LtIter it = ret->second;//it是list的迭代器
        it->second = value;//更新节点的值
        _LRUList.splice(_LRUList.begin(),_LRUList,it);//把当前节点转移到头部
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

整体代码:

class LRUCache {
public:
    typedef list<pair<int,int>>::iterator LtIter; //list的迭代器重命名为LtIter
    LRUCache(int capacity) {
        _capacity = capacity;
    }
    
    int get(int key) {
        //_hashMap中的key:key value：list的迭代器(LtIter)
        auto ret = _hashMap.find(key);//先查找是否在哈希表中
        if(ret != _hashMap.end())
        {
            //更新当前元素到链表头部
            LtIter it= ret->second;//该元素在list中的位置
            _LRUList.splice(_LRUList.begin(),_LRUList,it);//把元素转移到链表头部
            
            //it:是链表的迭代器,it-> 调用operator->,返回数据的地址,list中的数据是pair,所以返回的是pair*
            //pair  我们要的是第二个成员的值  
            //本来应该是it->->second 但是省略了一个箭头 
            return it->second;//返回key对应的value 
        }
        else    //该元素不存在
        {
            return -1;
        }
    }
    
    void put(int key, int value)
    {
        auto ret = _hashMap.find(key);
        //新增
        if(ret == _hashMap.end())
        {
            //判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)
            //if(_capacity == _LRUList.size()) 不建议
            if(_capacity == _hashMap.size()) //容量满了
            {
                pair<int,int> back = _LRUList.back();//取出链表尾部的数据
                //在哈希表中删除该数据 + 在链表弹出该元素
                _hashMap.erase(back.first);//back.first是key
                _LRUList.pop_back();
            }

            //头插入当前元素 + 哈希表新增键值对{key-该元素在list的位置(链表头部)}
            _LRUList.push_front(make_pair(key,value));
            _hashMap[key] = _LRUList.begin();
        }
        else
        {
            //修改节点的值 + 当前数据放到链表头部
            LtIter it = ret->second;//it是list的迭代器
            it->second = value;//更新节点的值
            _LRUList.splice(_LRUList.begin(),_LRUList,it);//把当前节点转移到头部
        }
    }

private:
	unordered_map<int,LtIter> _hashMap; //key:值  Value:list的迭代器,即key对应在list的位置
	list<pair<int,int>> _LRUList;
    size_t _capacity;//标记容量,满了就弹出链表尾的元素+在哈希表删除该元素的键值对
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

---

其实这里有两种更新常用元素的方式:

1.用内置的splice函数转移节点

2.先保存节点信息,然后erase节点,然后push_front. 然后更新key对应的迭代器, 因为原迭代器指向我们删除的数据,迭代器失效了!!

使用unordered_map，让搜索效率达到O(1)
需要注意：这里最巧的设计就是将unordered_map的value type放成list>::iterator，因为这样，当get一个已有的值以后，就可以直接找到key在list中对应的iterator，然后将这个值移动到链表的头部保持LRU

int get(int key) 
{
    // 如果key对应的值存在，就可以取出元素位置迭代器,这里就可以看出hashmap的value存的是list的 terator的好处：找到key
        // 也就找到key存的值在list中的iterator，也就直接删除，再进行头插，实现O(1)的数据挪动
     auto hashit = _hashmap.find(key);
    if(hashit != _hashmap.end())
    {
        auto listit = hashit->second;//list的迭代器
        pair<int, int> kv = *listit; //调用operator* 返回节点数据的内容,list的数据是pair

        _list.erase(listit);//通过迭代器删除该节点
        _list.push_front(kv);//然后头插
        _hashmap[key] = _list.begin();//更新迭代器的位置
        return kv.second;//返回key对应的value
    }
    else
    {
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

void put(int key, int value) 
{
    // 1.如果没有数据则进行插入数据
    // 2.如果有数据则进行数据更新
    auto hashit = _hashmap.find(key);
    if(hashit == _hashmap.end())
    {
        // 插入数据时，如果数据已经达到上限，则删除链表头的数据和hashmap中的数据，两个删除操作都是O(1)
            if(_list.size() >= _capacity)
            {
                _hashmap.erase(_list.back().first); //在哈希表中删除最后一个节点的信息,通过key删除. _list.back().first:最后一个节点的第一个成员就是key
                _list.pop_back();//尾删最后一个节点
            }

        _list.push_front(make_pair(key,value));//头插
        _hashmap[key] = _list.begin();//新建键值对
    }
    else
    {
        // 更新数据  将数据挪动list前面
        auto listit = hashit->second;//list的迭代器
        pair<int, int> kv = *listit;//调用operator* 返回节点数据的内容,list的数据是pair,先保留数据
        kv.second = value;//更新值

        _list.erase(listit);//通过迭代器删除该节点
        _list.push_front(kv);//头插
        _hashmap[key] = _list.begin();//更新迭代器的位置
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29