一、跳表的优点
对于一个需要频繁删除的线性有序结构，如何使插入/删除的速度提升？
- 对于单向链表，只能从头到尾遍历，时间复杂度为O(n)
- 对于数组，删除插入复杂度太高O(n)，还会涉及数组的扩容操作
- 平衡二叉树查询速度很快，但是需要平衡的操作开销很大
- 红黑树的话，性能差不多，但是如果需要多进程同时访问修改的话，红黑树有个平衡的过程，争锁代价也比较大
- 跳表的线程安全也是通过cas锁实现的，跳表的构建相对简单，同时支持范围查找
缺点：
相对于红黑树，空间消耗增加
二、增删改查
- 加入多层索引，加快查询速度，理想的跳表上层节点数量为下层的一半，相当于二分，复杂度为O(logn)
- 插入与删除都可由查找和更新两部分构成。查找的时间复杂度为O(logn)，更新部分的复杂度与跳跃表的高度成正比，所以总的时间复杂度为O(logn)
网友评论