LRUCache 全称为 Least Recently Used Cache ，用Java实现的话，可以很简单地用LinkedHashMap来实现。但如果面试过程中碰到面试官出这道题，大概率是希望你不借助过多的工具类，而是把一个LRUCache内部的get、put等方法给写一遍，以证实你是真的理解了。。
首先明确我们需要用到的数据结构：
1、hash表
为保证时间复杂度在O(1)，hash表是必不可少的，它的作用就是充当缓存的容器；
2、双向链表
双向链表的每个节点都具备指向前驱节点和指向后驱节点的两个指针，其双向查询的特点使得我们能够让一个（新/旧）节点以O(1)的时间复杂度快速入到链表的头部或尾部。而如果只是单向的链表，我们无法保证O(1)的时间复杂度的（比如删除队尾节点的操作，即使一开始定义了队尾节点，但是因为其单向的特点，删除时还是需要从头节点遍历到队尾的前一个节点，让其next指针指向空，才能将队尾删除）。
接下来一起看下代码中的逻辑：
- 构造器
1、我们将构造器传进来的capacity参数作为缓存允许的最大容量，同时初始化当前缓存的数量size为0；
2、定义头部节点head和尾部节点tail两个dummyNode，这是链表类题目的常用技巧，为的是避免处理头节点为空的边界问题，同时要初始化好head和tail节点互相指向的关联关系；
- get方法
根据key查询是否存在于缓存之中，不存在则直接返回null；如果存在，我们就要维护一下链表，将该节点移动到链表头部（同理，用尾部来作为最新节点的存放位置也是可以的），表示该节点最近被访问到了。
- put方法
判断该key是否存在于缓存之中
1、如果不存在
- 首先先新建一个节点放入hash表中，同时将这个节点添加到链表的头部，表示该节点最近被访问到了；
- 放入缓存后，我们要判断加上这个节点后，缓存的容量是否超过设定的最大容量，如果是，就要删掉链表中的尾部节点，并根据尾部节点的key，将其从hash表中remove掉
2、如果存在
- 移动该节点到链表头部，并更新节点中的value即可。
除此之外，对于链表节点的添加、移动、删除等操作，我们最好将方法单独抽离开来，这样做好处有两个：
一是可以对抽离开的方法进行复用；
二是在写get、put方法时，可以专注于缓存整体的维护逻辑，而不用关注到链表这一层数据结构，降低懵逼的风险。。
代码如下
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
Map<Integer, DLinkedNode> cache ;
int size;
int capacity;
DLinkedNode head, tail ;
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(3);
lruCache.put(1, 2);
lruCache.put(2, 2);
lruCache.put(3, 2);
lruCache.get(1);
lruCache.put(4, 2);
System.out.println(lruCache.cache.keySet());// [1, 3, 4]
}
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
cache = new HashMap<>();
// 维护两个dummy node（始终在头尾）
this.head = new DLinkedNode();
this.tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.v;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
node = new DLinkedNode(key, value);
cache.put(key, node);
// 移动到头部
addToHead(node);
if (++size > capacity) {
// 丢弃tail
DLinkedNode tail = removeTail();
cache.remove(tail.k);
--size;
}
} else {
// 替换并放到头部
node.v = value;
moveToHead(node);
}
}
/**
* 将节点移动到头部
*/
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
/**
* 删除节点
*/
private void removeNode(DLinkedNode node) {
node.next.prev = node.prev;
node.prev.next = node.next;
}
/**
* 添加到头部
*/
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
/**
* 删除尾部节点
*/
private DLinkedNode removeTail() {
DLinkedNode node = tail.prev;
removeNode(node);
return node;
}
/**
* 双向链表
*/
class DLinkedNode {
DLinkedNode prev;
DLinkedNode next;
// key作用体现在干掉tail的时候可以通过node的key去remove哈希表中的元素
int k;
int v;
public DLinkedNode() {
}
public DLinkedNode(int k, int v) {
this.k = k;
this.v = v;
}
}
}
网友评论