很多程序都需要處理一系列定時事件，一個Timer程序就是實現(xiàn)定時事件集合的管理。
每個timer事件項一般包括超時值(delay), 標(biāo)識(key)和回調(diào)函數(shù)，Timer程序的作用就是實現(xiàn)插入，刪除，更新和調(diào)用。
方法1. 鏈表
最簡單的實現(xiàn)是有序鏈表。list_head保存到當(dāng)前時間的剩余時間remain_time，后一節(jié)點保存與前一節(jié)點的超時時間的差(而不是到當(dāng)前時間的差)。
更新：每次tick update時，只需要更新鏈表頭節(jié)點remain_time，如果remain_time <= 0, 調(diào)用函數(shù)，刪除該頭節(jié)點，然后更新后一個節(jié)點的remain_time,如此類推直到頭結(jié)點remain_time > 0或鏈表為空. O(1)
插入：相當(dāng)于插入排序。有序插入到適當(dāng)位置，更新后一個節(jié)點的remain_time.
刪除：遍歷鏈表搜索，刪除節(jié)點，更新后一個節(jié)點的remain_time.
例子：live555流媒體服務(wù)器
方法2. 最小堆(優(yōu)先隊列)
方法與鏈表類似，插入/刪除效率從O(n)變?yōu)镺(lgN)
libevent中有min-heap實現(xiàn)一個優(yōu)先隊列，根節(jié)點是最先觸發(fā)的超時時間, 與方法1一樣，只需更新根節(jié)點。根節(jié)點超時后，調(diào)整堆即可
方法3. Hash或分級
根據(jù)超時值的范圍(比如CPU的流逝ticks)進行hash，hash后每個bucket實現(xiàn)方法1所示的鏈表. 較方法1減少了搜索次數(shù)
例子：MudOS定時器
方法4. 分級hash
這是linux內(nèi)核timer的實現(xiàn)方法，值得參考。見文獻[1]
方法：假設(shè)定時值以tick為單位，每tick更新timer一次。
定時值范圍為0 ~ 2^32個tick(32個bit), 則把他分成4級，每級做一個hash, 每個則有256個bucket (剛好8bit)
000000000 00000000 00000000 00000000
--------- -------- -------- --------
A B C D
插入：算出 tick_trig = delay + 當(dāng)前tick， mask = tick_trig & 0xFF000000，
如果mask不等于0，在A hash表插入timer項, 否則進入下一級，mask = tick_trig & 0x00FF0000, 插入B hash表，如此類推。
更新：每次tick++, 先檢查D hash表(最低8位的與操作)有無timer項，如果有，執(zhí)行函數(shù)并刪除。
如果tick滿255進位， 則檢查C hash表中對應(yīng)位置有否timer項，如果有，重新插入(此處的timer項必定會插入D hash表中)，如此類推
這樣，插入，更新，刪除都做到O(1)了
疑惑：這個方法用于內(nèi)核級程序。對于用戶級程序，每次update的間隔不恒定（即每次tick不一定是+1），這時需要掃描tick之前的幾個bucket了
參考文獻
[1] George Varghese
, Tony Lauck. Hashed and
Hierarchical Timing Wheels:
Efficient Data Structures for Implementing a Timer Facility
(1996)
[2] libevent 源碼
[3] <understanding linux kernel 3rd ed>
[4] MudOS 源碼