共计 3847 个字符，预计需要花费 10 分钟才能阅读完成。
简介
定时器是一种在理论的利用中十分常见和无效的一种工具，其原理就是把要执行的工作依照执行工夫的程序进行排序，而后在特定的工夫进行执行。JAVA 提供了 java.util.Timer 和 java.util.concurrent.ScheduledThreadPoolExecutor 等多种 Timer 工具，然而这些工具在执行效率下面还是有些缺点，于是 netty 提供了 HashedWheelTimer, 一个优化的 Timer 类。
一起来看看 netty 的 Timer 有何不同吧。
java.util.Timer
Timer 是 JAVA 在 1.3 中引入的。所有的工作都存储在它外面的 TaskQueue 中：
private final TaskQueue queue = new TaskQueue();TaskQueue 的底层是一个 TimerTask 的数组，用于存储要执行的工作。
private TimerTask[] queue = new TimerTask[128];看起来 TimerTask 只是一个数组，然而 Timer 将这个 queue 做成了一个均衡二叉堆。
当增加一个 TimerTask 的时候，会插入到 Queue 的最初面，而后调用 fixup 办法进行再均衡：
void add(TimerTask task) {
// Grow backing store if necessary
if (size + 1 == queue.length)
queue = Arrays.copyOf(queue, 2*queue.length);
queue[++size] = task;
fixUp(size);
}当从 heap 中移出运行的工作时候，会调用 fixDown 办法进行再均衡：
void removeMin() {queue[1] = queue[size];
queue[size--] = null; // Drop extra reference to prevent memory leak
fixDown(1);
}fixup 的原理就是将以后的节点和它的父节点进行比拟，如果小于父节点就和父节点进行交互，而后遍历进行这个过程：
private void fixUp(int k) {while (k > 1) {
int j = k >> 1;
if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
break;
TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
k = j;
}
}fixDown 的原理是比拟以后节点和它的子节点，如果以后节点大于子节点，则将其降级：
private void fixDown(int k) {
int j;
while ((j = k << 1) <= size && j > 0) {
if (j < size &&
queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)
j++; // j indexes smallest kid
if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
break;
TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
k = j;
}
}二叉均衡堆的算法这里不做具体的介绍。大家能够自行查找相干的文章。
java.util.concurrent.ScheduledThreadPoolExecutor
尽管 Timer 曾经很好用了，并且是线程平安的，然而对于 Timer 来说，想要提交工作的话须要创立一个 TimerTask 类，用来封装具体的工作，不是很通用。
所以 JDK 在 5.0 中引入了一个更加通用的 ScheduledThreadPoolExecutor，这是一个线程池应用多线程来执行具体的工作。当线程池中的线程个数等于 1 的时候，ScheduledThreadPoolExecutor 就等同于 Timer。
ScheduledThreadPoolExecutor 中进行工作保留的是一个 DelayedWorkQueue。
DelayedWorkQueue 和 DelayQueue,PriorityQueue 一样都是一个基于堆的数据结构。
因为堆须要一直的进行 siftUp 和 siftDown 再均衡操作，所以它的工夫复杂度是 O(log n)。
上面是 DelayedWorkQueue 的 shiftUp 和 siftDown 的实现代码：
private void siftUp(int k, RunnableScheduledFuture<?> key) {while (k > 0) {int parent = (k - 1) >>> 1;
RunnableScheduledFuture<?> e = queue[parent];
if (key.compareTo(e) >= 0)
break;
queue[k] = e;
setIndex(e, k);
k = parent;
}
queue[k] = key;
setIndex(key, k);
}
private void siftDown(int k, RunnableScheduledFuture<?> key) {
int half = size >>> 1;
while (k < half) {int child = (k << 1) + 1;
RunnableScheduledFuture<?> c = queue[child];
int right = child + 1;
if (right < size && c.compareTo(queue[right]) > 0)
c = queue[child = right];
if (key.compareTo(c) <= 0)
break;
queue[k] = c;
setIndex(c, k);
k = child;
}
queue[k] = key;
setIndex(key, k);
}HashedWheelTimer
因为 Timer 和 ScheduledThreadPoolExecutor 底层都是基于堆构造的。尽管 ScheduledThreadPoolExecutor 对 Timer 进行了改良，然而他们两个的效率是差不多的。
那么有没有更加高效的办法呢？比方 O(1) 是不是能够达到呢？
咱们晓得 Hash 能够实现高效的 O(1) 查找，设想一下如果咱们有一个有限刻度的钟表，而后把要执行的工作依照间隔时间长短的程序调配到这些刻度中，每当钟表挪动一个刻度，即能够执行这个刻度中对应的工作，如下图所示：
这种算法叫做 Simple Timing Wheel 算法。
然而这种算法是实践上的算法，因为不可能为所有的距离长度都调配对应的刻度。这样会消耗大量的有效内存空间。
所以咱们能够做个折中计划，将间隔时间的长度先用 hash 进行解决。这样就能够缩短间隔时间的基数，如下图所示：
这个例子中，咱们抉择 8 作为基数，间隔时间除以 8，余数作为 hash 的地位，商作为节点的值。
每次遍历轮询的时候，将节点的值减一。当节点的值为 0 的时候，就示意该节点能够取出执行了。
这种算法就叫做 HashedWheelTimer。
netty 提供了这种算法的实现：
public class HashedWheelTimer implements Timer HashedWheelTimer 应用 HashedWheelBucket 数组来存储具体的 TimerTask:
private final HashedWheelBucket[] wheel;首先来看下创立 wheel 的办法：
private static HashedWheelBucket[] createWheel(int ticksPerWheel) {
//ticksPerWheel may not be greater than 2^30
checkInRange(ticksPerWheel, 1, 1073741824, "ticksPerWheel");
ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel);
HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel];
for (int i = 0; i < wheel.length; i ++) {wheel[i] = new HashedWheelBucket();}
return wheel;
}咱们能够自定义 wheel 中 ticks 的大小，然而 ticksPerWheel 不能超过 2^30。
而后将 ticksPerWheel 的数值进行调整，到 2 的整数倍。
而后创立 ticksPerWheel 个元素的 HashedWheelBucket 数组。
这里要留神，尽管整体的 wheel 是一个 hash 构造，然而 wheel 中的每个元素，也就是 HashedWheelBucket 是一个链式构造。
HashedWheelBucket 中的每个元素都是一个 HashedWheelTimeout. HashedWheelTimeout 中有一个 remainingRounds 属性用来记录这个 Timeout 元素还会在 Bucket 中保留多久。
long remainingRounds;总结
netty 中的 HashedWheelTimer 能够实现更高效的 Timer 性能，大家用起来吧。
更多内容请参考 http://www.flydean.com/50-netty-hashed-wheel-timer/
最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！
欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！
