LRU是什么

古代计算机，内存仍是相当低廉的，那么如果利用好、治理好无限的内存，来为用户提供更好的性能，是一个有意义的议题。

LRU(Least Recently Used) 即最近起码应用，属于典型的内存淘汰机制。

艰深的说，LRU算法认为，最近被频繁拜访的数据会具备更高的留存，淘汰那些不常被拜访的数据。

LRU算法实现思路

依据LRU算法的理念，咱们须要：
一个参数cap来作为最大容量
一种数据结构来存储数据，并且须要1. 轻易地更新最新的拜访的数据。2. 轻易地找出最近起码被应用的数据，当达到cap时，清理掉。
在这里，咱们用到的数据结构是：hashmap+双向链表。
1.利用hashmap的get、put办法O(1)的工夫复杂度，疾速取、存数据。
2.利用doublelinkedlist的特色（能够拜访到某个节点之前和之后的节点），实现O(1)的新增和删除数据。

如下图所示：

当key2再次被应用时，它所对应的node3被更新到链表头部。

假如cap=3，当key4创立、被拜访后，处于链表尾部的node2将被淘汰，key1将被分明。

LRU的简略实现

节点node,寄存key、val值、前节点、后节点

class Node{    public int key;    public int val;    public Node next;    public Node previous;    public Node() {    }    public Node(int key, int val) {        this.key = key;        this.val = val;    }}

双向链表，属性有size、头节点、尾节点。
提供api：

  • addFirst(): 头插法入链表
  • remove(): 删除最初一个节点
  • remove(Node node):删除特定节点
  • size()：获取链表长度
class DoubleList{    private int size;    private Node head;    private Node tail;    public DoubleList() {        this.head = new Node();        this.tail = new Node();        size = 0;        head.next = tail;        tail.previous = head;    }    public void addFirst(Node node){        Node temp = head.next;        head.next = node;        node.previous = head;        node.next = temp;        temp.previous = node;        size++;    }    public void remove(Node node){        if(null==node|| node.previous==null|| node.next==null){            return;        }        node.previous.next = node.next;        node.next.previous = node.previous;        node.next=null;        node.previous=null;        size--;    }    public void remove(){        if(size<=0) return;        Node temp = tail.previous;        temp.previous.next = temp.next;        tail.previous = temp.previous;        temp.next = null;        temp.previous=null;        size--;    }    public int size(){        return size;    }}

LRU算法实现类
API

  • get(int key): 为null返回-1

  • put(int key, int value)

    • 若map中有，删除原节点，减少新节点
    • 若map中没有，map和链表中新增新数据。
public class LRUCache {    Map<Integer,Node> map;    DoubleList cache;    int cap;    public LRUCache(int cap) {        map = new HashMap<>();        cache = new DoubleList();        this.cap = cap;    }    public int get(int key){        Node node = map.get(key);        return  node==null? -1:node.val;    }    public void put(int key, int val){        Node node = new Node(key,val);        if(map.get(key)!=null){            cache.remove(map.get(key));            cache.addFirst(node);            map.put(key,node);            return;        }        map.put(key,node);        cache.addFirst(node);        if(cache.size()>cap){            cache.remove();        }    }    public static void main(String[] args) {        //test, cap = 3        LRUCache lruCache = new LRUCache(3);        lruCache.put(1,1);        lruCache.put(2,2);        lruCache.put(3,3);        //<1,1>来到链表头部        lruCache.put(1,1);        //<4,4>来到链表头部， <2,2>被淘汰。        lruCache.put(4,4);    }}

LRU利用场景

  • 底层的内存治理，页面置换算法
  • 个别的缓存服务，memcache\redis之类
  • 局部业务场景
参考
LRU 策略详解和实现
LRU原理以及利用场景