带过期时间的LRU（可运行）

import java.util.*;

class Node {
    public Integer key;
    public Integer value;
    public Long timeStamp;

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

class LRUCache {
    private Map<Integer, Node> map;
    private int capacity;

    public LRUCache(int capacity) {
        map = new LinkedHashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = map.get(key);
        // key 不存在
        if (node == null) {
            return -1;
        }
        // key 过期（懒删除策略）
        if (isExpire(node)) {
            map.remove(key);
            return -1;
        }
        map.remove(key);
        map.put(key, node);
        return node.value;
    }

    public void put(int key, int value, Long timeStamp) {
        Node node = map.get(key);
        if (node == null) {  // key 不存在
            node = new Node(key, value, timeStamp);
            if (map.size() < capacity) {  // 有额外空间
                map.put(key, node);
            } else {  // 没有额外空间
                // 先尝试移除过期key
                removeExpireNodes();
                // 如果空间还是不足，移除最老的key
                if (map.size() >= capacity) {
                    map.remove(map.keySet().iterator().next());
                }
                map.put(key, node);
            }
        } else {  // key 存在
            map.remove(key);
            node = new Node(key, value, timeStamp);
            map.put(key, node);
        }
    }

    private void removeExpireNodes() {
        for (Node node : map.values()) {
            if (isExpire(node)) {
                map.remove(node.key);
            }
        }
    }

    private boolean isExpire(Node node) {
        if (node.timeStamp == null) {  // 没有时间戳表示永久不过期
            return false;
        }
        return System.currentTimeMillis() > node.timeStamp;
    }

}

class LRUTTL {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);

        cache.put(1, 10, null);
        cache.put(2, 20, null);
        System.out.println(cache.get(1));  // 10
        cache.put(3, 30, null);
        System.out.println(cache.get(2));  // -1

        cache.put(4, 40, System.currentTimeMillis() + 1000);

        try {
            System.out.println(cache.get(1));  // -1
            Thread.sleep(1500);
            System.out.println(cache.get(3));  // 30
            System.out.println(cache.get(4));  // -1
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }

    }
}

优化点：可以维护一个map结构存储<最小过期时间，节点数量>来判断当前LinkedList中是否存在已经过期的node，可以一定程度地减少 removeExpireNodes 的调用次数