Java 版含过期时间的 LRU 实现

在 Java 编程中，LRU（Least Recently Used，最近最少使用）算法是一种常见的数据结构和算法应用。它用于缓存管理，以优化数据的访问效率。然而，当我们需要为 LRU 缓存添加过期时间的功能时，实现就会变得更加复杂但也更实用。

让我们来了解一下 LRU 算法的基本原理。LRU 算法的核心思想是当缓存容量达到上限时，删除最近最少使用的元素。在 Java 中，可以使用双向链表和哈希表来实现 LRU 数据结构。

接下来，要实现含过期时间的 LRU，我们需要为每个元素添加一个时间戳，用于记录其插入或更新的时间。还需要一个定时任务来定期检查并删除过期的元素。

在实现过程中，双向链表用于维护元素的访问顺序，哈希表则用于快速查找元素。当一个元素被访问时，将其移到链表的头部，以表示它是最近使用的。而当插入新元素时，如果缓存已满，则删除链表尾部的元素。

对于过期时间的处理，可以使用 Java 的定时任务机制，比如 ScheduledExecutorService 。每隔一定的时间间隔，遍历链表中的元素，检查时间戳是否超过了设定的过期时间，如果超过则将其从缓存中删除。

以下是一个简单的 Java 代码示例，展示了含过期时间的 LRU 实现的关键部分：

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

class LRUItem {
    String key;
    Object value;
    long timestamp;

    LRUItem(String key, Object value) {
        this.key = key;
        this.value = value;
        this.timestamp = System.currentTimeMillis();
    }
}

class ExpiredLRUCache {
    private int capacity;
    private LinkedList<LRUItem> list;
    private Map<String, LRUItem> map;
    private ScheduledExecutorService executorService;

    ExpiredLRUCache(int capacity, long expirationMillis) {
        this.capacity = capacity;
        list = new LinkedList<>();
        map = new HashMap<>();
        executorService = Executors.newScheduledThreadPool(1);
        executorService.scheduleAtFixedRate(() -> {
            removeExpiredItems(expirationMillis);
        }, 0, expirationMillis, TimeUnit.MILLISECONDS);
    }

    private void removeExpiredItems(long expirationMillis) {
        long currentTime = System.currentTimeMillis();
        for (LRUItem item : list) {
            if (currentTime - item.timestamp > expirationMillis) {
                list.remove(item);
                map.remove(item.key);
            }
        }
    }

    public Object get(String key) {
        if (map.containsKey(key)) {
            LRUItem item = map.get(key);
            list.remove(item);
            list.addFirst(item);
            return item.value;
        }
        return null;
    }

    public void put(String key, Object value) {
        if (map.containsKey(key)) {
            LRUItem item = map.get(key);
            item.value = value;
            list.remove(item);
            list.addFirst(item);
        } else {
            if (list.size() >= capacity) {
                LRUItem lastItem = list.removeLast();
                map.remove(lastItem.key);
            }
            LRUItem newItem = new LRUItem(key, value);
            list.addFirst(newItem);
            map.put(key, newItem);
        }
    }
}

通过上述的实现，我们在 Java 中成功构建了一个含过期时间的 LRU 缓存，能够更好地适应实际应用中的需求，提高系统的性能和资源利用率。