什么是LRU？ 很多时候尤其以前内存比较值钱的时候，我们空间比较宝贵，不会很大，那么就存在了重点数据和非重点数据，我们要在内存不够的时候有限保存重点数据淘汰非重点数据；LRU也就是说我们认为最近使用过的数据应该是重点数据，很久都没用过的数据应该是非重点数据，内存满了就优先删那些很久没用过的数据。 有哪些应用场景呢？ 1.手机上划显示的任务列表，都是按照最近打开顺序排列的 2.redis的lru淘汰策略
思路：
- 1.利用linkedhashmap实现lru，因为其本身就存在lru策略，只需要使用即可，这部分代码放最下面
- 2.自己写lru
手写LRU算法思路：
- 关注LRU算法需要什么？第一快，要能做到快速增加快速查找，以及数据根据访问顺序淘汰
- 那么这里就想到用Map保障数据的随机访问速度，用双链表保障数据的快速增加
- 如下代码，我们定义了双链表的结点以及双链表的重要操作（都是我们做数据新增和删除需要的数据）
手写LRU算法代码：
代码语言：javascript复制class LRUCache {
private HashMap<Integer,Node> lruCache;
private DoubleList doubleList;
private int capacity;
public LRUCache(int capacity){
this.capacity=capacity;
lruCache=new HashMap<>(capacity);
doubleList=new DoubleList();
}
public int get(int key){
if (!lruCache.containsKey(key)){
return -1;
}
int value = lruCache.get(key).val;
//将顺序提前
put(key,value);
return value;
}
public void put(int key, int value) {
//创建新结点
Node node=new Node(key,value);
if (lruCache.containsKey(key)){
//删除旧结点
doubleList.remove(lruCache.get(key));
//新结点添加
doubleList.addFirst(node);
//更新map数据
lruCache.put(key,node);
}else {
if (lruCache.size()==this.capacity){
Node last = doubleList.removeLast();
lruCache.remove(last.key);
}
doubleList.addFirst(node);
lruCache.put(key,node);
}
}
//构建node结点
class Node {
public int key, val;
public Node next, prev;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
//构建双链表
class DoubleList {
//头结点
private Node head;
//尾结点
private Node tail;
private int size=0;
// 在链表头部添加节点 node，时间 O(1)
public void addFirst(Node node){
if (head==null){
head=tail=node;
}else {
Node temp= head;
temp.prev=node;
node.next=temp;
head=node;
}
}
// 删除链表中的 node 节点（node 一定存在）
// 由于是双链表且给的是目标 Node 节点，时间 O(1)
public void remove(Node node){
if (node==head&&node==tail){
head=tail=null;
}else if (tail==node){
tail.prev.next=null;
tail=node.prev;
}else if (head==node){
head.next.prev=null;
head=node.next;
}else{
node.prev.next=node.next;
node.next.prev=node.prev;
}
}
// 删除链表中最后一个节点，并返回该节点，时间 O(1)
public Node removeLast(){
Node temp=tail;
remove(tail);
return temp;
}
// 返回链表长度，时间 O(1)
public int size(){
return size;
}
}
}LinkedHashMap实现lru代码：
代码语言：javascript复制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 super.size()>capacity;
}
}
