时间轮

java调度方法：

Timer，ScheduledExecutorService

时间复杂度 O(log(n)) 因为它们使用的 是 最小堆的对排序，每当有新任务的时候都需要堆堆进行插入， 堆排序插入的时间复杂度为 O(log(n))

Timer 的问题：

1. 如果任务执行时间过长，TimerTask会出现延迟执行的情况。比如，第一任务在1000ms执行了4000ms，第二个任务定时在2000ms开始执行。这里由于第一个任务要执行4000，所以第二个任务实际在5000ms开始执行。这是由于Timer是单线程，且顺序执行提交的任务
2. 如果执行任务抛出异常，Timer是不会执行会后面的任务的

ScheduledExecutorService 解决了这些问题

算法时间复杂度

实现方式	加入任务	取消任务	运行任务
基于排序链表	O(n)	O(1)	O(1)
基于最小堆	O(lgn)	O(1)	O(1)

有没有更高效的算法呢

有的 那就是 时间轮 调度算法

算法java实现 及使用demo

java实现

使用

TimeWheelService instance = TimeWheelService.instance;
        System.out.println("      start:"+new Date());
        instance.schedule(new Runnable() {
            @Override
            public void run() {
                System.out.println("task1 start:"+new Date());
//                throw new RuntimeException("aaa");
                try {
                    Thread.sleep(4000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        },1000);

        instance.schedule(new Runnable() {
            @Override
            public void run() {
                System.out.println("task2 start:"+new Date());
                try {
                    Thread.sleep(4000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        },2000);

算法作者

根据George Varghese 和 Tony Lauck 1996 年的论文 Hashed and Hierarchical Timing Wheels: data structures to efficiently implement a timer facility

算法原理：

问题:轮子过大

解决办法：多层时间轮

应用

linux 定时器，游戏buffer

算法对比

实现方式	加入任务	取消任务	运行任务
基于排序链表	O(n)	O(1)	O(1)
基于最小堆	O(lgn)	O(1)	O(1)
基于时间轮	O(1)	O(1)	O(1)

参考资料：

论文（英文）

参考博文（英文）

惊艳的时间轮定时器

Linux 下定时器的实现方式分析)