一个定时器的实现

程序使用的多数定时器都是操作超时定时器，只有少量定时器是周期任务定时器。这些超时定时器的特点是，很大的几率上的会在没有超时前就被重置了。所以有以下的讨论。

这里的设计是针对超时定时器而优化，假定超时定时器有以下特点:

1、需要常数时间的插入,即说能快速插入。

2、需要常数时间的删除，即能快速删除。

3、精度不需要太高，比如1秒定时，可以在两秒后才激发。

4、定时器在很大的几率上，没超时前就被重置/删除。

总结起来特点就是

StartTimer StopTimer PerTickBookkeeping

O(1)            O(1)           O(?)

实现方式:

1、创建一个32个节点，每个节点分别代表1s, 2s, 4s, ..., 2^32s的定时器(可见最小精度是1s)。

2、所有的定时器按照最接近的2次幂加入到对应的节点中而形成一个双向链表，比如60秒的定时器加入到64秒的节点中去。

3、因为是双向链表，可见删除定时器是一件很简单的事情。

4、按照前面的3点看，知道60秒的定时器的效果跟64秒的差别不大，这就是所谓的精度不高。

5、如果准确的60秒的定时器，方式1是使用1秒定时器，方式2是把60秒拆分为32+16+8+4即可，就是先将它加入32秒的定时器中，然后超时之后再加入到16秒的定时器中，然后加入到8秒的定时器中。

结论，虽然60秒的定时器需要做额外的出来，所以在超时处理上比较费时间，不过前面说到，超时定时器在没有超时之前就被重置了，所以通常不会耗费很大的CPU时间。

总的来说，这个实现跟linux下的时间轮定时器的实现很像,并且区别也不大。一个区别是，时间轮是按照超时时间来处理，而这里是按照定时器的周期时间来处理。所以每次都只需要将节点加入到对于那个的链表未就可以了。