时间轮算法

时间轮算法应用于定时任务之中。比如设定一个任务的到期时间，如何可以在到期时间后出发。并且插入，删除，触发一个到期任务的时间的复杂度都控制在一个较低的水平？时间轮算法就是为了解决这个问题而诞生。

简单时间轮算法

存在一个循环数组，数组中有一个指针以固定速度前进，到达尾部时再次回到位置0重新开始。这个固定的前进速度就是这个时间轮的精度，也就是该时间轮最小能够表达的时间间隔。数组的每一位都是一个list，存储着该这个节点上的触发动作。那么当指针到达这个位置时，就触发这个位置上的list中存储的所有的触发动作。

• 插入新的触发动作和时间
  将当前时间与时间轮的启动时间相减得到time1，将time1除以时间轮的间隔得到count，将count取模时间轮数组长度，得到插入位置。这个时间复杂度是o(1)。插入的时候返回一个timer用于指向这个任务和插入位置
• 删除某一个触发动作
  第一步返回的timer中包含了插入位置，因此可以直接使用这个插入位置寻找到对应的数据进行删除。显然时间复杂度也是o(1)
• 重置某一个触发动作的时间
  实际上该动作是先删除后加入的

简单的时间轮实现起来不复杂，效果也非常的好。插入和删除都是o（1）的时间。应该来说比最小堆实现的时间排序要好一些。

简单时间轮的问题

简单时间轮也有一个问题，就是单一数组所能表示的范围比较小。比如在时间精度为1秒的情况下，如果要表达一天的时间间隔，需要60*60*24的长度。这个对于内存的浪费是很严重的。为了解决这样的问题，可以采用多级时间轮的解决方案。
举个例子，可以定义3个时间轮。轮1有60个，代表60s；轮2有60个，代表60分钟，轮3有24格，代表24小时。当轮1转动1圈回到原点时，轮2转动1格，轮3也依次类推。这样就可以用60+60+24=144的长度来表达24小时的间隔了。对比原来，节省了非常多的空间。

多级时间轮

多级时间轮通过为每一级别的时间轮使用不同的时间权重来达到解决空间浪费的问题。而每一级的时间轮，所对应的超时时间级别都不同。仍然以时分秒时间轮为例子。秒轮中存储着超时时间在1-60s内的触发动作，分轮存储着60-60*60秒内的触发动作，时轮存储着60*60-60*60*24秒内的触发动作。多级时间轮中插入一个新的触发时间和动作的步骤是

• 首先判断触发时间在哪一级轮子的时间间隔中。然后除以上一级轮子的间隔时间上限得到一个位置数字，在该级轮子中以该位置数字为坐标（或者是坐标-1，取决于首坐标是否是0），插入该触发动作

多级时间轮中如果一个轮子走完了一圈，回归初始位置前，需要将下一级轮子的当前指针位置的触发器全部取出，并且再次执行插入动作。由于时间轮的不同的时间权重，下一级轮子的触发动作再次插入时都是插入在本级轮子中。完成这个动作后，将下级轮子的指针前进1格。