1、内存空间有限,当缓存满的时候,如何淘汰缓存?
FIFO(First In First Out)先进先出
LFU(Least Frequently Used)最不经常使用
LRU(Least Recently Used)最近最少使用
2、实现LRU demo
1、使用Java容器LinkedHashMap
LinkedHashMap本身就具有LRU算法的特性
class LRUCache {
private Map<Integer, Integer> cacheMap = null;
public LRUCache(int capacity) {
// 参数设置true,当removeEldestEntry()返回true,则删除最旧的数据
cacheMap = new LinkedHashMap<Integer, Integer>(capacity,0.75F,true){
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
};
}
public int get(int key) {
return cacheMap.getOrDefault(key, -1);
}
public void put(int key, int value) {
cacheMap.put(key, value);
}
}
2、哈希表(HashMap)+双向链表
- 维护一个双向链表,靠近链表尾部的结点是越早访问的,靠近头部的节点是最近访问的。
- 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
- 如果此数据没有在缓存链表中,又可以分为两种情况:
如果此时缓存未满,则将此结点直接插入到链表的头部
如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。
![在这里插入图片描述](https://img-blog.csdnimg.cn/2741955fec8c41e38982bde6c1024a57.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5p2OX-adsA==,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)
class LRUCache2 {
// 当前缓存容量
private int size;
// 限制最大缓存容量
private int capacity;
// 定义伪头尾节点
private Node head;
private Node tail;
// 定义HashMap存储数据
private Map<Integer, Node> cache = new HashMap();
// 初始化操作
public LRUCache2(int capacity) {
size = 0;
this.capacity = capacity;
// 初始化头尾节点
head = new Node();
tail = new Node();
// 让头尾节点相联
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = cache.get(key);
// 不存在返回-1
if (null == node) {
return -1;
}
// 存在返回值,并且将当前节点移动到头
moveNodeHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
// 不存在则插入,插入后判断当前容量是否大于限制最大容量
if (null == node) {
Node newNode = new Node(key, value);
cache.put(key, newNode);
// 放入链表头部
addNodeHead(newNode);
size++;
if (size > capacity) {
// 删除尾结点
Node tail = removeNodeTail();
cache.remove(tail.key);
}
} else {
// 存在则覆盖value,并且将当前节点移动到头
node.value = value;
moveNodeHead(node);
}
}
// 放入链表的头部
private void addNodeHead(Node node) {
// 当前头节点的下一个节点的pre和当前节点连接
head.next.pre = node;
//
node.next = head.next;
//
head.next = node;
node.pre = head;
}
// 将节点移动到链表的头部
private void moveNodeHead(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
addNodeHead(node);
}
// 删除链表的尾结点
private Node removeNodeTail() {
Node tailNode = tail.pre;
tailNode.pre.next = tailNode.next;
tailNode.next.pre = tailNode.pre;
return tailNode;
}
// 定义一个双向链表,实际的缓存
class Node {
private int key;
private int value;
private Node pre;
private Node next;
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}