缓存淘汰算法/LRU

概述

LRU（Least Recently Used）最近最少使用策略就像它的名字一样，是根据数据的历史访问记录来进行淘汰数据的，其思想是“如果数据最近被访问过，那么将来被访问的几率也更高；长期不被使用的数据在将来用到的几率也不大；当数据所占内存达到一定的阈值时，将移除最近最少被使用的数据”

步骤

1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
   如果此时缓存未满，则将此结点直接插入到链表的头部；
   如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

LRU缓存需要维护一个跟时间顺序关联的数据结构

使用LinkedHashMap

public class LRUCache{
    int capacity;
    Map<Integer, Integer> map;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>();
    }
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        //先删除旧的位置，再放入新位置
        Integer value = map.remove(key);
        map.put(key, value);
        return value;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
            map.put(key, value);
            return;
        }
        map.put(key, value);
        //超出capacity，删除最久没用的,利用迭代器，删除第一个
        if (map.size() > capacity) {
            map.remove(map.entrySet().iterator().next().getKey());
        }
    }
}

使用双链表+HashMap

public class LRUCache{
    //定义双向链表节点
    private class ListNode {
        int key;
        int val;
        ListNode pre;
        ListNode next;
        public ListNode(int key, int val) {
            this.key = key;
            this.val = val;
            pre = null;
            next = null;
        }
    }
    private int capacity;
    private Map<Integer, ListNode> map;     //key->node
    private ListNode head;  //dummy head
    private ListNode tail;  //dummy tail
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.pre = head;
    }
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        ListNode node = map.get(key);
        //先把这个节点删除，再接到尾部
        node.pre.next = node.next;
        node.next.pre = node.pre;
        moveToTail(node);
        return node.val;
    }
    public void put(int key, int value) {
        //直接调用这边的get方法，如果存在，它会在get内部被移动到尾巴，不用再移动一遍,直接修改值即可
        if (get(key) != -1) {
            map.get(key).val = value;
            return;
        }
        //不存在，new一个出来,如果超出容量，把头去掉
        ListNode node = new ListNode(key, value);
        map.put(key, node);
        moveToTail(node);
        if (map.size() > capacity) {
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.pre = head;
        }
    }
    private void moveToTail(ListNode node) {
        node.pre = tail.pre;
        tail.pre = node;
        node.pre.next = node;
        node.next = tail;
    }
}

使用单链表

public class LRUCache{
    private class ListNode {
        int key, val;
        ListNode next;
        public ListNode(int key, int val) {
            this.key = key;
            this.val = val;
            this.next = null;
        }
    }
    private int capacity;
    private Map<Integer, ListNode> map;     //key-> node.pre
    private ListNode head;  //dummy
    private ListNode tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new ListNode(-1, -1);
        tail = head;
    }
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        //map中存放的是要找的节点的前驱
        ListNode pre = map.get(key);
        ListNode cur = pre.next;
        //把当前节点删掉并移到尾部
        if (cur != tail) {
            pre.next = cur.next;
            map.put(cur.next.key, pre); //更新它后面node的前驱
            map.put(cur.key, tail);
            moveToTail(cur);
        }
        return cur.val;
    }
    public void put(int key, int value) {
        if (get(key) != -1) {
            map.get(key).next.val = value;
            return;
        }
        //不存在就new一个
        ListNode node = new ListNode(key, value);
        map.put(key, tail); //当前node的pre是tail
        moveToTail(node);
        if (map.size() > capacity) {
            map.remove(head.next.key);
            map.put(head.next.next.key, head);
            head.next = head.next.next;
        }
    }
    private void moveToTail(ListNode node) {
        node.next = null;
        tail.next = node;
        tail = tail.next;
    }
}

package main
type Node struct {
    key,val int
    next,prev *Node
}
type LRUCache struct {
    cap int // 缓存容量
    cache map[int]*Node//判断数据是否存在
    head *Node //头指针
    tail *Node // 尾指针
}
func NewLRUCache(capacity int)*LRUCache{
    l :=&LRUCache{
        cap:  capacity,
        cache: make(map[int]*Node),
        head:  &Node{},
        tail:  &Node{},
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}
// 双链表在头部插入数据
func (l *LRUCache)insertHead(node *Node){
    tmp := l.head.next
    l.head.next = node
    node.next = tmp
    tmp.prev = node
    node.prev = l.head
}
// 双链表删除数据
func (l *LRUCache)remove(node *Node){
    n := node.next// 获取后节点
    p := node.prev // 获取前节点
    p.next = n
    n.prev = p
    node.next = nil
    node.prev = nil
}
func(l *LRUCache)Get(key int)int{
    if n,ok:=l.cache[key];ok{
        l.remove(n)
        l.insertHead(n)
        return n.val
    }
    return -1
}
func(l *LRUCache)Put(key int,value int){
    if n,ok:=l.cache[key];ok{
        n.val =value
        l.remove(n)
        l.insertHead(n)
    }else {
        if len(l.cache)==l.cap {//需要判断当前容器是否已经满了
            deleteNode := l.tail.prev
            delete(l.cache,deleteNode.key)
            l.remove(deleteNode)
        }
        n :=&Node{
            key:  key,
            val:  value,
        }
        l.insertHead(n)
        l.cache[key]= n
    }
}
func main() {
}

参考

https://blog.csdn.net/fdl123456/article/details/97623208