题目

维护一个带有过期时间的LRU

coding

import java.util.*;

public class LRUWithTTL {
    // 带时间的LRU，相比于普通LRU，就是需要单独维护一个TTL，用heap来表示
    // 每次get和put都先执行删除过期节点
    // 其他时候，插入节点和删除节点和更新节点需要多维护一个堆
    class Node {
        int key;
        int value;
        long timestamp;
        Node pre;
        Node next;

        Node(int key, int value, long timestamp) {
            this.key = key;
            this.value = value;
            this.timestamp = timestamp;
        }
    }

    LRUWithTTL(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1, -1);
        tail = new Node(-1, -1, -1);
        head.next = tail;
        tail.pre = head;
        timeQueue = new PriorityQueue<>((o1, o2) ->
                Long.compare(map.get(o1).timestamp, map.get(o2).timestamp)
        );
    }

    int capacity;
    HashMap<Integer, Node> map;
    Node head;
    Node tail;
    PriorityQueue<Integer> timeQueue;

    public void put(int key, int value, long timestamp) {
        deleteOverdueNode();
        if (!map.containsKey(key)) {
            Node node = new Node(key, value, timestamp);

            if (capacity <= 0) {
                Node delNode = tail.pre;
                map.remove(delNode.key);
                popNode(delNode);
                timeQueue.remove(delNode.key);
            } else capacity--;

            map.put(key, node);
            insertNode(node);
            timeQueue.add(key);
        } else {
            Node node = map.get(key);
            node.value = value;
            node.timestamp = timestamp;

            popNode(node);
            insertNode(node);
            timeQueue.remove(key);
            timeQueue.add(key);
        }
    }

    public int get(int key) {
        deleteOverdueNode();
        if (map.containsKey(key)) {
            Node node = map.get(key);
            popNode(node);
            insertNode(node);
            return node.value;
        }
        return -1;
    }

    public void insertNode(Node node) {
        node.next = head.next;
        node.pre = head;
        node.next.pre = node;
        node.pre.next = node;
    }

    public void popNode(Node cur) {
        cur.next.pre = cur.pre;
        cur.pre.next = cur.next;
        cur.next = null;
        cur.pre = null;
    }

    public void deleteOverdueNode() {
        while (!timeQueue.isEmpty() && System.currentTimeMillis() > map.get(timeQueue.peek()).timestamp) {
            int key = timeQueue.poll();
            Node cur = map.remove(key);
            popNode(cur);
            capacity++;
        }
    }

    public static void main(String[] args) {
        String[] opts = {"LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"};
        for (String opt : opts) {
            if (opt.startsWith("LRU")) ;
            else if (opt.equals("put")) ;
            else if (opt.equals("get")) ;
        }

        System.out.println(Integer.compare(1, 2));
    }
}

• 带有TTL的LRU和普通的LRU不一样的地方在于多了一个过期时间
  • 对于过期时间的处理就是增加一个删除策略deleteOverdueNode，每次put和get的时候，都先执行一下，如果有过期的节点直接删除即可
  • 其他地方大致和普通的LRU流程一致，就是对节点insert、delete、update的时候需要同时维护时间表

ps:代码不能直接跑，因为main函数没有完善