跳表的原理和时间复杂度，为什么还需要字典结构配合？

## 1. 跳表的原理 跳表（SkipList）是 **一种有序链表的多级索引结构**，通过增加多层“索引”来加快查找速度。 * **最底层**：完整的有序链表（包含所有元素）。 * **上层索引**：抽取部分节点作为“快捷通道”，减少查找步数。 * **查找过程**：从最高层索引开始，能向右就向右，不能向右就向下，直到找到目标或最接近的位置。 举例（每层越上节点越少）： ``` Level 3: 1 --------- 9 Level 2: 1 --- 5 --- 9 Level 1: 1 3 5 7 9 ``` 找元素 7 的过程： * 从 Level 3 的 1 → 9（超了，往下） * Level 2 的 1 → 5 → 9（超了，往下） * Level 1 的 5 → 7（找到） ## 2. 时间复杂度 跳表的平均性能和 **平衡二叉树（AVL/红黑树）** 类似： | 操作 | 平均复杂度 | 最坏复杂度 | | ----- | ------------ | ----- | | 查找 | O(log N) | O(N) | | 插入/删除 | O(log N) | O(N) | | 范围查询 | O(log N + m) | O(N) | > m 为返回的结果数量。 > 在随机化层数 + 合理概率（Redis 用 1/4）下，O(N) 出现概率极低。 ## 3. 为什么 ZSet 还需要 **字典结构（hash）** 配合 在 Redis 的有序集合 ZSet 里，底层是 **跳表（skiplist） + 字典（dict）** 组合： * **跳表**： * 按分值（score）排序。 * 支持范围查询（如 `ZRANGEBYSCORE`）。 * 插入、删除、按排名查询效率高。 * **字典**： * key：成员（member） * value：分值（score） * **O(1) 时间** 根据成员查分值（比如 `ZSCORE`、`ZREM` 先定位成员）。 * 跳表按 score 排序，没法快速通过成员查 score，所以需要字典辅助。 **为什么不只用跳表？** * 如果只用跳表，查一个成员的分值需要 O(log N)，而有了字典就是 O(1)。 * 删除成员时，需要先 O(1) 定位到 score，再 O(log N) 从跳表删除，整体性能更好。 ## 4. 总结一句话 跳表保证了 **有序存储 + 范围查询的高效性**，字典保证了 **按成员快速定位**。 Redis 的 ZSet 用 **双结构冗余存储**，是空间换时间的设计，既能 O(1) 找成员，又能 O(log N) 做有序操作。