当前位置：首页 > news >正文

LRU缓存算法

news 来源：原创 2024/4/30 3:12:23

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

#include <iostream>
#include <unordered_map>
using namespace std;

struct ListedNode
{
	int key, value;
	ListedNode* last; // 前趋
	ListedNode* next;  //后继
	ListedNode() :key(0), value(0), last(nullptr), next(nullptr) {  }
	ListedNode(int k, int v) :key(k), value(v), last(nullptr), next(nullptr) { }
};

class LRUCache
{
private:
	unordered_map<int, ListedNode*> cache;
	ListedNode* head;  //头结点
	ListedNode* tail;  //尾节点
	int m_capacity;  // 缓存容量
	int m_size;
public:
	LRUCache(int _capacity) :m_capacity(_capacity), m_size(0)
	{   // 完成初始化
		head = new ListedNode();
		tail = new ListedNode();
		head->next = tail;
		tail->last = head;
	}
	int get(int key)
	{
		if (!cache.count(key)) // 如果不存在key
			return -1;
		// 如果key存在，则将其列为最近使用元素，移动到链表头部
		ListedNode* p = cache[key];
		moveTohead(p);
		return p->value;
	}

	void put(int key, int value)
	{
		if (!cache.count(key))  // 如果key不存在，创建一个新的结点
		{
			ListedNode* node = new ListedNode(key, value);
			// 添加进 哈希表
			cache[key] = node;
			// 更新位置到头部，标注最近使用
			addTohead(node);
			++m_size;
			if (m_size > m_capacity)
			{
				//如果超出容量，删除链表尾部结点
				ListedNode* removed = removeTail();
				//删除哈希表中对应项
				cache.erase(removed->key);
				//防止内存泄漏
				delete removed;
				--m_size;
			}

		}
		else
		{// 如果key存在，先通过哈希表定位，再修改value值，移动到头部
			ListedNode* node = cache[key];
			node->value = value;
			moveTohead(node);
		}
	}

	void addTohead(ListedNode* node)  // 插入节点
	{
		node->last = head;  // 插入结点前趋指向头结点
		node->next = head->next;  //  插入节点后继指向第一个结点
		head->next->last = node; // 头结点的后继指向插入节点
		head->next = node;  // （原）第一个结点的前趋指向插入结点，至此插入完成
	}

	void removeNode(ListedNode* node)  //删除结点
	{
		node->last->next = node->next;
		node->next->last = node->last;
	}

	ListedNode* removeTail()
	{
		ListedNode* p = tail->last;
		removeNode(p);
		return p;
	}

	void moveTohead(ListedNode* node)
	{
		removeNode(node);
		addTohead(node);
	}
};