手撕—带过期时间的LRU

与传统的LRU类似，使用双向链表+哈希表来完成

• 双向链表按照被使用顺序存储键值对，靠近头部的键值对是最近使用的，哈希表通过缓存数据的键映射到其在双向链表中的位置

• 对于get操作，首先判断key是否存在，如果key存在，再判断key是否过期，如未过期，则key对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值

• 对于put操作，首先清理所有过期的节点，再判断key是否存在，如果key不存在，使用key和value创建一个新的节点，在双向链表的头部添加该节点，并将key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项。如果key存在，先通过哈希表定位，再将对应的节点的值更新为value，并将该节点移到双向链表的头部

以系统时间为基准

// 双向链表节点类
class DLinkedList{
    int key;
    int value;
    long expireTime;
    DLinkedList pre;
    DLinkedList next;

    public DLinkedList() {}

    public DLinkedList(int key, int value, long ttlMillis){
        this.key = key;
        this.value = value;
        this.expireTime = System.currentTimeMillis() + ttlMillis;
    }
}

public class ExpirableLRUCache {
    private int cnt, capacity;
    private DLinkedList head, tail;
    private Map<Integer, DLinkedList> map = new HashMap<>();
    
    public ExpirableLRUCache(int capacity) {
        this.capacity = capacity;
        this.head = new DLinkedList();
        this.tail = new DLinkedList();
        head.next = tail;
        tail.pre = head;
    }
    
    private void removeNode(DLinkedList node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        map.remove(node.key);
    }
    
    private void addToHead(DLinkedList node){
        node.next = head.next;
        node.pre = head;
        head.next = node;
        node.next.pre = node;
        map.put(node.key, node);
    }
    
    private void moveToHead(DLinkedList node){
        removeNode(node);
        addToHead(node);
    }
    
    private void removeTail(){
        DLinkedNode node = tail.pre;
        if(node != head){
            removeNode(node);
            cnt--;
        }
    }
	
    private boolean isExpired(DLinkedList node){
        return System.currentTimeMillis() > node.expireTime;
    }
    
    private void removeExpiredNodes(){
        DLinkedList cur = tail.pre;
        while(cur != head){
            if(isExpired(cur)){
                DLinkedList pre = cur.pre;
                removeNode(cur);
                map.remove(cur.key);
                cnt --;
                cur = pre;
            } else {
                cur = cur.pre;
            }
        }
    }
    
    public int get(int key){
        if(map.containsKey(key)){
            DLinkedList node = map.get(key);
            if(isExpired(node)){
                removeNode(node);
                cnt --;
                return -1;
            }
            moveToHead(node);
            return node.value;
        }
        return -1;
    }
    
    public void put(int key, int value, long ttlMillis){
        removeExpiredNodes();
        if(map.containsKey(key)){
            DLinkedList node = map.get(key);
            node.value = value;
            node.expireTime = System.currentTimeMillis() + ttlMillis;
            moveToHead(node);
        } else {
            cnt ++;
            DLinkedList node = new DLinkedList(key, value, ttlMillis);
            addToHead(node);
            if(cnt > capacity){
                removeTail();
            }
        }
    }
}

逻辑过期时间

class DLinkedList {
    int key;
    int value;
    int expireStep; // 逻辑时间到期步数
    DLinkedList pre, next;

    public DLinkedList(int key, int value, int expireStep) {
        this.key = key;
        this.value = value;
        this.expireStep = expireStep;
    }
}

public class ExpirableLRUCache {
    private int capacity;
    private int currentStep = 0; // 逻辑时间步
    private DLinkedList head, tail;
    private Map<Integer, DLinkedList> map = new HashMap<>();

    public StepLRUCache(int capacity) {
        this.capacity = capacity;
        head = new DLinkedList(-1, -1, -1);
        tail = new DLinkedList(-1, -1, -1);
        head.next = tail;
        tail.pre = head;
    }

    private void removeNode(DLinkedList node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        map.remove(node.key);
    }

    private void addToHead(DLinkedList node) {
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
        map.put(node.key, node);
    }

    private void moveToHead(DLinkedList node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeTail() {
        DLinkedList node = tail.pre;
        if (node != head) {
            removeNode(node);
        }
    }

    private void removeExpiredNodes() {
        DLinkedList cur = tail.pre;
        while (cur != head) {
            DLinkedList pre = cur.pre;
            if (cur.expireStep <= currentStep) {
                removeNode(cur);
            }
            cur = pre;
        }
    }

    public int get(int key) {
        currentStep++;
        removeExpiredNodes();

        if (!map.containsKey(key)) return -1;

        DLinkedList node = map.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value, int ttlSteps) {
        currentStep++;
        removeExpiredNodes();

        if (map.containsKey(key)) {
            DLinkedList node = map.get(key);
            node.value = value;
            node.expireStep = currentStep + ttlSteps;
            moveToHead(node);
        } else {
            DLinkedList node = new DLinkedList(key, value, currentStep + ttlSteps);
            addToHead(node);
            if (map.size() > capacity) {
                removeTail();
            }
        }
    }
}