前几天在 LeetCode 上做题时做到了与 LRU 和 LFU 相关的题目，恰逢现在是暑期实习面试的高峰，LRU 也是面试中的常考内容，所以在此对 LRU 和 LFU 的 Java 实现做一个总结。
LRU 最近最久未使用
简单介绍一下 LRU，此处搬运自百度百科：
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
顾名思义，LRU 是一种淘汰算法，具体的淘汰策略是把最近最久未使用（或者说是最近最少使用）的页面淘汰掉，LRU 算法在操作系统的内存置换，Redis 缓存的数据淘汰策略中都有所涉及。百度百科中的介绍提到了根据 t 值进行淘汰，但是在实际应用中保存 t 值并不是一件容易的事，所以我们需要借助特别的数据结构来实现 LRU 算法。
具体来说，使用一个 HashMap 和一个自定义的双向链表：链表节点存储key，value，前向指针和后向指针；HashMap 中存储 key 和对应的链表节点；双向链表代表使用顺序，越靠近头节点表示最近使用过，越靠近尾节点表示很久没有使用，作用就是模拟具体的淘汰步骤了。
双向链表节点的结构如下
class ListNode {
int key;
int val;
ListNode prev;
ListNode next;
}LRU 的组成，我们定义 head 和 tail 作为辅助节点，表示双向链表的首尾
class LRUCache {
Map<Integer, ListNode> cache;
ListNode head;
ListNode tail;
int maxCap;
public LRUCache(int capacity) {
cache = new HashMap<>(capacity);
head = new ListNode();
tail = new ListNode();
head.next = tail;
tail.prev = head;
maxCap = capacity;
}
}具体的操作步骤
- 如果 put 进来的 key 不存在，则在 HashMap 中进行记录并插入到链表中
- 如果 put 进来的 key 已经存在，则通过 HashMap 找到对应的链表节点，修改其 value 值。接下来，就是 LRU 算法的关键部分，要把该节点从链表上取下来，并插入到链表的头部，表示该节点最近被使用过
- 如果 put 时已达到最大容量，则从链表的尾部删除一个节点（因为尾部的节点是很久没有使用过的），同时删除 HashMap 中的记录项
public void put(int key, int value) {
if (cache.containsKey(key)) { // 存在
// 获取到 key 对应的节点
ListNode node = cache.get(key);
// 修改 value 值
node.val = value;
// 把该节点从链表上取下来
node.prev.next = node.next;
node.next.prev = node.prev;
// 插入到链表头部
addToHead(node);
} else { // 不存在
// 创建一个节点
ListNode node = new ListNode();
node.key = key;
node.val = value;
// 判断是否还有空间
if (cache.size() == maxCap && maxCap != 0) {
// 已达到最大容量，移除最近最久未使用
ListNode popNode = popTail();
cache.remove(popNode.key);
}
// 插入到链表头部
addToHead(node);
// 在 map 中进行记录
cache.put(key, node);
}
}- get 方法也是同理，需要把节点从链表上取下来，并插入到链表的头部，表示该节点最近被使用过
public int get(int key) {
if (cache.containsKey(key)) {
// 获取到 key 对应的节点
ListNode node = cache.get(key);
// 把该节点从链表上取下来
node.prev.next = node.next;
node.next.prev = node.prev;
// 插入到链表头部
addToHead(node);
return node.val;
}
return -1;
}完整的代码如下：
class LRUCache {
class ListNode {
int key;
int val;
ListNode prev;
ListNode next;
}
Map<Integer, ListNode> cache;
ListNode head;
ListNode tail;
int maxCap;
public LRUCache(int capacity) {
cache = new HashMap<>(capacity);
head = new ListNode();
tail = new ListNode();
head.next = tail;
tail.prev = head;
maxCap = capacity;
}
public void addToHead(ListNode node) {
head.next.prev = node;
node.next = head.next;
head.next = node;
node.prev = head;
}
public ListNode popTail() {
ListNode tmp = tail.prev;
tmp.prev.next = tail;
tail.prev = tmp.prev;
return tmp;
}
public int get(int key) {
if (cache.containsKey(key)) {
ListNode node = cache.get(key);
node.prev.next = node.next;
node.next.prev = node.prev;
addToHead(node);
return node.val;
}
return -1;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
ListNode node = cache.get(key);
node.val = value;
node.prev.next = node.next;
node.next.prev = node.prev;
addToHead(node);
} else {
ListNode node = new ListNode();
node.key = key;
node.val = value;
if (cache.size() == maxCap && maxCap != 0) {
ListNode popNode = popTail();
cache.remove(popNode.key);
}
addToHead(node);
cache.put(key, node);
}
}
}LFU 最不经常使用