LRU
思想
- 淘汰最长时间未被使用的数据。
- 最近使用的数据优先保留，久未使用的优先淘汰。
原理
- 哈希表（key → node）
- 双向链表（记录使用顺序，头部是最新使用，尾部是最旧）
- 当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部， 如果不存在，则新建一个节点，放到链表头部 若缓存满了，则把链表最后一个节点删除即可。
- 在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。 这样一来在链表尾部的节点就是最近最久未访问的数据项。
import java.util.HashMap;
import java.util.LinkedList;
/**
LRU Cache
题目描述：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
思路：
双向链表和hashmap。
1.当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，
如果不存在，则新建一个节点，放到链表头部
若缓存满了，则把链表最后一个节点删除即可。
2.在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。
这样一来在链表尾部的节点就是最近最久未访问的数据项。
*/
//leetcode pass
public class LRUCache {
private int capacity;
private LinkedList<Integer> list;
private HashMap<Integer, Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
list = new LinkedList<>();
map = new HashMap<>();
}
public int get(int key) {
if (map.containsKey(key)) {
list.removeFirstOccurrence(key);
list.addFirst(key);
return map.get(key);
} else {
return -1;
}
}
public void put(int key, int value) {
if (!map.containsKey(key)) {
if (list.size() == capacity) {
int last = list.removeLast();
map.remove(last);
}
list.addFirst(key);
map.put(key, value);
} else {
list.removeFirstOccurrence(key);
list.addFirst(key);
map.put(key, value);
}
}
}
LFU
✅ 核心思想：
- 淘汰访问次数最少的数据。
- 频率低的数据说明“几乎没人用”，优先淘汰。
✅ 数据结构：
LFU（Least Frequently Used）缓存淘汰策略，结合了：
- Node 双向链表：记录具体缓存键值和访问频率。
- DoubleLinkedList 双向链表：每个频率都有一个 list，list 中按 LRU 排序。
- 双重链表结构：外层链表是按频率从高到低排，内层链表是每个频率下的缓存节点。
- 每次访问（
get）或更新（put）都会增加节点频率，并移动到高一频次的 list 中。 - 当缓存满时，淘汰 频率最小且最久未访问的 节点（也就是最靠近尾部的 node）。
每个
DoubleLinkedList存储相同频率的节点，内部使用 LRU 顺序。- LinkedNode存了前后指针，频率，还有上层链表对应的node.
- 第一层链表是每个频率一个node. 第二层是相同频率的一个map。 通过cache直接定位node，然后在第一层链表里后移。
- 双层链表，cache里存的最小单位的节点。
- put
- 找到接口，找到上层链表，后移插入
from collections import defaultdict
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.freq = 1
self.prev = self.next = None
self.parent = None # 所属频率链表
class DoubleLinkedList:
def __init__(self, freq):
self.freq = freq
self.head = Node(None, None) # 哨兵头
self.tail = Node(None, None) # 哨兵尾
self.head.next = self.tail
self.tail.prev = self.head
self.prev = self.next = None # 前后频率的 list
def add_node(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
node.parent = self
def remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def is_empty(self):
return self.head.next == self.tail
class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.cache = {} # key -> node
# 外层 freq 链表哨兵
self.first = DoubleLinkedList(None)
self.last = DoubleLinkedList(None)
self.first.next = self.last
self.last.prev = self.first
def _remove_list(self, dl):
dl.prev.next = dl.next
dl.next.prev = dl.prev
def _add_list_after(self, new_list, prev_list):
new_list.prev = prev_list
new_list.next = prev_list.next
prev_list.next.prev = new_list
prev_list.next = new_list
def _inc_freq(self, node):
old_list = node.parent
old_list.remove_node(node)
if old_list.is_empty():
self._remove_list(old_list)
node.freq += 1
prev = old_list.prev
if prev.freq != node.freq:
new_list = DoubleLinkedList(node.freq)
self._add_list_after(new_list, prev)
else:
new_list = prev
new_list.add_node(node)
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._inc_freq(node)
return node.value
def put(self, key, value):
if self.capacity == 0:
return
if key in self.cache:
node = self.cache[key]
node.value = value
self._inc_freq(node)
else:
if self.size == self.capacity:
min_list = self.last.prev
dead = min_list.tail.prev
min_list.remove_node(dead)
if min_list.is_empty():
self._remove_list(min_list)
del self.cache[dead.key]
self.size -= 1
new_node = Node(key, value)
self.cache[key] = new_node
if self.last.prev.freq != 1:
new_list = DoubleLinkedList(1)
self._add_list_after(new_list, self.last.prev)
else:
new_list = self.last.prev
new_list.add_node(new_node)
self.size += 1