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

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

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

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

跳躍表介紹

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

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

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

簡(jiǎn)單的跳躍表如下圖所示：

跳躍表添加流程

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

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

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

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

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

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

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

添加流程

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

1. 第一個(gè)元素添加到最底層的有序鏈表中（最底層存儲(chǔ)了所有元素?cái)?shù)據(jù)）。
2. 第二個(gè)元素生成的隨機(jī)層數(shù)是 2，所以再增加 1 層，并將此元素存儲(chǔ)在第 1 層和最低層。
3. 第三個(gè)元素生成的隨機(jī)層數(shù)是 4，所以再增加 2 層，整個(gè)跳躍表變成了 4 層，將此元素保存到所有層中。
4. 第四個(gè)元素生成的隨機(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é)

跳躍表是由多個(gè)有序的鏈表組成的，最底層存儲(chǔ)了所有元素的數(shù)據(jù)，這樣存儲(chǔ)讓它的查詢效率更高，查詢復(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。