赞
踩
关于跳跃表其实在 JUC 里面有一个并发容器就是利用跳跃表来实现的:ConcurrentSkipListMap。jdk的并发包中还有许多数据结构,最常用的又链表,哈希表等。
先介绍一下跳表的相关特性:
这些特性我们看到跳表的结构就很容易理解了:结构如下图:
最底层的是原链表,然后一级索引,二级索引,二级索引为什么选择1这个结点作为关键结点呢,是通过概率产生的,就是抛硬币,正反的概率都是百分之50,虽然这个图是均匀间隔的,但是实际上每一个节点都有可能成为关键节点。二级索引的关键节点也是这么产生的。
SkipListd的查找算法较为简单,对于上面我们我们要查找元素3,其过程如下:
SkipList的插入操作主要包括:
假定我们要插入的元素为5,其过程如下:
1.比较1,大于,往后找(6),小于,到下一层
2.比较3,大于,往后找(6),小于,到下一层,也就是原链表,确定位置为4后6前,插入到原链表
3.然后决定在一级索引上是不是关键节点,是,就继续抛,到二级索引,如果还是就继续抛,申请新的层
4.如果抛出来否,就不继续抛了
删除节点和插入节点思路基本一致:找到节点,删除节点,调整指针。
相比较红黑树来讲作者觉得这个跳表的实现更加简单,后期维护也更加方便:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。