赞
踩
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
1)LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
2)int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
3)void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
1.哈希表 + 双向链表
LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。
这样以来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下:
对于 get 操作,首先判断 key 是否存在:
如果 key 不存在,则返回 -1−1;
如果 key 存在,则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置,并将其移动到双向链表的头部,最后返回该节点的值。
对于 put 操作,首先判断 key 是否存在:
如果 key 不存在,使用 key 和 value 创建一个新的节点,在双向链表的头部添加该节点,并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项;
如果 key 存在,则与 get 操作类似,先通过哈希表定位,再将对应的节点的值更新为 value,并将该节点移到双向链表的头部。
上述各项操作中,访问哈希表的时间复杂度为 O(1),在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部,可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作,都可以在 O(1) 时间内完成。
1.LRU
这个算法是在学习操作系统的时候学的。
LRU-least recently used-最近最少使用算法,是一种内存数据淘汰策略,使用常见是当内存不足时,需要淘汰最近最少使用的数据。LRU常用语缓存系统的淘汰策略。
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。
1.方法1Java
public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) {key = _key; value = _value;} } private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } // 如果 key 存在,先通过哈希表定位,再移到头部 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { // 如果 key 不存在,创建一个新的节点 DLinkedNode newNode = new DLinkedNode(key, value); // 添加进哈希表 cache.put(key, newNode); // 添加至双向链表的头部 addToHead(newNode); ++size; if (size > capacity) { // 如果超出容量,删除双向链表的尾部节点 DLinkedNode tail = removeTail(); // 删除哈希表中对应的项 cache.remove(tail.key); --size; } } else { // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部 node.value = value; moveToHead(node); } } private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res; } }
2.方法1C++
struct DLinkedNode { int key, value; DLinkedNode* prev; DLinkedNode* next; DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {} }; class LRUCache { private: unordered_map<int, DLinkedNode*> cache; DLinkedNode* head; DLinkedNode* tail; int size; int capacity; public: LRUCache(int _capacity): capacity(_capacity), size(0) { // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head->next = tail; tail->prev = head; } int get(int key) { if (!cache.count(key)) { return -1; } // 如果 key 存在,先通过哈希表定位,再移到头部 DLinkedNode* node = cache[key]; moveToHead(node); return node->value; } void put(int key, int value) { if (!cache.count(key)) { // 如果 key 不存在,创建一个新的节点 DLinkedNode* node = new DLinkedNode(key, value); // 添加进哈希表 cache[key] = node; // 添加至双向链表的头部 addToHead(node); ++size; if (size > capacity) { // 如果超出容量,删除双向链表的尾部节点 DLinkedNode* removed = removeTail(); // 删除哈希表中对应的项 cache.erase(removed->key); // 防止内存泄漏 delete removed; --size; } } else { // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部 DLinkedNode* node = cache[key]; node->value = value; moveToHead(node); } } void addToHead(DLinkedNode* node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } void removeNode(DLinkedNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } void moveToHead(DLinkedNode* node) { removeNode(node); addToHead(node); } DLinkedNode* removeTail() { DLinkedNode* node = tail->prev; removeNode(node); return node; } };
1.方法1
时间复杂度:对于 put 和 get 都是 O(1)。
空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity+1 个元素。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。