LRU淘汰算法

LRU：Least Recently Used，最近最少使用。即淘汰掉最近最少使用的数据。
以时间轴作为走向：
在这里插入图片描述
如果数据A刚被访问，那么A就应该调至头部：

假如内存容量已满，现在新数据E被插入，需要淘汰一条数据，那么只需要从尾部开始淘汰，即B被淘汰，E插入头部：

上面的时间轴可以用双向链表来表示，可以方便的调整数据位置。但是链表的查询效率较低，所以可以在用一个Map作为查询使用，查询复杂度为O(1)。这样下面的数据结构就能完美实现LRU缓存淘汰策略了：
在这里插入图片描述
1. 新数据插入：追加到链表尾部。
2. 如果缓存容量已满，则从头部删除后再在头部插入数据。
3. 缓存中的数据再次被访问：将该节点移至尾部。

力扣LRU题解

原题：

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
1. LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
3. void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
* 示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
* 解释:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put

题解：

代码实现：

class LRUCache {//缓存节点private class CacheNode{CacheNode prev;CacheNode next;int key;int value;private CacheNode(int key,int value){this.key = key;this.value = value;this.prev = null;this.next = null;}}//缓存容量private int capacity;//key与节点映射private Map<Integer,CacheNode> valNodeMap;private CacheNode head = new CacheNode(-1,-1);private CacheNode tail = new CacheNode(-1,-1);public LRUCache(int capacity) {this.capacity = capacity;valNodeMap = new HashMap(capacity);this.head.next = tail;this.tail.prev = head;}public int get(int key) {if(!valNodeMap.containsKey(key)){return -1;}CacheNode node = valNodeMap.get(key);node.prev.next = node.next;node.next.prev = node.prev;moveToTail(node);return node.value;}public void put(int key, int value) {if(get(key)!=-1){valNodeMap.get(key).value = value;return;}CacheNode node = new CacheNode(key,value);if(valNodeMap.size() == capacity){//淘汰valNodeMap.remove(head.next.key);head.next.next.prev = head;head.next = head.next.next;}valNodeMap.put(key,node);//追加moveToTail(node);}public void moveToTail(CacheNode node){node.prev = this.tail.prev;this.tail.prev.next = node;node.next = this.tail;this.tail.prev = 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);*/

LFU淘汰算法

LFU算法：即最不经常使用淘汰算法。缓存数据会记录被访问的次数，每次被访问次数加一，当需要淘汰数据时，会淘汰使用次数最少的缓存数据。

数据结构

使用一个map作为数据查询，同时也需要一个map用于缓存淘汰，如下图，两个链表即表述缓存淘汰map，该map的value存储的是一个双向链表，链表中是相同使用次数的数据。

数据插入：在相应次数的链表中头节点插入。
缓存淘汰：从使用次数最小的链表尾部删除缓存数据。
数据访问：使用次数加1，原有次数链表中移除，添加到新的链表中。

代码实现：

package com.hiwe.demo.cache;import java.util.HashMap;
import java.util.Map;public class LfuCache {//缓存容器private Map<String,Node> cache;//用于存储缓存数据使用次数private Map<Integer,DoubleLinkedList> useTimes;//容量大小private Integer capacity;//已使用容量private Integer useCap = 0;//全局数据最少使用次数private Integer minUseTimes = 1;public LfuCache(Integer capacity){cache = new HashMap<>();this.capacity = capacity;useTimes = new HashMap<>();}/*** 添加数据* @param key* @param value* @return*/public boolean put(String key,String value){Node node = cache.get(key);if(node==null){node = new Node(key,value);cache.put(key,node);useCap++;if(useCap>capacity){//缓存淘汰eliminate();}}else{node.value=value;node.times++;}//次数增加addTimes(node);return true;}/*** 获取数据* @param key* @return*/public String get(String key){Node node = cache.get(key);if(node==null){return null;}//添加到对应次数的链表中node.times++;addTimes(node);return node.value;}/*** 缓存数据淘汰*/private void eliminate(){DoubleLinkedList linkedList = useTimes.get(minUseTimes);String key = linkedList.remove();cache.remove(key);}/*** 数据访问次数添加* @param node*/private void addTimes(Node node){int times = node.times;DoubleLinkedList link = useTimes.get(times);if(link==null){link = new DoubleLinkedList();useTimes.put(times,link);}link.put(node);//记录当前存在数据的最小访问次数if(times>1){DoubleLinkedList preLink = useTimes.get(times-1);preLink.delSize();if(times-1<minUseTimes&&preLink.size>0){minUseTimes=times-1;}}}private class DoubleLinkedList{private Integer size=0;private Node head = new Node(null,null);private Node tail = new Node(null,null);public DoubleLinkedList(){head.next = tail;tail.pre = head;}public void put(Node node){//如果之前存在，则从之前链删除if(node.pre!=null&&node.next!=null){node.pre.next=node.next;node.next.pre = node.pre;}//添加到链表中size++;Node temp = head.next;head.next = node;node.pre = head;node.next = temp;temp.pre = node;}/*** 移除节点* @return key*/public String remove(){Node temp = tail.pre;tail.pre = temp.pre;temp.pre.next = tail;temp.pre=null;temp.next=null;return temp.key;}public void delSize(){size--;}}/*** 数据节点*/private class Node{private String key;private String value;private Integer times = 1;private Node pre=null;private Node next=null;public Node(String key,String value){this.key = key;this.value = value;}}
}

测试代码：

package com.hiwe.demo.cache;public class TestCache {public static void main(String[] args) {LfuCache lfuCache = new LfuCache(2);lfuCache.put("bbb","bbb");lfuCache.put("aaa","aaa");lfuCache.get("bbb");lfuCache.put("ccc","ccc");System.out.println(lfuCache.get("aaa"));System.out.println(lfuCache.get("bbb"));System.out.println(lfuCache.get("ccc"));}
}