參考資料
skiplist與平衡樹、哈希表的比較
- skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做單個key的查找，不適宜做范圍查找。所謂范圍查找，指的是查找那些大小在指定的兩個值之間的所有節(jié)點。
- 在做范圍查找的時候，平衡樹比skiplist操作要復雜。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續(xù)尋找其它不超過大值的節(jié)點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現(xiàn)。而在skiplist上進行范圍查找就非常簡單，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實現(xiàn)。
- 平衡樹的插入和刪除操作可能引發(fā)子樹的調整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節(jié)點的指針，操作簡單又快速。
- 從內存占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節(jié)點包含2個指針（分別指向左右子樹），而skiplist每個節(jié)點包含的指針數(shù)目平均為1/(1-p)，具體取決于參數(shù)p的大小。如果像Redis里的實現(xiàn)一樣，取p=1/4，那么平均每個節(jié)點包含1.33個指針，比平衡樹更有優(yōu)勢。
- 查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值沖突概率的前提下，查找時間復雜度接近O(1)，性能更高一些。所以我們平常使用的各種Map或dictionary結構，大都是基于哈希表實現(xiàn)的。
從算法實現(xiàn)難度上來比較，skiplist比平衡樹要簡單得多。
