前言

此次 B 站服務(wù)端開(kāi)發(fā)面試之旅可謂驚險(xiǎn)，不過(guò)通過(guò)對(duì)大部分面試題套路的掌握，不出意外還是拿下了，下面我們來(lái)看看這些騷題是不是常見(jiàn)的不能再常見(jiàn)的了。

這些面試題看了就能面上？當(dāng)然不是，只是通過(guò)這些題讓自己知道所欠缺的是什么，以及可以去看看哪些資料。

正文

1. 操作系統(tǒng)相關(guān)

• 自旋鎖和一般鎖的區(qū)別是什么？為什么要使用自旋鎖？

當(dāng)一個(gè)線程在獲取鎖的時(shí)候，如果這個(gè)鎖已經(jīng)被其他線程獲取，那么這個(gè)線程不會(huì)破門(mén)而入，而是循環(huán)等待，但是嗷嗷待哺，需要不斷地嗷嗷叫判斷鎖是否被成功獲取，直到獲取到鎖才會(huì)退出循環(huán)。

自旋鎖通常會(huì)出現(xiàn)哪些問(wèn)題?

如果某個(gè)線程拿著鎖死不放手，其他線程沒(méi)法拿到這把鎖，只好等待獲取鎖的線程進(jìn)入循環(huán)等待的狀態(tài)，等待不是睡覺(jué)，還是會(huì)消耗CPU，等待久了就會(huì)導(dǎo)致CPU的使用率太高。

那么自旋鎖和其他鎖到底有啥不同？

從線程狀態(tài)來(lái)看，自旋鎖的狀態(tài)是運(yùn)行-運(yùn)行-運(yùn)行。而非自旋鎖的狀態(tài)是運(yùn)行---阻塞---運(yùn)行，所以自旋鎖會(huì)更高效。

不管是什么鎖，都是為了實(shí)現(xiàn)保護(hù)共享資源而提出的一種鎖機(jī)制，都是為了對(duì)某項(xiàng)資源的互斥使用。對(duì)于互斥鎖而言，如果資源已經(jīng)被占用，那么資源的申請(qǐng)者只會(huì)進(jìn)入睡眠的狀態(tài)。而自旋鎖不會(huì)引起調(diào)用者睡眠，而是一直循環(huán)在那里查看該自旋鎖的保持著是否已經(jīng)釋放了鎖。

那么在Java中如何去實(shí)現(xiàn)一個(gè)自旋鎖

public?class?SpinLock?{
????private?AtomicReference?cas?=?new?AtomicReference();
????public?void?lock()?{
????????Thread?current?=?Thread.currentThread();
????????//?利用CAS
????????while?(!cas.compareAndSet(null,?current))?{
????????????//?DO?
????????}
????}
????public?void?unlock()?{
????????Thread?current?=?Thread.currentThread();
????????cas.compareAndSet(current,?null);
????}
}

上段代碼中，方法lock利用的CAS，當(dāng)線程A獲取鎖的時(shí)候，成功獲取不會(huì)進(jìn)入while循環(huán)。如果此時(shí)線程A沒(méi)有釋放鎖，當(dāng)線程B來(lái)獲取鎖的時(shí)候，由于不滿(mǎn)足CAS，就會(huì)進(jìn)入while循環(huán)，不斷判斷是否滿(mǎn)足CAS，直到線程A調(diào)用unlock釋放。

自旋鎖有哪些優(yōu)點(diǎn)？

1. 因?yàn)檫\(yùn)行在用戶(hù)態(tài)，沒(méi)有上下文的線程狀態(tài)切換，線程一直處于active，減少了不必要的上下文切換，從而執(zhí)行速度較快

2. 因?yàn)榉亲孕i在沒(méi)有獲取鎖的情況下會(huì)進(jìn)入阻塞狀態(tài)，從而進(jìn)入內(nèi)核態(tài)，此時(shí)就需要線程的上下文切換，因?yàn)樽枞筮M(jìn)入內(nèi)核調(diào)度狀態(tài)，會(huì)導(dǎo)致用戶(hù)態(tài)和內(nèi)核態(tài)之間的切換，影響鎖的性能。

• 了解哪些I/O模型?select是阻塞IO嗎？

首先將IO模型給安排一遍，然后把自己很熟悉的IO模型詳細(xì)說(shuō)一波并介紹出應(yīng)用場(chǎng)景，這個(gè)裝的X就算比較完美，具體的非常詳細(xì)的在下一篇文章，這里簡(jiǎn)要說(shuō)一波。這一部分在上一篇詳細(xì)闡述過(guò)

阻塞IO

我們知道在調(diào)用某個(gè)函數(shù)的時(shí)候無(wú)非就是兩種情況，要么馬上返回，然后根據(jù)返回值進(jìn)行接下來(lái)的業(yè)務(wù)處理。

當(dāng)在使用阻塞IO的時(shí)候，應(yīng)用程序會(huì)被無(wú)情的掛起，等待內(nèi)核完成操作，因?yàn)榇藭r(shí)的內(nèi)核可能將CPU時(shí)間切換到了其他需要的進(jìn)程中，在我們的應(yīng)用程序看來(lái)感覺(jué)被卡主(阻塞)了。

非阻塞IO

當(dāng)使用非阻塞函數(shù)的時(shí)候，和阻塞IO類(lèi)比，內(nèi)核會(huì)立即返回，返回后獲得足夠的CPU時(shí)間繼續(xù)做其他的事情。

IO復(fù)用模型

當(dāng)使用fgets等待標(biāo)準(zhǔn)輸入的時(shí)候，如果此時(shí)套接字有數(shù)據(jù)但不能讀出。IO多路復(fù)用意味著可以將標(biāo)準(zhǔn)輸入、套接字等都當(dāng)做IO的一路，任何一路IO有事件發(fā)生，都將通知相應(yīng)的應(yīng)用程序去處理相應(yīng)的IO事件，在我們看來(lái)就反復(fù)同時(shí)可以處理多個(gè)事情。這就是IO復(fù)用。

信號(hào)驅(qū)動(dòng)IO

在信號(hào)驅(qū)動(dòng)式 I/O 模型中，應(yīng)用程序使用套接口進(jìn)行信號(hào)驅(qū)動(dòng) I/O，并安裝一個(gè)信號(hào)處理函數(shù)，進(jìn)程繼續(xù)運(yùn)行并不阻塞。

當(dāng)數(shù)據(jù)準(zhǔn)備好時(shí)，進(jìn)程會(huì)收到一個(gè) SIGIO 信號(hào)，可以在信號(hào)處理函數(shù)中調(diào)用 I/O 操作函數(shù)處理數(shù)據(jù)。

異步IO

用程序告知內(nèi)核啟動(dòng)某個(gè)操作，并讓內(nèi)核在整個(gè)操作（包括將數(shù)據(jù)從內(nèi)核拷貝到應(yīng)用程序的緩沖區(qū)）完成后通知應(yīng)用程序。那么和信號(hào)驅(qū)動(dòng)有啥不一樣?

• 講講select和epoll的區(qū)別？

這里一樣的套路，先說(shuō)出兩者的用途，然后兩者的優(yōu)缺點(diǎn)。

select的缺點(diǎn)

• select返回的是含有整個(gè)句柄的數(shù)組，應(yīng)用程序需要遍歷整個(gè)數(shù)組才能發(fā)現(xiàn)哪些句柄發(fā)生了事件

• select的觸發(fā)方式是水平觸發(fā)，應(yīng)用程序如果沒(méi)有完成對(duì)一個(gè)已經(jīng)就緒的文件描述符進(jìn)行IO操作，那么之后每次select調(diào)用還是會(huì)將這些文件描述符通知進(jìn)程

• 內(nèi)核 / 用戶(hù)空間內(nèi)存拷貝問(wèn)題，select每次都會(huì)改變內(nèi)核中的句柄數(shù)據(jù)結(jié)構(gòu)集，因而每次select調(diào)用時(shí)都需要從用戶(hù)空間向內(nèi)核空間復(fù)制所有的句柄數(shù)據(jù)結(jié)構(gòu)，產(chǎn)生巨大的開(kāi)銷(xiāo)

• 單個(gè)進(jìn)程能夠監(jiān)視的文件描述符的數(shù)量存在最大限制，通常是1024，當(dāng)然可以更改數(shù)量

epoll實(shí)現(xiàn)

epoll在內(nèi)核中會(huì)維護(hù)一個(gè)紅黑樹(shù)和一個(gè)雙向鏈表，紅黑樹(shù)存放通過(guò)epoll_ctl方法向epoll對(duì)象中添加進(jìn)來(lái)的事件，所以不需要每次調(diào)用epoll_wait都全量復(fù)制所有的事件結(jié)構(gòu)。

雙向鏈表存放就緒的事件，所有添加到epoll中的事件都會(huì)與設(shè)備(網(wǎng)卡)驅(qū)動(dòng)程序建立回調(diào)關(guān)系，也就是說(shuō)，當(dāng)相應(yīng)的事件發(fā)生時(shí)會(huì)調(diào)用這個(gè)回調(diào)方法，這個(gè)回調(diào)方法在內(nèi)核中叫ep_poll_callback,它會(huì)將發(fā)生的事件添加到rdlist雙鏈表中。

調(diào)用epoll_wait就會(huì)直接返回鏈表中的就緒事件，效率高。

• select適合少量活躍連接，一般幾千。

• epoll適合大量不太活躍的連接。

• 樂(lè)觀鎖和悲觀鎖了解嗎？

這個(gè)問(wèn)題延伸的問(wèn)題會(huì)很多，比如線程安全，CAS原理，優(yōu)缺點(diǎn)等。

啥是悲觀和樂(lè)觀，咋們面試的時(shí)候不得樂(lè)觀一些。想給面試來(lái)一波官方解釋?zhuān)缓蟠蟀自捊忉屢徊ň筒畈欢嗔恕?/p>

官方：悲觀鎖是總是假設(shè)最壞的情況，每次那數(shù)據(jù)都認(rèn)為別人會(huì)修改它，所以每次去那數(shù)據(jù)都要上鎖，這樣別人去拿這個(gè)數(shù)據(jù)就會(huì)阻塞。樂(lè)觀鎖就不一樣了，總是覺(jué)得一切都是最好的安排，每次拿數(shù)據(jù)都認(rèn)為別人不會(huì)修改，所以也就不上鎖，但是在更新的時(shí)候會(huì)判斷這個(gè)期間別人有沒(méi)有更新這個(gè)數(shù)據(jù)。

• 什么是緩存穿透？如何避免？什么是緩存雪崩？何如避免？

緩存穿透

一般來(lái)說(shuō)，緩存系統(tǒng)會(huì)通過(guò)key去緩存查詢(xún)，如果不存在對(duì)應(yīng)的value，就應(yīng)該去后端系統(tǒng)查找（比如DB）。

這個(gè)時(shí)候如果一些惡意的請(qǐng)求到來(lái)，就會(huì)故意查詢(xún)不存在的key,當(dāng)某一時(shí)刻的請(qǐng)求量很大，就會(huì)對(duì)后端系統(tǒng)造成很大的壓力。這就叫做緩存穿透。

如何避免？

對(duì)查詢(xún)結(jié)果為空的情況也進(jìn)行緩存，緩存時(shí)間設(shè)置短一點(diǎn)，或者該key對(duì)應(yīng)的數(shù)據(jù)insert了之后清理緩存。對(duì)一定不存在的key進(jìn)行過(guò)濾。

可以把所有的可能存在的key放到一個(gè)大的Bitmap中，查詢(xún)時(shí)通過(guò)該bitmap過(guò)濾。

緩存雪崩

當(dāng)緩存服務(wù)器重啟或者大量緩存集中在某一個(gè)時(shí)間段失效，這樣在失效的時(shí)候，會(huì)給后端系統(tǒng)帶來(lái)很大壓力。導(dǎo)致系統(tǒng)崩潰。

如何避免？

在緩存失效后，通過(guò)加鎖或者隊(duì)列來(lái)控制讀數(shù)據(jù)庫(kù)寫(xiě)緩存的線程數(shù)量。比如對(duì)某個(gè)key只允許一個(gè)線程查詢(xún)數(shù)據(jù)和寫(xiě)緩存，其他線程等待。

做二級(jí)緩存，A1為原始緩存，A2為拷貝緩存，A1失效時(shí)，可以訪問(wèn)A2，A1緩存失效時(shí)間設(shè)置為短期，A2設(shè)置為長(zhǎng)期。

不同的key，設(shè)置不同的過(guò)期時(shí)間，讓緩存失效的時(shí)間點(diǎn)盡量均勻。

2. redis相關(guān)

如果是后端/服務(wù)端面試的同學(xué)，怎么說(shuō)都的去找一本 redis 書(shū)來(lái)看看，其出現(xiàn)的概率只有那么大了，切記切記?？纯碆站問(wèn)了哪幾個(gè)問(wèn)題。

• redis的淘汰刪除策略了解嗎？

能說(shuō)不了解嗎，就算是沒(méi)有聽(tīng)說(shuō)過(guò)，咋們也可以來(lái)一句：“不好意思面試官，這一塊還不怎么深入，但是從字面意思來(lái)理解巴拉巴拉”，不至于一臉懵逼。下面我們看看redis的緩存策略

Redis中通過(guò)maxmemory參數(shù)來(lái)設(shè)定內(nèi)存的使用上限，如果Redis所使用內(nèi)存超過(guò)設(shè)定的最大值，那么會(huì)根據(jù)配置文件中的策略選取要?jiǎng)h除的key來(lái)刪除，從而留出新的鍵值空間。主要的六種淘汰key策略

1. volatile-lru

在鍵空間中設(shè)置過(guò)期時(shí)間，移除哪些最近最少使用的key，占著茅坑不拉屎的key

2. allkeys-lru

移除最近最少使用的key

3. volatile-random

在鍵空間中設(shè)置過(guò)期時(shí)間，隨機(jī)移除一個(gè)key

4. allkeys-random

隨機(jī)移除一個(gè)key

5. noeviction

當(dāng)內(nèi)存使用達(dá)到閥值的時(shí)候，所有引起申請(qǐng)內(nèi)存的命令會(huì)報(bào)錯(cuò)；

ok，現(xiàn)在知道了需要淘汰哪些key，那我們?nèi)绾稳ヌ蕴@些key

1. 定時(shí)刪除

很簡(jiǎn)單，設(shè)置一個(gè)鬧鐘，鬧鐘響了就刪除即可。這種方式對(duì)于內(nèi)存來(lái)說(shuō)還是比較友好，內(nèi)存不需要啥額外的操作，直接通過(guò)定時(shí)器就可保證盡快的刪除。

對(duì)于CPU來(lái)說(shuō)就有點(diǎn)麻煩了，如果過(guò)期鍵比較多，那么定時(shí)器也就多，這刪除操作就會(huì)占用太多的CPU資源

2. 惰性刪除

每次從鍵空間獲取鍵的時(shí)候檢查鍵的過(guò)期時(shí)間，如果過(guò)期了，刪除完事。

3. 定期刪除

每隔一段時(shí)間就去數(shù)據(jù)庫(kù)檢查，刪除過(guò)期的鍵

這種方案是定時(shí)刪除和惰性刪除的中和方法，既通過(guò)限制刪除操作執(zhí)行的時(shí)長(zhǎng)來(lái)減少對(duì)CPU時(shí)間的影響，也能減少內(nèi)存的浪費(fèi)。但是難點(diǎn)在于間隔時(shí)長(zhǎng)需要根據(jù)業(yè)務(wù)情況而定。

3. mysql

• mysql中使用的鎖有哪些？什么時(shí)候使用行鎖，什么時(shí)候會(huì)使用表鎖？

InnoDB中的行鎖是通過(guò)索引上的索引項(xiàng)實(shí)現(xiàn)，主要特點(diǎn)是，只有通過(guò)索引條件檢索數(shù)據(jù)，InnoDB才會(huì)使用行級(jí)鎖，否則InnoDB將使用表鎖。

這里注意，在Mysql中，行級(jí)鎖不是鎖記錄而是鎖索引。索引又分為主鍵索引和非主鍵索引兩種。如果在一條語(yǔ)句中操作了非主鍵索引，Mysql會(huì)鎖定該非主鍵索引，再鎖定相關(guān)的主鍵索引。

• 了解過(guò)間隙鎖嗎？間隙鎖的加鎖范圍是怎么確定的？

• 了解B+樹(shù)嗎？B+樹(shù)什么時(shí)候會(huì)出現(xiàn)結(jié)點(diǎn)分裂？

這個(gè)回答在上一篇的B+樹(shù)已經(jīng)詳細(xì)說(shuō)了。這里簡(jiǎn)述一下

1. 將已滿(mǎn)結(jié)點(diǎn)進(jìn)行分裂，將已滿(mǎn)節(jié)點(diǎn)后M/2節(jié)點(diǎn)生成一個(gè)新節(jié)點(diǎn)，將新節(jié)點(diǎn)的第一個(gè)元素指向父節(jié)點(diǎn)。

2. 父節(jié)點(diǎn)出現(xiàn)已滿(mǎn)，將父節(jié)點(diǎn)繼續(xù)分裂。

3. 一直分裂，如果根節(jié)點(diǎn)已滿(mǎn)，則需要分類(lèi)根節(jié)點(diǎn)，此時(shí)樹(shù)的高度增加。

• 事務(wù)還沒(méi)執(zhí)行完數(shù)據(jù)庫(kù)掛了，重啟的時(shí)候會(huì)發(fā)生什么？

• undo日志和redo日志分別是干嘛的？

redo log重做日志是InnDB存儲(chǔ)引擎層的，用來(lái)保證事務(wù)安全。在事務(wù)提交之前，每個(gè)修改操作都會(huì)記錄變更后的數(shù)據(jù)，保存的是物理日志-數(shù)據(jù)，防止發(fā)生故障的時(shí)間點(diǎn)，有臟頁(yè)未寫(xiě)入磁盤(pán)，在重啟mysql的時(shí)候，根據(jù)redo log進(jìn)行重做從而達(dá)到事務(wù)的持久性

undo log回滾日志保存了事務(wù)發(fā)生之前的數(shù)據(jù)的一個(gè)版本，可以用于回滾，同時(shí)也提供多版本并發(fā)控制下的讀。

• 簡(jiǎn)單講講數(shù)據(jù)庫(kù)的MVCC的實(shí)現(xiàn)原理？

細(xì)說(shuō)太多了，幾個(gè)大寫(xiě)字母代表啥，這幾個(gè)大寫(xiě)字母又是如何關(guān)聯(lián)起來(lái)完事。細(xì)問(wèn)再深究

• mysql的binlog日志什么時(shí)候會(huì)使用？

首先應(yīng)該知道binlog是一個(gè)二進(jìn)制文件，記錄所有增刪改操作，節(jié)點(diǎn)之間的復(fù)制都會(huì)依靠binlog來(lái)完成。從底層原理來(lái)說(shuō)，binlog有三個(gè)模式

1. 模式1--row模式

每一行的數(shù)據(jù)被修改就會(huì)記錄在日志中，然后在slave段對(duì)相同的數(shù)據(jù)進(jìn)行修改。比如說(shuō)"update xx where id in(1,2,3,4,5)"，使用此模式就會(huì)記錄5條記錄

2. 模式2--statement模式

修改數(shù)據(jù)的sql會(huì)記錄到master的binlog中。slave在復(fù)制的時(shí)候sql thread會(huì)解析成和原來(lái)maseter端執(zhí)行過(guò)的相同的sql在此執(zhí)行

3. 模式3--mixed模式

mixed模式即混合模式，Mysql會(huì)根據(jù)執(zhí)行的每一條具體sql區(qū)分對(duì)待記錄的日志形式。那么binlog的主從同步流程到底是咋樣的

流程簡(jiǎn)述：

Master執(zhí)行完增刪改操作后都會(huì)記錄binlog日志,當(dāng)需要同步的時(shí)候會(huì)主動(dòng)通知slave節(jié)點(diǎn)，slave收到通知后使用IO THREAD主動(dòng)去master讀取binlog寫(xiě)入relay日志(中轉(zhuǎn)日志),然后使 SQL THREAD完成對(duì)relay日志的解析然后入庫(kù)操作,完成同步。

4. 基本數(shù)據(jù)結(jié)構(gòu)

• 使用LRU時(shí)，如果短時(shí)間內(nèi)會(huì)出現(xiàn)大量只會(huì)使用一次的數(shù)據(jù)，可能導(dǎo)致之前大量高頻使用的緩存被刪除，請(qǐng)問(wèn)有什么解決辦法?

• 了解過(guò)循環(huán)鏈表嗎？他的長(zhǎng)度怎么計(jì)算？

他的主要特點(diǎn)是鏈表中的最后一個(gè)節(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，這里循環(huán)鏈表判斷鏈表結(jié)束的標(biāo)志是，判斷尾節(jié)點(diǎn)是不是指向頭結(jié)點(diǎn)

• 哪種數(shù)據(jù)結(jié)構(gòu)可以支持快速插入，刪除，查找等操作？

思考這個(gè)問(wèn)題的時(shí)候，我們不凡復(fù)習(xí)下不錯(cuò)的二分查找，它依賴(lài)數(shù)組隨機(jī)訪問(wèn)的特性，其查找時(shí)間復(fù)雜度為O(log n)。如果我們將元素放入鏈表中，二分查找還好使嗎？這就是今天和大家分享的跳表

理解跳表

假設(shè)使用單鏈表存儲(chǔ)n個(gè)元素，其中元素有序如下圖所示

從鏈表中查找一個(gè)元素，自然從頭開(kāi)始遍歷找到需要查找的元素，此時(shí)的時(shí)間復(fù)雜度為O(n)。那采用什么方法可以提高查詢(xún)的效率呢？問(wèn)就是加索引，如何加，我們從這部分?jǐn)?shù)據(jù)中抽取幾個(gè)元素出來(lái)作為單獨(dú)的一個(gè)鏈表，如下圖所示]

假設(shè)此時(shí)咋們查找元素16，首先一級(jí)索引處尋找，當(dāng)找到元素14的時(shí)候，下一個(gè)節(jié)點(diǎn)的值為18，意味著我們尋找的數(shù)在這兩個(gè)數(shù)的中間。此時(shí)直接從14節(jié)點(diǎn)指針下移到下面的原始鏈表中，繼續(xù)遍歷，正好下一個(gè)元素就是我們尋找的16。好了，我們小結(jié)一下，如果從原始鏈表中尋找元素16，需要遍歷比較8次，如果通過(guò)索引鏈表尋找我們只需要5次即可。

我們繼續(xù)查找元素16，此時(shí)比較次數(shù)變?yōu)?次。這樣看來(lái)，加一層索引查找的次數(shù)就變少，如果有n個(gè)元素到底有多少索引？

假設(shè)我們按照每?jī)蓚€(gè)結(jié)點(diǎn)就抽出一個(gè)結(jié)點(diǎn)作為上一層的索引節(jié)點(diǎn)，第一層所以節(jié)點(diǎn)個(gè)數(shù)n/2，第二層為n/4,第x級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)是第x-1級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)的1/2，那第x級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就是n/(2^x)。假設(shè)索引有y級(jí)，我們可以得到n/(2^y)=2，從而求得y=log2n-1。

這么多索引是不是就很浪費(fèi)內(nèi)存嘞？

假設(shè)原始鏈表大小為n，那第一級(jí)索引大約有 n/2 個(gè)結(jié)點(diǎn)，第二級(jí)索引大約有 n/4 個(gè)結(jié)點(diǎn)，以此類(lèi)推，每上升一級(jí)就減少一半，直到剩下 2 個(gè)結(jié)點(diǎn)。如果我們把每層索引的結(jié)點(diǎn)數(shù)寫(xiě)出來(lái)，就是一個(gè)等比數(shù)列。這幾級(jí)索引的結(jié)點(diǎn)總和就是 n/2+n/4+n/8…+8+4+2=n-2 。所以，跳表的空間復(fù)雜度是 O(n) 。那還能不能降低一些呢。機(jī)智的你應(yīng)該就考慮到假設(shè)每三個(gè)結(jié)點(diǎn)抽取一個(gè)節(jié)點(diǎn)作為索引鏈表的節(jié)點(diǎn)。

跳表與二叉查找樹(shù)

兩者其查找的時(shí)間復(fù)雜度均為O(logn) ，那跳表還有哪些優(yōu)勢(shì)？

先看二叉查找樹(shù)，

這種結(jié)構(gòu)會(huì)導(dǎo)致二叉查找樹(shù)的查找效率變?yōu)?O(n),。

跳表與紅黑樹(shù)

說(shuō)實(shí)話，紅黑樹(shù)確實(shí)比較復(fù)雜，面試的時(shí)候讓你寫(xiě)紅黑樹(shù)，你就給他大嘴巴子？

紅黑樹(shù)需要通過(guò)左右旋的方式去維持樹(shù)大小平衡。而跳表是通過(guò)隨機(jī)函數(shù)來(lái)維護(hù)前面提到的 “ 平衡性 ” 。當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候，我們可以選擇同時(shí)將這個(gè)數(shù)據(jù)插入到部分索引層中。如何選擇加入哪些索引層呢？
我們通過(guò)一個(gè)隨機(jī)函數(shù)，來(lái)決定將這個(gè)結(jié)點(diǎn)插入到哪幾級(jí)索引中，比如隨機(jī)函數(shù)生成了值 K ，那我們就將這個(gè)結(jié)點(diǎn)添加到第一級(jí)到第 K 級(jí)這 K 級(jí)索引中。當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候，我們可以選擇同時(shí)將這個(gè)數(shù)據(jù)插入到部分索引層中。

小結(jié)

Redis中的有序集合采用了跳表的方式來(lái)實(shí)現(xiàn)，其實(shí)還采用了散列表等數(shù)據(jù)結(jié)構(gòu)進(jìn)行融合。

它在插入，刪除等都有比較快的速度，雖然紅黑樹(shù)也可以做到，但是紅黑樹(shù)對(duì)于按照區(qū)間查找數(shù)據(jù)這個(gè)操作，跳表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷就可以了

• 平時(shí)愛(ài)看技術(shù)博客嗎？分享一篇最近的技術(shù)博客？平時(shí)上B站嗎？

看的技術(shù)博客多了，這就是嘮嗑。比如說(shuō)，看看小林一天天BB的文章，哈哈哈哈哈

面試官：我擦，尼瑪說(shuō)的這個(gè)我都關(guān)注了，難怪我問(wèn)啥你都能說(shuō)個(gè)一二三。

5. 總結(jié)

請(qǐng)記下以下幾點(diǎn):

• 公司招你去是干活了，不會(huì)因?yàn)槟阍趺丛趺吹亩档蛯?duì)你的要求標(biāo)準(zhǔn)。

• 工具上面寫(xiě)代碼和手撕代碼完全不一樣。

• 珍惜每一次面試機(jī)會(huì)并學(xué)會(huì)復(fù)盤(pán)。

• 對(duì)于應(yīng)屆生主要考察的還是計(jì)算機(jī)基礎(chǔ)知識(shí)的掌握，項(xiàng)目要求沒(méi)有那么高，是自己做的就使勁摳細(xì)節(jié)，做測(cè)試，只有這樣，才知道會(huì)遇到什么問(wèn)題，遇到什么難點(diǎn)，如何解決的。從而可以侃侃而談了。

• 非科班也不要怕，怕了你就輸了！一定要多嘗試。

嘮嗑

大家好，我是小林，一個(gè)專(zhuān)為大家圖解的工具人，如果覺(jué)得文章對(duì)你有幫助，歡迎分享給你的朋友，也給小林點(diǎn)個(gè)「在看」，這對(duì)小林非常重要，謝謝你們，我們下次見(jiàn)！

推薦閱讀

讀者問(wèn)：小林怎么學(xué)操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)呀？