LRU淘汰缓存机制（LRU页面置换算法）HashMap+双向链表 C++实现

1、刚写入的元素，是最有可能被马上读出的，拿注册举例来说，有一个网站，注册完，紧接着下一步的动作就应该是登录，注册是一个写入的行为，登录是从数据库读取校验的过程，立刻写入，立刻读出的过程，LRU就是基于这样的思想，刚写入的数据是有一个热度的概念，热度是最高的，热度低的数据就是很久没有被访问过，如果数据刚被写入，或者刚被访问过，那么这个数据的热度就很高。
我们将真实数据的data结点放在双向链表中，设置虚结点head和tail不存元素，只是为了方便表达。

2、如何表达记录一个数据的热度？什么时候链表结点会被删除？
1）当data数据结点刚被访问过，它的热度是最高的，需要删除它在原本的位置，将此data结点移动到head的下一个结点。我们时刻维护head的next是热度最高的结点，那么当新的data数据来临的时候，我们也是需要将它插入到head后面的。
2）链表的长度已经到达规定容量capacity，那么需要淘汰热度最低的结点，也就是需要删除链表的tail结点前面的一个结点。我们时刻维护tail的前一个结点就是热度最低的结点。

3、我们会进行的操作，读取(不会触发淘汰机制)，新来结点（可能触发淘汰机制）
读取：从plist中获取data结点，将data从plist中删除，把data结点插入到plist的头部结点后面，返回plist中的data结点存储的value。
插入：如果链表长度没有超过容量，直接插入头部，链表长度超过容量，先删除尾部tail的前一个结点，然后将新的data结点插入到head结点的后面。

现在的问题就在于我们如何确认到我们需要的value在哪个data节点中。我们需要定位data结点。借助hashmap，hash的key就是data结点的key，对应的hash值就是data结点的地址。

4、时间复杂度计算
双向链表的插入和删除是在O（1）时间复杂度之内完成的，因为我们已经知道了插入和删除的具体位置。hashmap的查找时间复杂度也是O（1），所以整个算法的时间复杂度就是O(1)。

5、代码实现

class LRUCache{
public:
	struct Node{
	    int key,val;
		Node* pre;
		Node* next;

		Node (int k,int v){
			key = k;
			val = v;
			pre = next = nullptr;
		}
	};

	Node * head;
	Node * tail;
	int C;
	unordered_map<int,Node*>hashmap; //key data地址

	LRUCache(int Capacity){
		C = Capacity;
		head = new Node(-1,-1);
		tail = new Node(-1,-1);
		head->next = tail;   //空的LRU 头尾先连接起来
		tail->pre = head;
	}
	int get(int key){
		if(!hashmap.count(key)) return -1;
		Node* ptr = hashmap[key];
		remove(ptr);
		insert(ptr);
		return ptr->val;
	}
	void put(int key,int value){
		if(!hashmap.count(key)){
			//insert逻辑 增加结点
			if(hashmap.size() == C){
				//淘汰热度最低的结点
					Node* ptr = tail->pre;//尾巴的 pre不可能是 head 因为 Capacity至少是1，hashmap中至少存在一个真正的key。
			        remove(ptr);
                    hashmap.erase(ptr->key);
					delete ptr;		 
			}
			Node*ptr = new Node(key,value);
            hashmap[ptr->key] = ptr;
			insert(ptr);
			return;
		}

		//存在的话就是一个更新操作
		Node *ptr = hashmap[key];
		ptr->val = value;
		remove(ptr);
		insert(ptr);
	}

	void remove(Node*ptr){
		Node *a = ptr->pre;
		Node *b = ptr->next;

		a->next = b;
		b->pre = a;

		ptr->pre = ptr->next = nullptr;

	}
	void insert(Node*ptr){ //将一个结点插入到双向链表的头部（head-》next）
		Node* a = head->next;
		a->pre = ptr;
		ptr->next = a;

		ptr->pre = head;
		head->next = ptr;
	}
};
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
69
70
71
72
73
74
75