今天分享的這道題來自于蔚來的真實(shí)面試題。

面試 Java 不可能不問 Redis，問到 Redis 不可能不問 Redis 的常用數(shù)據(jù)類型，問到 Redis 的常用數(shù)據(jù)類型，不可能不問跳躍表，當(dāng)問到跳躍表經(jīng)常會被問到跳躍表的查詢和添加流程，所以接下來我們一起來看這道題的答案吧。

Redis 有序集合ZSet 是由 ziplist (壓縮列表) 或 skiplist (跳躍表) 組成的。

1. 壓縮列表 ziplist 本質(zhì)上就是一個字節(jié)數(shù)組，是 Redis 為了節(jié)約內(nèi)存而設(shè)計的一種線性數(shù)據(jù)結(jié)構(gòu)，可以包含多個元素，每個元素可以是一個字節(jié)數(shù)組或一個整數(shù)。
2. 跳躍表 skiplist 是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點(diǎn)中維持多個指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。跳躍表支持平均 O(logN)、最壞 O(N) 復(fù)雜度的節(jié)點(diǎn)查找，還可以通過順序性操作來批量處理節(jié)點(diǎn)。

跳躍表介紹

跳躍表 Skip List，也稱之為跳表，是一種數(shù)據(jù)結(jié)構(gòu)，用于在有序元素的集合中進(jìn)行高效的查找操作。它通過添加多層鏈表的方式，提供了一種以空間換時間的方式來加速查找。

跳躍表由一個帶有多層節(jié)點(diǎn)的鏈表組成，每一層都是原始鏈表的一個子集。最底層是一個完整的有序鏈表，包含所有元素。每個更高層級都是下層級的子集，通過添加額外的指針來跳過一些元素。這些額外的指針稱為“跳躍指針”，它們允許快速訪問更遠(yuǎn)的節(jié)點(diǎn)，從而減少了查找所需的比較次數(shù)。

跳躍表的平均查找時間復(fù)雜度為 O(log n)，其中 n 是元素的數(shù)量。這使得它比普通的有序鏈表具有更快的查找性能，并且與平衡二叉搜索樹（如紅黑樹）相比，實(shí)現(xiàn)起來更為簡單。

簡單的跳躍表如下圖所示：

跳躍表添加流程

前置知識：節(jié)點(diǎn)隨機(jī)層數(shù)

在開始講跳躍表的添加流程之前，必須先搞懂一個概念：節(jié)點(diǎn)的隨機(jī)層數(shù)。所謂的隨機(jī)層數(shù)指的是每次添加節(jié)點(diǎn)之前，會先生成當(dāng)前節(jié)點(diǎn)的隨機(jī)層數(shù)，根據(jù)生成的隨機(jī)層數(shù)來決定將當(dāng)前節(jié)點(diǎn)存在幾層鏈表中。

為什么要這樣設(shè)計呢？

這樣設(shè)計的目的是為了保證 Redis 的執(zhí)行效率。

為什么要生成隨機(jī)層數(shù)，而不是制定一個固定的規(guī)則，比如上層節(jié)點(diǎn)是下層跨越兩個節(jié)點(diǎn)的鏈表組成，如下圖所示：

如果制定了規(guī)則，那么就需要在添加或刪除時，為了滿足其規(guī)則，做額外的處理，比如添加了一個新節(jié)點(diǎn)，如下圖所示：

這樣就不滿足制定的上層節(jié)點(diǎn)跨越下層兩個節(jié)點(diǎn)的規(guī)則了，就需要額外的調(diào)整上層中的所有節(jié)點(diǎn)，這樣程序的效率就降低了，所以使用隨機(jī)層數(shù)，不強(qiáng)制制定規(guī)則，這樣就不需要進(jìn)行額外的操作，從而也就不會占用服務(wù)執(zhí)行的時間了。

添加流程

Redis 中跳躍表的添加流程如下圖所示：

1. 第一個元素添加到最底層的有序鏈表中（最底層存儲了所有元素數(shù)據(jù)）。
2. 第二個元素生成的隨機(jī)層數(shù)是 2，所以再增加 1 層，并將此元素存儲在第 1 層和最低層。
3. 第三個元素生成的隨機(jī)層數(shù)是 4，所以再增加 2 層，整個跳躍表變成了 4 層，將此元素保存到所有層中。
4. 第四個元素生成的隨機(jī)層數(shù)是 1，所以把它按順序保存到最后一層中即可。

其他新增節(jié)點(diǎn)以此類推。

隨機(jī)層數(shù)源碼分析

隨機(jī)層數(shù)的源碼在 t_zset.c/zslRandomLevel(void) 中，如下所示：

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

從源碼可知，隨機(jī)層數(shù)有 50% 的概率被分配到 Level 1，25% 的概率被分配到 Level 2，12.5% 的概率被分配到 Level 3，以此類推。

Redis 跳躍表默認(rèn)允許最大的層數(shù)是 32，此值在 ZSKIPLIST_MAXLEVEL 源碼中被定義。

小結(jié)

跳躍表是由多個有序的鏈表組成的，最底層存儲了所有元素的數(shù)據(jù)，這樣存儲讓它的查詢效率更高，查詢復(fù)雜度從 O(n) 變?yōu)榱?O(log n)。跳躍表的添加流程是根據(jù)節(jié)點(diǎn)生成的隨機(jī)層數(shù)，將它插入到最底層節(jié)點(diǎn)和上層的 N-1 層節(jié)點(diǎn)中，描述添加流程的關(guān)鍵就是理解隨機(jī)層數(shù)以及其背后的原理。

參考 & 鳴謝

https://segmentfault.com/a/1190000022028505。