LRU（Least recently used）算法实现

1.概述

在一个有界集合中，存放每次使用的数据。当集合容纳的不同数据达到上限时，需要删除最近最少使用的数据让新使用的数据存放进来。

2.设计逻辑

1. put时，如果已存在数据，需要更新

2. get时，需要更新取出的数据为最新使用

3. put时，空间未满插入即可。当空间满了，需要更新，并且删除最少使用的数据

3.实现

实现的方法有很多，此处综合考虑使用性能较好的策略。哈希+双端链表实现。使get和put达到O(1)。

这里实现的双链表带头指针（head）(头指针指向一个空节点防止删除等异常情况)和尾指针(tail)。

1.创建一个数据结构。（链表的一个节点）

package ydcList;

/**
 * @program: demostudy
 * @description:
 * @author: yidacheng
 * @create: 2021-12-09 17:13
 **/
public class Node {
    private Integer key;
    private Integer value;
    private Node pre;
    private Node next;

    public Node(Integer key, Integer value) {
        this.key = key;
        this.value = value;
    }

    public Integer getKey() {
        return key;
    }

    public void setKey(Integer key) {
        this.key = key;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    public Node getPre() {
        return pre;
    }

    public void setPre(Node pre) {
        this.pre = pre;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

2.创建双端链表，实现add和delete方法

package ydcList;

/**
 * @program: demostudy
 * @description:
 * @author: yidacheng
 * @create: 2021-12-09 17:15
 **/
public class DoubleList {
    private Node head;
    private Node tail;
    private Long length;

    public DoubleList() {
        head = new Node(-1,-1);
        tail = head;
        length = 0L;
    }

    public void add(Node tempNode){
        tail.setNext(tempNode);
        tempNode.setPre(tail);
        //移动尾指针
        tail = tempNode;
        length++;
    }

    public void deleteFirst(){
        if(head.getNext()==null){
            return;
        }
        if(head.getNext() == tail){
            tail = head;
        }
        //删第一个节点
        head.setNext(head.getNext().getNext());
        //将第二个节点回传指针回指head
        if(head.getNext() !=null){
            head.getNext().setPre(head);
        }
        length--;
    }

    public void deleteNode(Node node){
        //断 当前节点，前置节点的后指针
        node.getPre().setNext(node.getNext());
        //连 当前节点的后节点，至当前节点的前节点
        if(node.getNext() != null){
            node.getNext().setPre(node.getPre());
        }
        //尾指针移动
        if(tail == node){
            tail = tail.getPre();
        }
        node.setPre(null);
        node.setNext(null);
        length--;
    }

    @Override
    public String toString() {
        Node team = head.getNext();
        String vaString = "len:"+length+" ";
        while (team != null) {
            vaString +="key:"+team.getKey()+" val:"+ team.getValue() + " ";
            team = team.getNext();
        }
        return vaString;
    }

    public Long getLength() {
        return length;
    }

    public void setLength(Long length) {
        this.length = length;
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public Node getTail() {
        return tail;
    }

    public void setTail(Node tail) {
        this.tail = tail;
    }
}

3.LRU算法实现

package ydcList;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @program: demostudy
 * @description:
 * @author: yidacheng
 * @create: 2021-12-09 17:34
 **/
public class LruMethod {
    private DoubleList doubleList;
    private Map<Integer, Node> map = new HashMap<>();
    private LinkedList<Integer> linkedList = new LinkedList();
    private Long maxSize;

    public LruMethod(Long size) {
        doubleList = new DoubleList();
        this.maxSize = size;
    }

    public void print() {
        System.out.print("maplen:" + map.keySet().size() + " ");
        for (Integer in : map.keySet()) {
            System.out.print("key:" + in + " val:" + map.get(in).getValue() + " ");
        }
        System.out.print("              ");
        System.out.println("listLen:" + doubleList.getLength() + " " + doubleList.toString() + " maxSize:" + maxSize);
    }

    public Integer get(int key) {
        int val;
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        val = node.getValue();
        doubleList.deleteNode(node);
        doubleList.add(node);
        return val;
    }

    public void put(Integer key, Integer value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            doubleList.deleteNode(node);
        } else if (doubleList.getLength().longValue() == maxSize) {
            Node next = doubleList.getHead().getNext();
            map.remove(next.getKey());
            doubleList.deleteFirst();
        }
        Node node = new Node(key, value);
        doubleList.add(node);
        map.put(key, node);
    }
}

4.测试

package ydcList;

/**
 * @program: demostudy
 * @description:
 * @author: yidacheng
 * @create: 2021-12-09 17:46
 **/
public class TestList {
    public static void main(String[] args) {
        LruMethod lruMethod = new LruMethod(5L);
        lruMethod.put(1,1);
        lruMethod.put(1,2);
        lruMethod.put(2,3);
        lruMethod.put(4,3);
        lruMethod.put(5,3);
        lruMethod.put(6,3);
        lruMethod.get(1);
        lruMethod.put(7,1);
        lruMethod.print();
        //此处展示的结果应该 hash顺序为 4 5 6 1 7 删除的是2
        控制台打印如下
       /**  maplen:5 
         key:1 val:2 
         key:4 val:3 
         key:5 val:3 
         key:6 val:3 
         key:7 val:1*/
        /**
        此处为算法集合的先后顺序
         * listLen:5 len:5 
         * key:4 val:3 
         * key:5 val:3 
         * key:6 val:3 
         * key:1 val:2 
         * key:7 val:1  
         * maxSize:5
         */
    }
}

完结撒花✿✿ヽ(°▽°)ノ✿