java 过期策略实现_java 从零开始手写 redis（五）过期策略的另一种实现思路

前言

前面实现了 redis 的几个基本特性，其中在 expire 过期原理时，提到了另外一种实现方式。

这里将其记录下来，可以拓展一下自己的思路。

以前的实现方式

核心思路

原来的实现方式见：

不足

以前的设计非常简单，符合最基本的思路，就是将过期的信息放在一个 map 中，然后去遍历清空。

为了避免单次操作时间过长，类似 redis，单次操作 100 个元素之后，直接返回。

不过定时任务之心时，其实存在两个不足：

(1)keys 的选择不够随机，可能会导致每次循环 100 个结束时，真正需要过期的没有被遍历到。

不过 map 的随机比较蠢，就是将 map 的 keys 全部转为集合，然后通过 random 返回。

转的过程就是一个时间复杂度为 O(n) 的遍历，所以一开始没有去实现。

还有一种方式，就是用空间换区时间，存储的时候，同时存储在 list 中，然后随机返回处理，这个后续优化。

(2)keys 的遍历可能大部分都是无效的。

我们每次都是根据 keys 从前往后遍历，但是没有关心对应的过期时间，所以导致很多无效遍历。

本文主要提供一种以过期时间为维度的实现方式，仅供参考，因为这种方式也存在缺陷。

基于时间的遍历

思路

我们每次 put 放入过期元素时，根据过期时间对元素进行排序，相同的过期时间的 Keys 放在一起。

优点：定时遍历的时候，如果时间不到当前时间，就可以直接返回了，大大降低无效遍历。

缺点：考虑到惰性删除问题，还是需要存储以删除信息作为 key 的 map 关系，这样内存基本翻倍。

基本属性定义

我们这里使用 TreeMap 帮助我们进行过期时间的排序&