时间复杂度问题

[winyMu]

虽然 DelayQueue 中 offer（添加）和 poll（获取并删除）操作的时间复杂度为 O(log n)，但是相比定时任务的个数而言，bucket 的个数其实是非常小的（也就是 O(log n) 中的 n 很小），因此性能也是没有问题的。

看到作者博客中提到delayQueue中的元素个数应该只是跟bucket个数n有关,但是看到如下代码，在添加一个timer时，只要expiration不同，就会被添加到delayQueue中，所以这里会比较疑惑，这个时间复杂度是与“不同expiration的timer个数”有关？

if b.SetExpiration(virtualID * tw.tick) { tw.queue.Offer(b, b.Expiration()) }

[RussellLuo]

在添加一个timer时，只要expiration不同，就会被添加到delayQueue中

一个时间轮中的一个 bucket，同一时刻只会对应一个 expiration：

1. 如果 currentTime 没有变化，那么在此期间这个 expiration 也是不变的（假设为 Exp1），所有到期时间为 Exp1 的 tasks 都会落到这个 bucket；但对于这个 bucket 而言，只有在第一次调用 b.SetExpiration() 时会返回 true，因此它只会被添加到 delayQueue 一次。
2. 如果 currentTime 往前推移了，这个 expiration 会随之改变（假设为 Exp2），此后在 currentTime 不变期间的逻辑同上。

[winyMu]

get, 感谢指点！