我们常用缓存提升数据查询速度,由于缓存容量有限,当缓存容量达到上限,就需要删除部分数据挪出空间,这样新数据才可以添加进来,缓存数据不能随机删除,一般情况下我们需要根据某种算法删除缓存数据,常用的淘汰算法有LRU,LFU,FIFO
LRU简介
LRU是Least Recently Used的缩写,这种算法认为最近使用的数据是热门数据,下一次很大概率将会再次使用,而最近最少被使用的数据,很大概率下一次不再用到,当缓存容量满的时候,优先淘汰最近最少使用的
如下图所示,队列只能够存放5个元素
当调用缓存获取key = 1的数据,LRU算法需要将这个节点移动到头节点,其余节点不变
当缓存满的时候,添加新的数据会优先淘汰最近最少使用的
LRU数据结构选择
综合以上问题,可以结合其他数据结构解决
O(1) 的快速查找,就哈希表了。光靠哈希表可以吗?哈希表是无序的,无法知道里面的键值对哪些最近访问过,哪些很久没访问。
快速删除,谁合适?
- 数组?元素的插入/移动/删除都是 O(n)/O(n)。不行。
- 单向链表?删除节点需要访问前驱节点,只能花 O(n)/O(n) 从前遍历查找。不行。
- 双向链表,结点有前驱指针,删除/移动节点都是纯纯的指针变动,都是 O(1)/O(1)。
LRU代码实现
package com.example;
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
//定义头节点和尾节点
Entry head, tail;
//定义缓存容量大小
int capacity;
//定义双向链表长度
int size;
//定义散列表
Map<Integer, Entry> cache;
//初始化
public LRUCache(int capacity) {
this.capacity = capacity;
//初始化链表
initLinkedList();
size = 0;
cache = new HashMap<>(capacity + 2);
}
//如果节点不存在,返回 -1.如果存在,将节点移动到头结点,并返回节点的数据。
public int get(int key) {
//O(1)从HashMap中得到缓存命中的节点
Entry node = cache.get(key);
//如果缓存没有命中就返回-1
if (node == null) {
return -1;
}
//缓存命中执行以下操作
moveToHead(node);
return node.value;
}
//将节点加入到头结点,如果容量已满,将会删除尾结点
public void put(int key, int value) {
//查看放入的节点缓存能否命中
Entry node = cache.get(key);
//缓存命中就更新节点的值然后将节点放到队头
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
//不存在,先加进去,再移除尾结点
//此时容量已满 删除尾结点
if (size == capacity) {
Entry lastNode = tail.pre;
deleteNode(lastNode);
cache.remove(lastNode.key);
size--;
}
//加入头结点
Entry newNode = new Entry();
newNode.key = key;
newNode.value = value;
addNode(newNode);
cache.put(key, newNode);
size++;
}
private void moveToHead(Entry node) {
//首先删除原来节点的关系
deleteNode(node);
//将缓存命中的节点添加到头部
addNode(node);
}
//将缓存命中的节点添加到头部
private void addNode(Entry node) {
head.next.pre = node;
node.next = head.next;
node.pre = head;
head.next = node;
}
//删除双向链表中的节点
private void deleteNode(Entry node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
//定义双向链表中的节点
public static class Entry {
public Entry pre;
public Entry next;
public int key;
public int value;
public Entry(int key, int value) {
this.key = key;
this.value = value;
}
public Entry() {
}
}
//初始化链表
private void initLinkedList() {
//初始化头节点和尾节点
head = new Entry();
tail = new Entry();
head.next = tail;
tail.pre = head;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2); // 21
System.out.println(cache.get(1)); // 12
cache.put(3, 3); // 31
System.out.println(cache.get(2));
}
}