-
LRU缓存是什么?
-
LRU算法就是一种缓存淘汰策略，其他常见的缓存淘汰策略有这几种：
- FIFO(First in first out): 先进先出式的淘汰机制，队列式的
- LRU(Least recently used):最近最少使用的,将很长时间没有使用过的淘汰掉
- LFU(Least frequently used):计算每个信息的访问次数，踢走访问次数最少的那个；如果访问次数一样，就踢走好久没用过的那个
-
缓存是什么以及为什么要使用缓存
- 缓存的目的：
- 1.提升速度。将一些需要频繁访问的数据存放在高速缓存中，可以在需要的时候快速获取到
- 2.通过缓存一些变化频率较小的数据，来减少对数据请求方的访问次数，减少服务器的请求压力。
- 为什么需要上述的LRU等缓存策略?
因为现实中各个服务的资源都是有限的，不断堆积的数据缓存会占用大量的服务器空间，因此需要采取一些策略来释放资源以用来承载新到来的需要缓存的数据，以支持服务长期稳定的运行 - 有哪些方式实现数据缓存?
- 1.使用JDK或者其他框架所提供的容器类，在服务器内存中缓存数据
- 2.通过一些NOSql数据库服务进行缓存，不会占用当前服务器的资源。如：redis,elastic等
- 3.可以使用一些开源的已经封装好的缓存框架帮助我们更好的使用缓存。如：Spring的springCache,Alibaba开源的JetCache等
- 缓存的目的：
-
实现LRU缓存需要实现哪些功能?
- 作为缓存最基本的操作就是能够将数据写入和读取数据，最好这两种操作都能在O(1)的时间复杂度完成；
- get()操作读取数据没什么好说的：当前key存在则返回数据，不存在则返回-1；
-
写入数据时的put操作逻辑如下：
put操作.png
-
实现上述功能需要什么样的数据结构支撑?
- 在O(1)的时间复杂度内实现get操作: 使用HashMap来存储KV数据
- put()操作需要对加入的value标记其加入的顺序，且需要在O(1)的复杂度内完成数据的删除以及将其标记为最新访问的元素。
- 元素有序：使用链表可以规定元素头插或者尾插，从而使新插入的元素或者最近访问的元素存放在链表头或链表尾部来保证链表中元素的顺序
- 在较短时间内实现链表的删除：链表中删除一个节点时不仅要有该节点的指针，还需要该节点前驱结点的指针，因次可以采用双向链表DoubleLinkedList来实现O(1)的删除操作。
因此，我们可以采用哈希表和双向链表结合来实现LRU缓存。
Java中已经对拥有上述特性的类作了专门的封装，即java.util.LinkedHashMap类。（方法4）
-
具体实现（3种写法）
- 使用LinkedList和HashMap实现：
import java.util.LinkedList;
import java.util.concurrent.ConcurrentHashMap;
/**
* LRU缓存实现
*/
class LRUCache {
static class Node {
public int key, val;
public Node prev,next;
public Node(int k,int v){
this.key = k;
this.val = v;
}
}
private LinkedList<Node> cache;
private ConcurrentHashMap<Integer, Node> map;
private int cap;
public LRUCache(int capacity) {
this.cap = capacity;
this.cache = new LinkedList<>();
this.map = new ConcurrentHashMap<>();
}
public int get(int key) {
if (!map.containsKey(key)){
return -1;
}else {
Node node = map.get(key);
//移除该节点并将其插到头部
cache.remove(node);
cache.addFirst(node);
return node.val;
}
}
public void put(int key, int value) {
Node node = new Node(key, value);
if (map.containsKey(key)){
//更新值，并前置到头结点
cache.remove(map.get(key));
cache.addFirst(node);
map.put(key, node);
}else {
//不存在，先判断容量
if (cap == cache.size()){
//删除最后一个节点
Node lastNode = cache.removeLast();
map.remove(lastNode.key);
}
cache.addFirst(node);
map.put(key, node);
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
- 自己定义双向链表的实现(推荐：头插作为最近使用元素)
import java.util.concurrent.ConcurrentHashMap;
class LRUCache {
/**
* 定义链中的Node
*/
static class DLinkedNode {
int key, value;
DLinkedNode prev, next;
public DLinkedNode() {
}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
ConcurrentHashMap<Integer, DLinkedNode> map = new ConcurrentHashMap<>();
DLinkedNode head, tail;
private int size;
private int capacity;
public LRUCache(int cap) {
this.capacity = cap;
this.size = 0;
this.head = new DLinkedNode();
this.tail = new DLinkedNode();
//连接首尾节点
head.next = tail;
tail.prev = head;
}
/**
* 获取值
* @param key
* @return
*/
public int get(int key){
if (!map.containsKey(key)){
return -1;
}else {
DLinkedNode node = map.get(key);
//更新到头部
moveToHead(node);
return node.value;
}
}
/**
* 添加值
* @param key
* @param val
*/
public void put(int key,int val){
DLinkedNode node = new DLinkedNode(key, val);
//当前键值对存在，直接更新
if (map.containsKey(key)){
//删除旧值再添加，而不是直接移动
removeNode(map.get(key));
addToHead(node);
map.put(key,node);
}else {
//容量已满
if (size==capacity){
DLinkedNode tail = removeTail();
map.remove(tail.key);
size--;
}
map.put(key,node);
addToHead(node);
size++;
}
}
/**
* 添加到头结点（相当于一次插入节点 o(1)）
*
* @param node
*/
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
/**
* 删除节点（断开链）
*
* @param node
*/
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
/**
* 移动到头节点处
*
* @param node
*/
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
/**
* 删除尾结点(删除虚拟尾结点的前一个节点)
*
* @return
*/
private DLinkedNode removeTail() {
DLinkedNode node = tail.prev;
removeNode(node);
return node;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
- 自己定义双向链表的实现(推荐：尾插作为最近使用元素，并对哈希表和双向链表的处理调用多做了一层封装，使直接调用方法的逻辑更为清晰)
public class LRUCache {
//定义双向链表所需的Node类
private class Node{
public int key,val;
public Node prev,next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
//双向链表 此处假设双向链表在尾部添加节点，则头部节点为最久未使用节点
private class DoubleList{
//首尾结点
private Node head,tail;
//链表元素数
private int size;
public DoubleList() {
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
tail.prev = head;
size =0;
}
//在链表尾部添加节点x，节点数量+1
public void addLast(Node x){
x.prev = tail.prev;
x.next = tail;
tail.prev.next = x;
tail.prev = x;
size++;
}
//删除链表中的节点x
public void remove(Node x){
x.prev.next = x.next;
x.next.prev = x.prev;
size--;
}
//删除链表中的第一个节点并返回该节点
public Node removeFirst(){
if (head.next == tail){
return null;
}
Node first = head.next;
remove(first);
return first;
}
//返回链表长度
public int size(){return size;}
}
private HashMap<Integer,Node> map;
private DoubleList cache;
private int capacity;
public LRUCache(int cap) {
this.map = new HashMap<Integer,Node>();
this.cache = new DoubleList();
this.capacity = cap;
}
//将某个Key提升为最近使用
private void makeRecently(int key){
Node node = map.get(key);
//删除节点
cache.remove(node);
//添加到最近使用
cache.addLast(node);
}
//添加最近使用节点
private void addRecently(int key,int val){
Node node = new Node(key, val);
/**本代码采用链表尾部插入作为最近使用的元素*/
cache.addLast(node);
//在Map中添加key的映射
map.put(key,node);
}
//删除key
private void deleteKey(int key){
Node node = map.get(key);
//缓存中删除
cache.remove(node);
//Map中删除
map.remove(key);
}
//当缓存容量不足时，删除最久未使用的节点
private void removeLeastRecently(){
/**本代码链表头部的第一个节点即为最久未使用的节点*/
Node deleteNode = cache.removeFirst();
int key = deleteNode.key;
map.remove(key);
}
public int get(int key){
if (!map.containsKey(key)){
return -1;
}
makeRecently(key);
return map.get(key).val;
}
public void put(int key, int value) {
if (map.containsKey(key)){
//删除旧数据
deleteKey(key);
//将当前插入数据设置为最近使用
addRecently(key, value);
return;
}
if (capacity==cache.size){
removeLeastRecently();
}
addRecently(key, value);
}
}
- 直接继承java封装好的LinkedHashMap类，重写其中的关于清理最旧数据的条件即可
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
