跳表的底层结构

程序员朱永胜2024-10-212024-11-12

有的时候博客内容会有变动，首发博客是最新的，其他博客地址可能会未同步, 认准 https://blog.zysicyj.top

全网最细面试题手册，支持艾宾浩斯记忆法。这是一份最全面、最详细、最高质量的 java 面试题，不建议你死记硬背，只要每天复习一遍，有个大概印象就行了。https://store.amazingmemo.com/chapterDetail/1685324709017001`

跳表（Skip List）是一种概率性的数据结构，它通过在标准的有序链表上增加多级索引来提高搜索效率。跳表的底层结构和操作原理可以通过以下几个方面来理解：

跳表的基础是一个标准的单向链表。在这个链表中，元素是按照顺序排列的，每个元素包含两个部分：

在基础链表的顶部，跳表增加了多级索引（也称为 “ 层 “ 或 “ 级 “），以便快速跳过那些不需要比较的元素。每一级索引都是一个链表，包含了下一级链表中的部分元素。索引层的元素也包含两个部分：

跳表包含一个特殊的头节点，它在所有级别的链表中都存在。头节点不包含任何实际的数据值，它的目的是作为搜索、插入和删除操作的起点。

与头节点类似，跳表通常也会有一个尾节点，表示链表的结束。尾节点在所有级别的链表中都存在，并且通常会包含一个特殊值，如 null 或无穷大，以便于在搜索时作为边界条件。

跳表中元素在各个索引层中出现的频率是通过随机化过程决定的。通常，一个元素在第一级索引中出现的概率是 1/2，在第二级索引中出现的概率是 1/4，以此类推。这种随机化确保了跳表的搜索、插入和删除操作的平均时间复杂度为 O(log n)。

要在跳表中搜索一个元素，算法从最高级的索引开始，沿着链表向前移动，直到找到一个大于或等于目标值的元素。然后，算法移动到下一级索引，并重复这个过程，直到到达基础链表。这种方式允许算法快速跳过那些不需要比较的元素，从而加快搜索速度。

插入一个新元素时，首先在基础链表中找到正确的位置，然后通过随机化过程决定新元素应该被添加到哪些索引层中。新元素在每一级索引中的插入都遵循链表的插入规则。

删除操作与插入操作类似，首先在基础链表中找到要删除的元素，然后从所有包含该元素的索引层中将其移除。

跳表的底层结构虽然简单，但它的设计巧妙地利用了随机化和多级索引来提高效率，使得在平均情况下，跳表的搜索、插入和删除操作都能达到对数级的时间复杂度。