跳錶是什麼

跳躍表

跳錶，全稱跳躍表，是一種隨機化的數據結構，它實質上是一種可以進行二分查找的有序鏈表。

跳錶在原有有序鏈表的基礎上增加了多級索引，通過這些索引實現快速查詢。這種數據結構不僅提高了搜索性能，同時也優化了插入和刪除操作的效率。跳錶通過維護多層次的鏈表來實現快速查詢效果，與下層鏈表相比，每一層的鏈表元素數量更少，從而允許在有序序列中進行快速查找、插入和刪除操作。其平均時間複雜度爲O(logn)，優於數組的O(n)複雜度。