赠源码和设计思路

• ect get(key) ：获取保存的数据，如果数据不存在或者已经过期，则返回null。
• void put(key,value,expireTime)：加入缓存。 无论此key是否已存在，均作为新key处理(移除旧key);如果空间不足，则移除已过期的key，如果没有，则移除最早加入缓存的key。过期时间未指定，则表示永不自动过期。
• 注意 ，我们允许key是有过期时间的，这一点与普通的FIFO有所区别，所以在设计此题时需要注意。(也是面试考察点，偏设计而非算法)

普通的FIFO或许大家都能很简单的写出，增加了过期时间的考虑之后，在设计时需要多考虑。如下示例，为暂未考虑并发环境的FIFO设计。

设计思路

1)用普通的hashMap保存缓存数据。

2)需要额外的map用来保存key的过期特性，例子中使用了TreeMap，将“剩余存活时间”作为key，利用TreeMap的排序特性。

 

用，是目前最常用的缓存算法和设计方案之一，其移除策略为“当缓存(页)满时，优先移除最近最久未使用的数据”，优点是易于设计和使用，适用场景广泛。算法可以参考leetcode 146 (LRU Cache)。

操作

• Object get(key)：从cache中获取key对应的数据，如果此key已过期，移除此key，并则返回null。
• void put(key,value,expired)：设置k-v，如果容量不足，则根据LRU置换算法移除“最久未被使用的key”。 需要注意，根据LRU优先移除已过期的keys，如果没有，则根据LRU移除未过期的key。如果未设定过期时间，则认为永不自动过期。
• 这里的设计关键是过期时间特性，这与常规的LRU有所不同。

设计思路

• LRU的基础算法，需要了解;每次put、get时需要更新key对应的访问时间，我们需要一个数据结构能够保存key最近的访问时间且能够排序。
• 既然包含过期时间特性，那么带有过期时间的key需要额外的数据结构保存。
• 暂时不考虑并发操作;尽量兼顾空间复杂度和时间复杂度。
• 此题仍然偏向于设计题，而非纯

 

（编辑：阜阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!