LRU+定期删除

直接上代码

package com.kael.modules.data;

import org.jetbrains.annotations.NotNull;

import java.util.*;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;

/**
 * 设计一个对象cache, 他支持下列两个基本操作:
 * set(id, object), 根据id设置对象;
 * get(id): 根据id得到一个对象;
 * 同时它有下面几个性质:
 * 1: x秒自动过期, 如果cache内的对象, x秒内没有被get或者set过, 则会自动过期;
 * 2: 对象数限制, 该cache可以设置一个n, 表示cache最多能存储的对象数;
 * 3: LRU置换, 当进行set操作时, 如果此时cache内对象数已经到达了n个,
 * 则cache自动将最久未被使用过的那个对象剔除, 腾出空间放置新对象;
 * 请你设计这样一个cache;
 */
public class LRUTest {


    public static void main(String[] args) {

        LRUTest lruTest = new LRUTest(5);
        lruTest.put(1,1,0);
        lruTest.put(2,2,1);
        lruTest.put(6,6,1);
        lruTest.print();
        lruTest.put(3,3,10);
        lruTest.print();
        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        System.out.println("");

        lruTest.get(1);
        lruTest.print();
    }

    private Map<Integer,Node>  map ;

    private Node head;

    private Node tail;

    private int cap;

    private DelayQueue queue = new DelayQueue<Node>();


    public LRUTest(int cap){
        this.map = new HashMap<>();
        this.head = new Node(0,0);
        this.tail = new Node(0,0);
        head.next = tail;
        tail.pre = head;
        this.cap = cap;

        new Thread(()->{
            while (true){
                try {
                    Node take = (Node) queue.take();
                    this.removeNode(take);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }

            }
        }).start();
    }

    /**
     *
     * @param node
     */
    public void addTail(Node node){
        Node tailPre = tail.pre;

        tail.pre = node;
        node.next = tail;
        node.pre = tailPre;

        tailPre.next = node;
    }


    /**
     * 后移
     * @param node
     */
    public void popToTail(Node node){
        Node nodeNext = node.next;
        Node nodePre = node.pre;

        nodePre.next = nodeNext;
        nodeNext.pre = nodePre;

        Node tailPre = tail.pre;
        tailPre.next = node;
        node.pre = tailPre;
        node.next = tail;

        tail.pre = node;

    }

    /**
     * 过期清除节点
     * @param node
     */
    public synchronized void removeNode(Node node){
        if(map.get(node.key)!=null){
            System.out.println("del node:"+node);
            Node nodeNext = node.next;
            Node nodePre = node.pre;
            nodePre.next = nodeNext;
            nodeNext.pre = node.pre;
            map.remove(node.key);
        }
    }


    /**
     * 移除第一个
     */
    public void removeFirst(){
        Node firstNode = head.next;
        Node sce = firstNode.next;
        head.next = sce;
        sce.pre = head;

        queue.remove(firstNode);
    }


    /**
     * 获取元素
     * @param id
     * @return
     */
    public synchronized Object get(int id){
        if(map.get(id)!=null){

            Node node = map.get(id);
            queue.remove(node);
            //刷新时间
            node.refreshExpire(node.expire);

            popToTail(node);
            queue.put(node);
            return map.get(id).value;
        }
        return null;
    }

    /**
     * set
     * @param id
     * @param value
     * @param expire
     */
    public synchronized void put(int id, Object value,int expire){

        if(map.get(id)==null){
            Node node = new Node(id, value,expire);
            if(cap<=map.size()){
                removeFirst();
                map.remove(id);
            }
            addTail(node);
            map.put(id,node);
            if(expire>0){
                queue.put(node);
            }
        } else {
            Node node = (Node) map.get(id);
            popToTail(node);
            if(expire>0){
                queue.remove(node);
                //刷新时间
                node.refreshExpire(expire);
                queue.put(node);
            }
        }


    }



    public void print(){
        Node node = head;
        while (node.next!=null){
            System.out.print(node.value + " -> ");
            node = node.next;
        }
        System.out.println();
    }




    class Node implements Delayed {
        public int expire;
        public long expireTime;

        public Integer key;
        public Object value;
        public Node pre;
        public Node next;

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

        public Node(Integer key, Object value,int expire) {
            this.key = key;
            this.value = value;
            this.expire = expire;
            this.expireTime = new Date().getTime() + expire*1000;
        }

        public void refreshExpire(int expire){
            this.expire  = expire;
            this.expireTime = new Date().getTime() + expire*1000;
        }

        @Override
        public long getDelay(@NotNull TimeUnit unit) {
            Date date = new Date();

            return unit.convert(expireTime-date.getTime(),TimeUnit.MILLISECONDS);
        }

        @Override
        public int compareTo(@NotNull Delayed o) {
            if(o instanceof  Node){
                Node node = (Node)o;
                //排后面
                if(expireTime > node.expireTime){
                    return 1;
                }
                //排前面
                if(expireTime <= node.expireTime){
                    return -1;
                }
            }
            return 0;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "expire=" + expire +
                    ", expireTime=" + expireTime +
                    ", key=" + key +
                    ", value=" + value +
                    '}';
        }
    }


}