跳表是允许在有序序列元素内快速搜索的数据结构。
通过维护子序列的链接层次结构可以快速搜索，每个连续的子序列跳过比前一个更少的元素。搜索开始于最小的子序列，直到找到两个连续的元素，一个更小，一个大于或等于所搜索的元素。通过链接层次结构，这两个元素链接到下一个最短子序列的元素，其中搜索继续，直到最后我们以完整的顺序搜索。可以概率地或确定性地选择跳过的元素
完整的跳表的图示
跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。
下面来研究一下跳表的核心思想：
先从链表开始，如果是一个简单的链表，那么我们知道在链表中查找一个元素I的话，需要将整个链表遍历一次。
如果是说链表是排序的，并且节点中还存储了指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。
使用跳过列表的应用程序和框架列表：
- MemSQL使用跳过列表作为其数据库技术的主要索引结构。
- Cyrus IMAP服务器提供了一个“skiplist”后端DB实现
- Lucene使用跳过列表以对数时间搜索增量式编码的发布列表。
- QMAP（最多Qt的4）模板类的Qt的，提供了一个字典。
- Redis是用于Posix系统的ANSI-C开源持久密钥/值存储，它在执行有序集时使用跳过列表。
- nessDB是一个非常快速的键值嵌入式数据库存储引擎（使用日志结构合并（LSM）树），它的memtable使用了跳过列表。
- skipdb是使用有序键/值对的开源数据库格式。
- Java 1.6 API中的ConcurrentSkipListSet和ConcurrentSkipListMap。
- 速度表是Tcl的一个快速键值数据存储区，它使用滑雪板进行索引和无锁共享内存。
- leveldb是一种用于在Google中编写的快速键值存储库，它提供从字符串键到字符串值的有序映射
- Con Kolivas的MuQSS [8] Linux内核计划程序使用跳过列表
- SkiMap使用跳过列表作为基础数据结构，为机器人映射系统构建更复杂的3D稀疏网格。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/179365.html原文链接：https://javaforall.net
