- 正确答案：实现一个支持TTL（Time-To-Live）的LRU缓存，需同时满足两个核心约束：1）容量限制下的最近最少使用淘汰策略；2）每个key-value对具有独立过期时间，过期后自动失效（即使未被访问或未满容）。典型实现是组合哈希表 + 双向链表 + 定时/惰性过期机制。推荐采用“惰性删除 + 定期清理”混合策略，避免高并发下定时器爆炸；核心数据结构为：HashMap 存储key到带ttl信息节点的映射，Node包含value、expireTime（毫秒级绝对时间戳）、prev/next指针；维护head/tail伪节点构成的双向链表，head.next为最近访问节点，tail.prev为最久未访问节点。 - 解答思路：第一步：明确接口需求——get(key)需返回value并刷新访问顺序和剩余TTL（若未过期）；put(key, value, ttlMs)需插入或更新，若已存在则更新value和expireTime并移至链表头；若容量超限，先驱逐过期key（惰性），再按LRU驱逐最久未用的有效key。第二步：设计Node类，必须封装expireTime（long类型，System.currentTimeMillis() + ttlMs），而非相对TTL，避免每次比较需重新计算，提升判断效率。第三步：在get/put入口处统一做“惰性过期检查”——遍历链表头部若干节点（如3~5个）检查是否过期，过期则unlink并从HashMap中remove；不扫描全链表，保证O(1)均摊复杂度。第四步：put时若map size已达capacity，先尝试惰性驱逐过期项，若仍超容，则驱逐tail.prev（最久未用节点），但需循环验证该节点是否已过期（因惰性检查可能漏掉），若过期则继续向前找第一个未过期节点驱逐。第五步：所有链表操作（moveToHead、unlink、addToHead）必须严格维护prev/next指针，避免空指针或环链表；HashMap的put/remove必须与链表操作原子配套。 - 深度知识讲解：考点一：LRU底层实现原理。标准LRU用HashMap+DoubleLinkedList实现O(1) get/put，核心在于双向链表支持O(1)任意节点删除和头插。本题叠加TTL后，不能仅依赖访问序，必须引入时间维度。关键矛盾是“逻辑过期”与“物理存储”的分离——节点在链表中存在，但业务上已失效，因此必须在每次访问时做时效校验。考点二：TTL实现模式对比。常见三种：1）被动过期（lazy expiration）——仅在get/put时检查，优点无额外开销，缺点过期key可能长期残留；2）主动过期（active expiration）——后台线程定期扫描，如Redis的定时器+惰性结合，但Java中需注意ScheduledThreadPool线程安全及扫描粒度；3）时间轮（TimingWheel）——适合大量短期TTL场景，但实现复杂，校园招聘中不作强求。本题考察对被动过期工程权衡的理解。考点三：时间精度与系统时钟依赖。expireTime必须用绝对时间戳（而非相对TTL），否则在节点长期驻留时，因系统时钟漂移或调整导致误判。且需注意System.currentTimeMillis()精度仅毫秒级，高并发下可能产生相同时间戳，但LRU顺序仍以访问先后为准，不影响正确性。考点四：线程安全性。题目未明确是否多线程，但生产环境必考虑。HashMap非线程安全，应替换为ConcurrentHashMap；双向链表操作需加锁或用CAS（如Java 8+可基于LinkedBlockingDeque思想，但本题手撕建议用ReentrantLock保护整个cache操作，或更轻量的读写锁）。若要求无锁，可引入CopyOnWriteArrayList（不适用，因需频繁修改），故通常面试接受synchronized或显式锁。考点五：内存泄漏防护。Node中若持有外部对象引用，需确保expire后及时置null；尤其value为大对象时，过期节点未unlink会导致GC无法回收。因此unlink操作必须同步清除Node内所有强引用。 - 代码示例（Java，含注释，线程安全简化版，使用synchronized）： ``` import java.util.*; public class TTLCache { private final int capacity; private final Map> cache; private final Node head; // most recently used private final Node tail; // least recently used private static class Node { K key; V value; long expireTime; // absolute timestamp in ms Node prev; Node next; Node(K key, V value, long expireTime) { this.key = key; this.value = value; this.expireTime = expireTime; } } public TTLCache(int capacity) { this.capacity = capacity; this.cache = new HashMap<>(); this.head = new Node<>(null, null, 0); this.tail = new Node<>(null, null, 0); head.next = tail; tail.prev = head; } public V get(K key) { synchronized (this) { Node node = cache.get(key); if (node == null || isExpired(node)) { return null; } // refresh access: move to head moveToHead(node); return node.value; } } public void put(K key, V value, long ttlMs) { synchronized (this) { long expireTime = System.currentTimeMillis() + ttlMs; Node node = cache.get(key); if (node != null) { // update existing node.value = value; node.expireTime = expireTime; moveToHead(node); } else { // insert new node = new Node<>(key, value, expireTime); cache.put(key, node); addToHead(node); // evict if over capacity if (cache.size() > capacity) { evict(); } } } } private boolean isExpired(Node node) { return System.currentTimeMillis() >= node.expireTime; } private void moveToHead(Node node) { unlink(node); addToHead(node); } private void addToHead(Node node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void unlink(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private void evict() { // lazy expire: check tail side up to 3 nodes int checked = 0; Node candidate = tail.prev; while (candidate != head && checked < 3) { if (isExpired(candidate)) { cache.remove(candidate.key); unlink(candidate); } else { break; } candidate = tail.prev; checked++; } // if still over capacity, evict the first non-expired from tail if (cache.size() > capacity) { candidate = tail.prev; while (candidate != head) { if (!isExpired(candidate)) { cache.remove(candidate.key); unlink(candidate); break; } candidate = candidate.prev; } } } } ```

12.30字节头条实习一面

全站热榜

创作者周榜