题目大意:设计一个数据结构实现LRU(Least Recently Used)缓存机制,必须实现以下两个操作:get和set
get(key) -- 如果key存在,返回key所对应的value(为正数);否则返回-1;
set(key, value) -- key不存在时,设置或插入这个(key, value)对,当cache的容量已满时,插入前应该移除least recently used元素。
理解:1)题目要求设计并实现一个cache,使用LRU调度机制来进行存储管理。LRU调度是指当存储满时,选择最近最少使用的元素移除缓存,我们知道LRU调度最新调用或使用的对象都会放在第一个,随着时间的推移,当存储满时,排在最后个那个元素就是最长时间没有被再次使用的,就是该被移除的那个。
2)设计的数据结构要满足插入、删除和移动很容易,所有很容易想到用链表,为满足插入首节点和删除最后一个元素很简单,我们同时为链表增加首节点(head)和尾节点(tail),并使用双向链表。只需要实现对链表的三种操作:插入首节点,移除尾节点和将某个给定节点移到首位(表示最新使用)。
实现:
public class LRUCache { private int capacity; class node { // 节点类型 int key; int val; node next; node pre; private node(int key, int val) { this.key = key; this.val = val; this.next = null; this.pre = null; } } private class cacheList { // 内部类 实现对双向链表的插入、删除和移动的操作 private node head, tail; // 增加首尾节点,方便插入首节点和删除尾节点 private cacheList() { head = new node(0, 0); tail = new node(0, 0); head.next = tail; tail.pre = head; } private void insertFirst(node p) { // 插入到第一个节点位置 p.next = head.next; head.next.pre = p; p.pre = head; head.next = p; } private node removeLast() { // 删除最后一个节点,并返回被删除的节点 node last = tail.pre; last.next.pre = last.pre; last.pre.next = last.next; return last; } private void removeToFirst(node p) { // 将特定节点移动到第一个节点位置 p.pre.next = p.next; p.next.pre = p.pre; this.insertFirst(p); } } private cacheList cachelist; public HashMap<Integer, node> map; public LRUCache(int capacity) { this.capacity = capacity; cachelist = new cacheList(); map = new HashMap<Integer, node>(); } public int get(int key) { // 查找某个key对应的value,若不存在则返回-1 node res = map.get(key); if(res != null) { cachelist.removeToFirst(res); return res.val; } return -1; } public void set(int key, int value) { // 插入一(key, value)对 if(map.containsKey(key)) { // 若该key已存在,则更新其对应的value,并移动到第一个节点位置 node res = map.get(key); res.val = value; map.put(key, res); cachelist.removeToFirst(res); } else { // 不存在,则将(key, value)对插入到第一个节点位置 if(map.size() == capacity) { // 若cache容量已满,则移除LRU节点,即链表的最后一个节点 node last = cachelist.removeLast(); map.remove(last.key); } node q = new node(key, value); cachelist.insertFirst(q); map.put(key, q); } } }