java - 使用哪种数据结构来存储条目及其时间戳(按排序顺序)

Question

我必须实现一种场景，其中我需要存储大量条目及其时间戳，例如“AnyString”和“Timestamp”。现在，我必须定期检查计时器即将过期的条目(假设时间戳超过一小时的条目将过期)。因此，为了让它们保持活力，我必须过滤掉计时器将在一段时间内到期的条目，并执行一些操作并重新初始化它们的时间戳。它是多线程环境。

为了做到这一点，我正在寻找有效的数据结构，以便当我扫描 map 以找出谁的计时器即将到期时，我不必遍历整个 map 。每次都遍历完整的map来过滤掉即将过期的条目会对性能产生巨大的影响。

我考虑使用“ConcurrentSkipListMap”，其中比较器可用于按时间戳的排序顺序存储条目。这样每次我扫描 map 直到网络的时间戳大于所需的值。

有没有更好的方法来完成这个任务？谢谢。

Answer 1

简短:我建议您查看http://netty.io/4.0/api/io/netty/util/HashedWheelTimer.html - 它会做你想要的。

长:

有一种特殊的结构用于此目的:计时器轮。 Here

简而言之，这个想法如下:你有一个大的循环数组，这个数组的每个元素都是你的对象的列表。此外，您还有一个指针，它指向数组的某个元素，并且在每个刻度上递增。每个元素都有关联的时间范围，这些时间范围是以特殊方式选择的。例如。整个轮转时间为1s，数组有1000个元素，则:第 0 个元素是事件列表，应在 x.000 - x.001s 处触发，第一个元素是事件列表，应在 x.001 - x.002s 等处触发。

当您添加新事件时，您应该收到提醒 time_when_the_event_should_fire/wheel_period，这样就可以确定应该将该事件添加到数组的哪个元素。

指针将在每个刻度(1 毫秒)上增加 1，元素是有序列表 - 因此在每个刻度上，您获取元素(列表)，迭代列表项，并且如果事件应在该刻度处触发，你触发它，否则停止迭代。

因此，所有操作的复杂度为 O(1)，添加新事件的复杂度为 O(n/wheel_size)。