深入理解數(shù)據(jù)結(jié)構(gòu)和算法

時(shí)間：2021-08-19 15:31:02

關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu)

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]hi，大家好，今天分享一些對(duì)數(shù)據(jù)結(jié)構(gòu)和算法精華總結(jié)，希望對(duì)大家的面試或者工作有一定的幫助；看完本文可以學(xué)到什么知道哪些數(shù)據(jù)結(jié)構(gòu)和算法在實(shí)際工作中最常用，最重要理解一些設(shè)計(jì)上注意事項(xiàng)（經(jīng)驗(yàn)總結(jié)）掌握常用數(shù)據(jù)結(jié)構(gòu)和算法核心知識(shí)點(diǎn)數(shù)據(jù)結(jié)構(gòu)工作中或者開(kāi)源項(xiàng)目中最常用數(shù)據(jù)結(jié)構(gòu)：數(shù)組/lis...

hi，大家好，今天分享一些對(duì)數(shù)據(jù)結(jié)構(gòu)和算法精華總結(jié)，希望對(duì)大家的面試或者工作有一定的幫助；

看完本文可以學(xué)到什么

知道哪些數(shù)據(jù)結(jié)構(gòu)和算法在實(shí)際工作中最常用，最重要
理解一些設(shè)計(jì)上注意事項(xiàng)（經(jīng)驗(yàn)總結(jié)）
掌握常用數(shù)據(jù)結(jié)構(gòu)和算法核心知識(shí)點(diǎn)

數(shù)據(jù)結(jié)構(gòu)

工作中或者開(kāi)源項(xiàng)目中最常用數(shù)據(jù)結(jié)構(gòu)：數(shù)組/list hash tree

O(n)結(jié)構(gòu)：list/棧/隊(duì)列

O(1)結(jié)構(gòu)：數(shù)組/hash/位圖

O(logn)樹(shù)形結(jié)構(gòu)：紅黑樹(shù)/B 樹(shù)/skip list

數(shù)組

核心點(diǎn)：

1 內(nèi)存空間大小固定，如果支持動(dòng)態(tài)擴(kuò)展，需要內(nèi)存遷移，有一定的性能代價(jià)，比如C STL的vector結(jié)構(gòu)；

2 內(nèi)存連續(xù)，對(duì)CPU cache友好，如果內(nèi)存空間足夠，能用數(shù)組就最好用數(shù)組結(jié)構(gòu)；

3 ?數(shù)組空間一般都是預(yù)分配的，不會(huì)頻繁申請(qǐng)和釋放，所以可以提供程序性能，這個(gè)做內(nèi)存池優(yōu)化的實(shí)現(xiàn)手段；

鏈表

核心點(diǎn)：

可以動(dòng)態(tài)項(xiàng)擴(kuò)縮容，比較節(jié)約空間；
鏈表編程邊界case檢查：??
每個(gè)節(jié)點(diǎn)必須有個(gè)“指針“要么指向其他節(jié)點(diǎn)，要么為空，這樣才能把鏈表串起來(lái)，任何操作都必須保證鏈表完整性，不允許節(jié)點(diǎn)無(wú)故脫鏈，所以任何操作之前，都要思考會(huì)不會(huì)導(dǎo)致節(jié)點(diǎn)脫鏈，如果不下心脫鏈就會(huì)存在內(nèi)存泄漏風(fēng)險(xiǎn)；
鏈表作為最基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，很多高級(jí)結(jié)構(gòu)：隊(duì)列，棧，hash，二叉樹(shù)，都是在鏈表基礎(chǔ)上演化而來(lái)；

編程技巧

頭結(jié)點(diǎn)解決什么問(wèn)題？

頭結(jié)點(diǎn):是虛擬出來(lái)的一個(gè)節(jié)點(diǎn)，不保存數(shù)據(jù)。頭結(jié)點(diǎn)的next指針指向鏈表中的第一個(gè)節(jié)點(diǎn)。對(duì)于頭結(jié)點(diǎn)，數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可存儲(chǔ)如鏈表長(zhǎng)度等附加信息。頭結(jié)點(diǎn)不是鏈表所必需的。

頭指針:是指向第一個(gè)結(jié)點(diǎn)的指針,如果鏈表沒(méi)有引入頭結(jié)點(diǎn)，那么頭指針指向的是鏈表的第一個(gè)結(jié)點(diǎn)。頭指針是鏈表所必需的。

[注意]無(wú)論是否有頭結(jié)點(diǎn)，頭指針始終指向鏈表的第一個(gè)結(jié)點(diǎn)。如果有頭結(jié)點(diǎn)，頭指針就指向頭結(jié)點(diǎn)。

1）對(duì)鏈表的刪除、插入操作時(shí)，第一個(gè)結(jié)點(diǎn)的操作更方便

如果鏈表沒(méi)有頭結(jié)點(diǎn)，那么頭指針指向的是鏈表的第一個(gè)結(jié)點(diǎn)，當(dāng)在第一個(gè)結(jié)點(diǎn)前插入一個(gè)節(jié)點(diǎn)時(shí)，那么頭指針要相應(yīng)指向新插入的結(jié)點(diǎn)，把第一個(gè)結(jié)點(diǎn)刪除時(shí)，頭指針的指向也要更新。也就是說(shuō)如果沒(méi)有頭結(jié)點(diǎn)，我們需要維護(hù)著頭指針的指向更新。因?yàn)轭^指針指向的是鏈表的第一個(gè)結(jié)點(diǎn)，如果引入頭結(jié)點(diǎn)的話，那么頭結(jié)點(diǎn)的next始終都是鏈表的第一個(gè)結(jié)點(diǎn)。

2）統(tǒng)一空表和非空表的處理

有了頭結(jié)點(diǎn)之后頭指針指向頭結(jié)點(diǎn)，不論鏈表是否為空，頭指針總是非空，而且頭結(jié)點(diǎn)的設(shè)置使得對(duì)鏈表的第一個(gè)位置上的操作與在表中其它位置上的操作一致，即統(tǒng)一空表和非空表的處理。

鏈表最常規(guī)操作

刪除: ?遍歷鏈表，找到刪除的節(jié)點(diǎn)，保存刪除節(jié)點(diǎn)的pre節(jié)點(diǎn)和next節(jié)點(diǎn)；

然后pre和next 串起來(lái)

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
? ? next->prev = prev;
? ? prev->next = next;
}再釋放刪除節(jié)點(diǎn)內(nèi)存；

添加: ?遍歷鏈表找到要加入位置（或者節(jié)點(diǎn)），保存該節(jié)點(diǎn)的pre節(jié)點(diǎn)和next節(jié)點(diǎn)，然后把新接入插入到鏈表中：

static inline void __list_add(struct list_head *new,
? ? struct list_head *prev,
? ? struct list_head *next)
{
? ? next->prev = new;
? ? new->next = next;
? ? new->prev = prev;
? ? prev->next = new;
}2 ?快慢指針，快慢指針一般都初始化指向鏈表的頭結(jié)點(diǎn) head，前進(jìn)時(shí)快指針 fast 在前，慢指針 slow 在后，巧妙解決一些鏈表中的問(wèn)題。比如：判定鏈表中是否含有環(huán)，尋找鏈表的中點(diǎn), 尋找距離尾部第K個(gè)節(jié)點(diǎn)等；

3 dummy node，dummy node是鏈表問(wèn)題中一個(gè)重要的技巧，中文翻譯叫“啞節(jié)點(diǎn)”，使用通常針對(duì)單鏈表沒(méi)有前向指針的問(wèn)題，保證鏈表的 head不會(huì)在刪除操作中丟失，當(dāng)鏈表的 head 有可能變化（被修改或者被刪除）時(shí)，使用 dummy node 可以很好的簡(jiǎn)化代碼，最終返回 dummy.next 即新的鏈表。

4 通常鏈表有兩種實(shí)現(xiàn)方式，一種是抽象獨(dú)立型，一種是傳統(tǒng)耦合型；

list作為常用數(shù)據(jù)結(jié)構(gòu)，寫代碼時(shí)候經(jīng)常會(huì)遇到，可以看一下傳統(tǒng)list設(shè)計(jì)和抽象list設(shè)計(jì)有什么不一樣。

一般的雙向鏈表一般是如下的結(jié)構(gòu):

有個(gè)單獨(dú)的頭結(jié)點(diǎn)(head)
每個(gè)節(jié)點(diǎn)(node)除了包含必要的數(shù)據(jù)之外，還有2個(gè)指針(pre,next)
pre指針指向前一個(gè)節(jié)點(diǎn)(node)，next指針指向后一個(gè)節(jié)點(diǎn)(node)
頭結(jié)點(diǎn)(head)的pre指針指向鏈表的最后一個(gè)節(jié)點(diǎn)
最后一個(gè)節(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn)(head)

傳統(tǒng)list如下圖：

傳統(tǒng)的鏈表不同node類型，需要重新定義結(jié)構(gòu)，不夠通用化，還需要為node實(shí)現(xiàn)脫鏈、入鏈操作等。

我們需要抽象出一個(gè)“基類”來(lái)實(shí)現(xiàn)鏈表的功能，其他數(shù)據(jù)結(jié)構(gòu)只需要簡(jiǎn)單的繼承這個(gè)鏈表類就可以了。

抽象型list設(shè)計(jì)如下：

鏈表不是將用戶數(shù)據(jù)保存在鏈表節(jié)點(diǎn)中，而是將鏈表節(jié)點(diǎn)保存在用戶數(shù)據(jù)中
鏈表節(jié)點(diǎn)只有2個(gè)指針(prev和next)
prev指針指向前一個(gè)節(jié)點(diǎn)的鏈表節(jié)點(diǎn)，next指針指向后一個(gè)節(jié)點(diǎn)(node)的鏈表節(jié)點(diǎn)

如下圖：

這樣設(shè)計(jì)的好處是鏈表的節(jié)點(diǎn)將獨(dú)立于用戶數(shù)據(jù)之外，便于把鏈表的操作獨(dú)立出來(lái)，和具體數(shù)據(jù)節(jié)點(diǎn)無(wú)關(guān)，這里可能有些人會(huì)問(wèn)，數(shù)據(jù)節(jié)點(diǎn)怎么訪問(wèn)呢？通過(guò)一個(gè)container_of的宏從鏈表節(jié)點(diǎn)找到數(shù)據(jù)節(jié)點(diǎn)起始地址：

找到數(shù)據(jù)節(jié)點(diǎn)起始地址后，通過(guò)數(shù)據(jù)節(jié)點(diǎn)定義就可以訪問(wèn)數(shù)據(jù)。

5 鏈表最核心技巧，就是理解指針操作（包括安全檢查-空指針判斷），不要被指針復(fù)雜的賦值操作搞暈，多敲代碼，找到經(jīng)典的鏈表練習(xí)題（28原則）不斷練習(xí)，比如：判斷鏈表是否有環(huán)，反轉(zhuǎn)鏈表，合并鏈表等，寫好每一題，再認(rèn)真總結(jié)，唯有熟才能生巧。

棧

核心點(diǎn)：

需要關(guān)注棧的深度大?。ㄈ萘浚?；
棧各個(gè)極端情況處理，比如空，滿，溢出等；
多線程下實(shí)現(xiàn)安全的棧操作；
堆棧很容易被攻擊(緩沖區(qū)溢出攻擊)，程序員必須特別注意避免這些實(shí)現(xiàn)的陷阱, 防止代碼產(chǎn)生安全漏洞；

使用場(chǎng)景：

1 ?操作系統(tǒng)程序運(yùn)行棧，實(shí)現(xiàn)函數(shù)調(diào)用運(yùn)行機(jī)制；

2 ?操作前進(jìn)和后退，比如編輯器，瀏覽器等；

3 ?編譯器使用，比如表達(dá)式解析，語(yǔ)法檢查等；

隊(duì)列

核心點(diǎn)：

隊(duì)列核心作用：應(yīng)用耦合、異步處理、流量削鋒（緩沖）；
隊(duì)列各個(gè)極端情況處理，比如空，滿，溢出等；
隊(duì)列支持多線程并發(fā)操作，加鎖或者無(wú)鎖隊(duì)列實(shí)現(xiàn)；
隊(duì)列零拷貝優(yōu)化，比如隊(duì)列操作零拷貝（操作指針地址或者索引），IO零拷貝；

使用場(chǎng)景：

1 各種消息隊(duì)列中間件，比如RabbitMQ、RocketMQ、ActiveMQ、Kafka、ZeroMQ、MetaMq等；

2 各種排隊(duì)（緩沖區(qū)）系統(tǒng)，操作系統(tǒng)任務(wù)FIFO調(diào)度隊(duì)列，數(shù)據(jù)包發(fā)送隊(duì)列，凡是需要滿足FIFO場(chǎng)景，都是可以用隊(duì)列實(shí)現(xiàn)；

Hash結(jié)構(gòu)：

hash結(jié)構(gòu)核心點(diǎn)：

Hash是以空間換時(shí)間結(jié)構(gòu)，需要評(píng)估好所有Hash頭結(jié)構(gòu)的內(nèi)存使用量；
Hash桶選擇需要考慮到內(nèi)存和沖突鏈長(zhǎng)度大小（影響查找效率)；
hash的優(yōu)化 --解決hash沖突
3.1 內(nèi)存有限場(chǎng)景下，就需要優(yōu)化沖突鏈結(jié)構(gòu)（鏈表轉(zhuǎn)紅黑樹(shù)）；
3.2 優(yōu)化hash函數(shù)，讓hash結(jié)果更均勻；
3.3 可以考慮雙重hash（空間和時(shí)間，還有編碼復(fù)雜度的一種折中方案）
?
需要考慮hash擴(kuò)容
4.1 在設(shè)計(jì)hash結(jié)構(gòu)的時(shí)候，需要考慮未來(lái)可用戶量增長(zhǎng)后導(dǎo)致規(guī)格變大，這樣原先hash結(jié)構(gòu)已經(jīng)不合適，沖突鏈太長(zhǎng)，導(dǎo)致查詢效率急速降低，所以再最初設(shè)計(jì)的時(shí)候，需要考慮到rehash設(shè)計(jì)（為什么不一次設(shè)置為最大，因?yàn)閮?nèi)存不是無(wú)限的，需要考慮一定時(shí)間還可以提供很好的服務(wù)，不需要升級(jí)版本），當(dāng)hash沖突鏈太長(zhǎng)后，進(jìn)行rehash流程；
4.2 rehash算法有很多，需要考慮幾點(diǎn)：
a. 要不要保證hash一致性，擴(kuò)容后，重hash還是不變，這個(gè)在負(fù)載均衡網(wǎng)關(guān)里面很重要，需要保證hash選擇RS后端服務(wù)節(jié)點(diǎn)不變，否則會(huì)到存量連接走到其他RS節(jié)點(diǎn)，讓服務(wù)變得不可用，甚至斷開(kāi)（tcp需要建立會(huì)話，其他RS沒(méi)有這個(gè)會(huì)話）等。?所以這里可能會(huì)采用一致性hash算法，或者其他hash算法，保證相同client去相同RS。

其實(shí)redis的rehash算法，就是類似這種，屬于漸進(jìn)式rehash算法，好處在于它采取分而治之的方式，將 rehash 鍵值對(duì)所需的計(jì)算工作均灘到對(duì)字典的每個(gè)添加、刪除、查找和更新操作上，從而避免了集中式 rehash 而帶來(lái)的龐大計(jì)算量。

業(yè)界還有其他擴(kuò)容的算法，比如Linear Hash Tables是一種動(dòng)態(tài)擴(kuò)展空間的哈希表，會(huì)隨著插入的元素的增多而自動(dòng)擴(kuò)展空間等；

使用場(chǎng)景：

1 redis的dict結(jié)構(gòu)設(shè)計(jì)；

2 簽名算法MD5算法；

3 數(shù)據(jù)包校驗(yàn) CRC算法；

4 負(fù)載均衡LB選擇后端服務(wù)器hash算法；

5 布隆過(guò)濾器：布隆過(guò)濾器被廣泛用于黑名單過(guò)濾、垃圾郵件過(guò)濾、爬蟲(chóng)判重系統(tǒng)以及緩存穿透問(wèn)題。對(duì)于數(shù)量小，內(nèi)存足夠大的情況，我們可以直接用hashMap或者h(yuǎn)ashSet就可以滿足這個(gè)活動(dòng)需求了。但是如果數(shù)據(jù)量非常大，比如5TB的硬盤上放滿了用戶的參與數(shù)據(jù)，需要一個(gè)算法對(duì)這些數(shù)據(jù)進(jìn)行去重，取得活動(dòng)的去重參與用戶數(shù)。這種時(shí)候，布隆過(guò)濾器就是一種比較好的解決方案了。

位圖（Bitmap）

核心點(diǎn)：

即位（Bit）的集合，是一種數(shù)據(jù)結(jié)構(gòu)，可用于記錄大量的0-1狀態(tài)，在很多地方都會(huì)用到，優(yōu)勢(shì)是可以在一個(gè)非常高的空間利用率下保存大量0-1狀態(tài)。
本質(zhì)上是采用了bit位來(lái)表示元素狀態(tài)，從而在特定場(chǎng)景下能夠極大的節(jié)省存儲(chǔ)空間，非常適合對(duì)海量數(shù)據(jù)的查找，判重，刪除等問(wèn)題的處理；
數(shù)據(jù)稀疏。又比如要存入(10,8887983,93452134)這三個(gè)數(shù)據(jù)，我們需要建立一個(gè) 99999999 長(zhǎng)度的 BitMap ，但是實(shí)際上只存了3個(gè)數(shù)據(jù)，這時(shí)候就有很大的空間浪費(fèi)，碰到這種問(wèn)題的話，可以通過(guò)引入 Roaring BitMap 來(lái)解決，就是通過(guò)壓縮算法進(jìn)行空間壓縮。
數(shù)據(jù)碰撞。比如將字符串映射到 BitMap 的時(shí)候會(huì)有碰撞的問(wèn)題，那就可以考慮用 Bloom Filter 來(lái)解決，Bloom Filter 使用多個(gè) Hash 函數(shù)來(lái)減少?zèng)_突的概率

使用場(chǎng)景：

1 在Java里面一個(gè)int類型占4個(gè)字節(jié)，假如要對(duì)于10億個(gè)int數(shù)據(jù)進(jìn)行處理呢？10億*4/1024/1024/1024=4個(gè)G左右，需要4個(gè)G的內(nèi)存。如果能夠采用bit儲(chǔ),10_0000_0000Bit=1_2500_0000byte=122070KB=119MB, 那么在存儲(chǔ)空間方面可以大大節(jié)省。在Java里面，BitMap已經(jīng)有對(duì)應(yīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類java.util.BitSet，BitSet的底層使用的是long類型的數(shù)組來(lái)存儲(chǔ)元素。

2 redis bitmap；

3 布隆過(guò)濾器；

4 ?Linux內(nèi)核（如inode，磁盤塊）；

紅黑樹(shù)

核心點(diǎn)

在已經(jīng)有了AVL之類的BBST，為什么還需要引入紅黑樹(shù)？我們希望數(shù)據(jù)結(jié)構(gòu)具有關(guān)聯(lián)性，即相鄰版本之間，比如說(shuō)第一次插入，和第二次插入時(shí)，樹(shù)的結(jié)構(gòu)不能發(fā)生太大變化，應(yīng)該可以經(jīng)過(guò)O（1）次數(shù)就可以變化完成。對(duì)于AVL樹(shù)來(lái)說(shuō)，插入是滿足這個(gè)條件的，刪除卻不滿足這個(gè)條件。紅黑樹(shù)就滿足這一特性，插入和刪除操作后的拓?fù)渥兓粫?huì)超過(guò)O(1)。
紅黑樹(shù)與AVL樹(shù)相似，但提供更快的實(shí)時(shí)有界最壞情況下的插入和刪除性能（分別達(dá)到最多兩輪和三輪以平衡樹(shù)），但速度稍慢（但仍為O（log n））查找時(shí)間；
紅黑樹(shù)和AVL樹(shù)一樣都對(duì)插入時(shí)間、刪除時(shí)間和查找時(shí)間提供了最好可能的最壞情況擔(dān)保。這不只是使它們?cè)跁r(shí)間敏感的應(yīng)用，如實(shí)時(shí)應(yīng)用（real time application）中有價(jià)值，而且使它們有在提供最壞情況擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中作為基礎(chǔ)模板的價(jià)值；例如，在計(jì)算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)都可以基于紅黑樹(shù)實(shí)現(xiàn)。
紅黑樹(shù)在函數(shù)式編程中也特別有用，在這里它們是最常用的持久數(shù)據(jù)結(jié)構(gòu)（persistent data structure）之一，它們用來(lái)構(gòu)造關(guān)聯(lián)數(shù)組和集合，每次插入、刪除之后它們能保持為以前的版本。除了的時(shí)間之外，紅黑樹(shù)的持久版本對(duì)每次插入或刪除需要的空間。
紅黑樹(shù)相對(duì)于AVL樹(shù)來(lái)說(shuō)，犧牲了部分平衡性以換取插入/刪除操作時(shí)少量的旋轉(zhuǎn)操作，整體來(lái)說(shuō)性能要優(yōu)于AVL樹(shù)。
維護(hù)紅黑樹(shù)的平衡需要考慮7種不同的情況:

紅黑樹(shù)為什么綜合性能好？

因?yàn)?strong>紅黑樹(shù)利用了緩存。

Robert Sedgewick, ?紅黑樹(shù)的發(fā)明人，在《算法（第4版）》中說(shuō)過(guò)，紅黑樹(shù)等價(jià)于2-3樹(shù), 換句話說(shuō)，對(duì)于每個(gè)2-3樹(shù)，都存在至少一個(gè)數(shù)據(jù)元素是同樣次序的紅黑樹(shù)。在2-3樹(shù)上的插入和刪除操作也等同于在紅黑樹(shù)中顏色翻轉(zhuǎn)和旋轉(zhuǎn)。這使得2-3樹(shù)成為理解紅黑樹(shù)背后的邏輯的重要工具，這也是很多介紹算法的教科書(shū)在紅黑樹(shù)之前介紹2-3樹(shù)的原因，盡管2-3樹(shù)在實(shí)踐中不經(jīng)常使用。

其中2-節(jié)點(diǎn) 等價(jià)于普通平衡二叉樹(shù)的節(jié)點(diǎn)，3-節(jié)點(diǎn) 本質(zhì)上是非平衡性的緩存。

當(dāng)需要再平衡（rebalance）時(shí)，增刪操作時(shí)，2-節(jié)點(diǎn) 與 3-節(jié)點(diǎn)間的轉(zhuǎn)化會(huì)吸收不平衡性，減少旋轉(zhuǎn)次數(shù)，使再平衡盡快結(jié)束。

在綜合條件下，增刪操作相當(dāng)時(shí)，數(shù)據(jù)的隨機(jī)性強(qiáng)時(shí)，3-節(jié)點(diǎn)的非平衡性緩沖效果越明顯。因此紅黑樹(shù)的綜合性能更優(yōu)。

繼續(xù)追根溯源，紅黑樹(shù)的性能優(yōu)勢(shì)，本質(zhì)上是用空間換時(shí)間。

發(fā)展：

我們將紅黑樹(shù)分成這么幾種類型：左傾紅黑樹(shù)、右傾紅黑樹(shù)、AA樹(shù)。

左傾紅黑樹(shù)（LLRB，Left-Learning Red-Black Tree），一個(gè)節(jié)點(diǎn)如果有紅色子節(jié)點(diǎn)，那么，它的紅色子節(jié)點(diǎn)是向左傾斜的。

右傾紅黑樹(shù)（RLRB，Right-Learning Red-Black Tree），也是一樣的道理，即紅色子節(jié)點(diǎn)向右傾斜。

左傾紅黑樹(shù)（*LLRB**）是一種類型的自平衡二叉查找樹(shù)。它是紅黑樹(shù)的變體，并保證對(duì)操作相同漸近的復(fù)雜性，但被設(shè)計(jì)成更容易實(shí)現(xiàn)。

AA樹(shù)是紅黑樹(shù)的一種變種，是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹，設(shè)計(jì)的目的是減少紅黑樹(shù)考慮的不同情況，區(qū)別于紅黑樹(shù)的是，AA樹(shù)的紅節(jié)點(diǎn)只能作為右葉子，從而大大簡(jiǎn)化了維護(hù)2-3樹(shù)的模擬，因?yàn)锳A樹(shù)有嚴(yán)格的條件(紅節(jié)點(diǎn)只能為右節(jié)點(diǎn))，故只需考慮2種情形:

使用場(chǎng)景：

1 C

廣泛用在C 的STL中。如map和set都是用紅黑樹(shù)實(shí)現(xiàn)的；

2 Java

Java的TreeMap實(shí)現(xiàn)；

HashMap的底層實(shí)現(xiàn)，在JDK1.8中為了解決過(guò)度哈希沖突帶來(lái)的長(zhǎng)鏈表，當(dāng)鏈表長(zhǎng)度大于某個(gè)閾值會(huì)將鏈表轉(zhuǎn)為紅黑樹(shù)；

3 Linux操作系統(tǒng)

?????CFS進(jìn)程調(diào)度算法中，vruntime利用紅黑樹(shù)來(lái)進(jìn)行存儲(chǔ)，選擇最小vruntime節(jié)點(diǎn)調(diào)度。

數(shù)據(jù)包CD / DVD驅(qū)動(dòng)程序執(zhí)行相同的操作。

高分辨率計(jì)時(shí)器代碼使用rbtree來(lái)組織未完成的計(jì)時(shí)器請(qǐng)求。

ext3文件系統(tǒng)跟蹤紅黑樹(shù)中的目錄條目。

虛擬內(nèi)存結(jié)構(gòu)管理（VMA）.。

多路復(fù)用技術(shù)的Epoll的核心結(jié)構(gòu)也是紅黑樹(shù) 雙向鏈表。

加密密鑰和網(wǎng)絡(luò)數(shù)據(jù)包均由紅黑樹(shù)跟蹤。

4 Linux應(yīng)用程序

nginx用紅黑樹(shù)管理timer等。

5 實(shí)際工作中也會(huì)用到紅黑樹(shù)

1 我們做的是大流量網(wǎng)關(guān)，100G 流量，pps 實(shí)際是5000w pps 左右，我們路由表項(xiàng)總共是5000w。

2 當(dāng)時(shí)采用數(shù)據(jù)結(jié)構(gòu)是hash list，路由規(guī)模還會(huì)不斷增大，但不能無(wú)腦增加hash桶，這個(gè)會(huì)增加內(nèi)存，本身當(dāng)時(shí)網(wǎng)關(guān)內(nèi)存就不是很充裕，所以這里要把list換成紅黑樹(shù)。

3 ?但之前l(fā)ist都是用RCU鎖（因?yàn)殒湵聿僮骺梢栽踊?4位指針））實(shí)現(xiàn)多核并發(fā)訪問(wèn)，但紅黑樹(shù)這種樹(shù)形結(jié)構(gòu)要實(shí)現(xiàn)無(wú)鎖多核并發(fā)一直是比較困難的點(diǎn)，每次變更可能會(huì)產(chǎn)生多次位移（旋轉(zhuǎn)）操作，多個(gè)操作比較困實(shí)現(xiàn)原子化。

4 ?最終想到一個(gè)比較好方法是雙份指針，用空間換時(shí)間，紅黑樹(shù)維護(hù)兩份指針（骨架），當(dāng)前使用的active指針，更新操作backup指針，等更新backup指針后，再原子交換根節(jié)點(diǎn)，這樣不妨礙其他核讀，然后再同步指針拓?fù)潢P(guān)系到備份指針。

跳表（skip list）

核心點(diǎn)：

1 跳表本質(zhì)上是對(duì)鏈表的一種優(yōu)化，通過(guò)逐層跳步采樣的方式構(gòu)建索引，以加快查找速度。使用概率均衡的思路，確定新插入節(jié)點(diǎn)的層數(shù)，使其滿足集合分布，在保證相似的查找效率簡(jiǎn)化了插入實(shí)現(xiàn)。

2 skiplist的復(fù)雜度和紅黑樹(shù)一樣，而且實(shí)現(xiàn)起來(lái)更簡(jiǎn)單；

3 在并發(fā)環(huán)境下skiplist有另外一個(gè)優(yōu)勢(shì)，紅黑樹(shù)在插入和刪除的時(shí)候可能需要做一些rebalance的操作，這樣的操作可能會(huì)涉及到整個(gè)樹(shù)的其他部分，而skiplist的操作顯然更加局部性一些，鎖需要盯住的節(jié)點(diǎn)更少，因此在這樣的情況下性能好一些；

使用場(chǎng)景：

1 HBase MemStore 的數(shù)據(jù)結(jié)構(gòu)：HBase 屬于 LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫(kù)，LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫(kù)有個(gè)特點(diǎn)，實(shí)時(shí)寫入的數(shù)據(jù)先寫入到內(nèi)存，內(nèi)存達(dá)到閾值往磁盤 flush 的時(shí)候，會(huì)生成類似于 StoreFile 的有序文件，而跳表恰好就是天然有序的，所以在 flush 的時(shí)候效率很高。

2 Google 開(kāi)源的 key/value 存儲(chǔ)引擎 LevelDB 以及 Facebook 基于 LevelDB 優(yōu)化的 RocksDB 都是 LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫(kù)，他們內(nèi)部的 MemTable 都是使用了跳表這種數(shù)據(jù)結(jié)構(gòu)；

3 ?redis的sorted set內(nèi)部實(shí)現(xiàn)；

B/B 樹(shù)（平衡多路查找樹(shù)）

核心點(diǎn)：

1 Ｂ樹(shù)和Ｂ＋樹(shù)的出現(xiàn)是因?yàn)榇疟PＩＯ；眾所周知，ＩＯ操作的效率很低，那么，當(dāng)在大量數(shù)據(jù)存儲(chǔ)中，查詢時(shí)我們不能一下子將所有數(shù)據(jù)加載到內(nèi)存中，只能逐一加載磁盤頁(yè)，每個(gè)磁盤頁(yè)對(duì)應(yīng)樹(shù)的節(jié)點(diǎn)。造成大量磁盤ＩＯ操作（最壞情況下為樹(shù)的高度）。平衡二叉樹(shù)由于樹(shù)深度過(guò)大而造成磁盤IO讀寫過(guò)于頻繁，進(jìn)而導(dǎo)致效率低下。所以，我們?yōu)榱藴p少磁盤ＩＯ的次數(shù)，就你必須降低樹(shù)的深度，將“瘦高”的樹(shù)變得“矮胖”。一個(gè)基本的想法就是：

每個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)元素
摒棄二叉樹(shù)結(jié)構(gòu)，采用多叉樹(shù)

這樣就引出來(lái)了一個(gè)新的查找樹(shù)結(jié)構(gòu) ——多路查找樹(shù)（multi-way search tree）。一顆平衡多路查找樹(shù)自然可以使得數(shù)據(jù)的查找效率保證在O(logN)這樣的對(duì)數(shù)級(jí)別上。

2 B-Tree是為磁盤等外存儲(chǔ)設(shè)備設(shè)計(jì)的一種平衡查找樹(shù)。系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存時(shí)是以磁盤塊（block）為基本單位的，位于同一個(gè)磁盤塊中的數(shù)據(jù)會(huì)被一次性讀取出來(lái)，B Tree是在B-Tree基礎(chǔ)上 ? 的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)；

3 B Tree 只有葉子結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，所有非葉子結(jié)點(diǎn)（內(nèi)部結(jié)點(diǎn)）不存儲(chǔ)數(shù)據(jù)，只有指向子結(jié)點(diǎn)的指針。葉子結(jié)點(diǎn)均在同一層，且葉子結(jié)點(diǎn)之間類似于鏈表結(jié)構(gòu)，即有指針指向下一個(gè)葉子結(jié)點(diǎn)；

4 由于B 樹(shù)在內(nèi)部節(jié)點(diǎn)上不包含數(shù)據(jù)信息，因此在內(nèi)存頁(yè)中能夠存放更多的key。數(shù)據(jù)存放的更加緊密，具有更好的空間局部性。因此訪問(wèn)葉子節(jié)點(diǎn)上關(guān)聯(lián)的數(shù)據(jù)也具有更好的緩存命中率

5 B 樹(shù)的葉子結(jié)點(diǎn)都是相鏈的，因此對(duì)整棵樹(shù)的便利只需要一次線性遍歷葉子結(jié)點(diǎn)即可。而且由于數(shù)據(jù)順序排列并且相連，所以便于區(qū)間查找和搜索。而B(niǎo)樹(shù)則需要進(jìn)行每一層的遞歸遍歷，相鄰的元素可能在內(nèi)存中不相鄰，所以緩存命中性沒(méi)有B 樹(shù)好，B樹(shù)也有優(yōu)點(diǎn)，其優(yōu)點(diǎn)在于：由于B樹(shù)的每一個(gè)節(jié)點(diǎn)都包含key和value，因此經(jīng)常訪問(wèn)的元素可能離根節(jié)點(diǎn)更近，因此訪問(wèn)也更迅速。

使用場(chǎng)景：

MySQL InnoDB存儲(chǔ)引擎就是用B Tree實(shí)現(xiàn)：

每個(gè)級(jí)別的所有頁(yè)面都相互雙向鏈接，并且在每個(gè)頁(yè)面內(nèi)，記錄按升序單獨(dú)鏈接。非葉頁(yè)包含“指針”（包含子頁(yè)碼）而不是非關(guān)鍵行數(shù)據(jù)。

算法

一些的重要算法，很多算法在工作中都經(jīng)常使用；

排序算法核心：

核心點(diǎn):

穩(wěn)定性得好處：從一個(gè)鍵上排序，然后再?gòu)牧硪粋€(gè)鍵上排序，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用，多重key值排序；
大多數(shù)語(yǔ)言的標(biāo)準(zhǔn)庫(kù)排序算法是快速排序：

核心原理是通過(guò)選擇一個(gè)元素作為基點(diǎn)，然后通過(guò)與基點(diǎn)比較，根據(jù)比較結(jié)果進(jìn)行分類（移動(dòng)元素），再遞歸下去，直到不能遞歸為止，這樣整個(gè)數(shù)組就有序了；

標(biāo)準(zhǔn)庫(kù)中的sort，是通過(guò)先快排，遞歸深度超過(guò)一個(gè)閥值就改成堆排，然后對(duì)最后的幾個(gè)進(jìn)行插入排序來(lái)實(shí)現(xiàn)的；

快速排序復(fù)雜度是nlogn，但實(shí)際綜合性能最好；

原因：

1. 快速排序中，每次數(shù)據(jù)移動(dòng)都意味著該數(shù)據(jù)距離它正確的位置越來(lái)越近，而在其他同等級(jí)排序中，類似將堆尾部的數(shù)據(jù)移到堆頂這樣的操作只會(huì)使相應(yīng)的數(shù)據(jù)遠(yuǎn)離它正確的位置，后續(xù)必然有一些操作再將其移動(dòng)，即“做了好多無(wú)用功”。

2. 快速排序通常比其他排序算法快得多，因?yàn)樗偷剡\(yùn)行，無(wú)需創(chuàng)建任何輔助數(shù)組來(lái)保存臨時(shí)值。與歸并排序之類的東西相比，這可能是一個(gè)巨大的優(yōu)勢(shì)，因?yàn)榉峙浜腿∠峙漭o助數(shù)組所需的時(shí)間可能很明顯。就地操作還提高了快速排序的局部性。?????????????????

? ? ? ? ? ?

增量型排序（比如實(shí)時(shí)計(jì)算topN這種）采用是堆排序（最小堆或者最大堆）；

字符串匹配算法

核心點(diǎn)：

盡可能利用一切可以利用信息，比如模式串本身信息，后綴信息，比較后的殘余信息等；
掌握正則表達(dá)式語(yǔ)法；
理解模式匹配：KMP、Boyer-Moore算法；

使用場(chǎng)景：

1 ?linux文本處理三劍客 grep ，awk， sed 等用了大量正則表達(dá)式算法。

2 文本編輯器使用大量字符串匹配算法。

圖論

核心點(diǎn)：

實(shí)際工作中網(wǎng)絡(luò)會(huì)用到部分圖算法，比如網(wǎng)絡(luò)拓?fù)渑判?，OSPF路由協(xié)議（最短路徑）；
如果你要參加ACM or OJ 這種比賽，可以學(xué)一些常用圖算法：最短路徑、最小生成樹(shù)、網(wǎng)絡(luò)流建模；

使用場(chǎng)景：

1 游戲開(kāi)發(fā)中會(huì)用到大量的圖算法：路徑搜索算法（BFS,DFS,A*)；

2 導(dǎo)航軟件會(huì)用到大量的圖算法：最短路徑，路徑搜索算法；

3 網(wǎng)絡(luò)bridge的STP協(xié)議用到最小生成樹(shù)算法；

4 網(wǎng)頁(yè)排名中PageRank 算法；

搜索(遍歷) 剪枝

核心點(diǎn):

核心是減少解空間，窮舉排除法；
核心是減少解空間，遞歸判斷；

使用場(chǎng)景：

1 ?深度優(yōu)先搜索、廣度優(yōu)先搜索、A*算法、回溯算法、蒙特卡洛樹(shù)搜索；

二分法

核心點(diǎn)：

前置條件，需要有序；
全面考慮算法邊界點(diǎn)，實(shí)現(xiàn)細(xì)節(jié)，溢出等問(wèn)題；
不能在線增量計(jì)算；

使用場(chǎng)景：

1 用二分法計(jì)算方程近似解；

2 機(jī)器學(xué)習(xí)二分分類算法；

3?有序序列快速查找場(chǎng)景;

分治算法

核心點(diǎn):

一是自頂向下分解問(wèn)題，二是自底向上抽象合并；
將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之；?

使用場(chǎng)景：

1 二分搜索，排序算法(快速排序，歸并排序)，動(dòng)態(tài)規(guī)劃；

2 傅立葉變換(快速傅立葉變換)；

3 程序模塊化設(shè)計(jì)；

動(dòng)態(tài)規(guī)劃（DP）

核心點(diǎn):

實(shí)際工作中很少用到，工作多年，從來(lái)沒(méi)有在工作中使用過(guò)動(dòng)態(tài)規(guī)劃。
核心是了解其思想和原理:

動(dòng)態(tài)規(guī)劃最核心的思想，就在于拆分子問(wèn)題，記住過(guò)往，減少重復(fù)計(jì)算；
深刻理解最優(yōu)子結(jié)構(gòu)，重疊子問(wèn)題，狀態(tài)轉(zhuǎn)移方程，無(wú)后效性，以及邊界條件；
熟悉各種類型DP特點(diǎn)，普通DP，區(qū)間DP，樹(shù)形DP，數(shù)位DP，狀態(tài)壓縮DP等；

應(yīng)對(duì)面試，刷幾道題就行，一般面試很少出動(dòng)態(tài)規(guī)劃的題，校招可能會(huì)出，社招基本上不會(huì)出；
如果你要參加ACM or OJ 這種比賽，必須掌握, 這個(gè)區(qū)分菜鳥(niǎo)的分界點(diǎn)。

使用場(chǎng)景：

1 切割鋼條問(wèn)題, Floyd最短路問(wèn)題,最大不下降子序列,矩陣鏈乘,凸多邊形三角剖分,0-1背包,最長(zhǎng)公共子序列,最優(yōu)二分搜索樹(shù)；

2 運(yùn)籌學(xué)，經(jīng)濟(jì)學(xué)等；

最后總結(jié)

程序 = 數(shù)據(jù)結(jié)構(gòu) 算法?? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ?---Niklaus EmilWirth

程序本質(zhì)是數(shù)據(jù)結(jié)構(gòu) 算法，任何一門語(yǔ)言都可以這樣理解，這個(gè)公式對(duì)計(jì)算機(jī)科學(xué)的影響程度足以類似物理學(xué)中愛(ài)因斯坦的“E=MC^2”——一個(gè)公式展示出了程序的本質(zhì)。

其實(shí)在工作中，最重要是設(shè)計(jì)好數(shù)據(jù)結(jié)構(gòu)，因?yàn)樵谠O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，就是性能和實(shí)現(xiàn)難度的權(quán)衡，程序當(dāng)然是越簡(jiǎn)單越好，但為了性能，有時(shí)候不得不設(shè)計(jì)出像紅黑樹(shù)這種復(fù)雜數(shù)據(jù)結(jié)構(gòu)。

希望我們都可以掌握好算法核心思想，和常見(jiàn)數(shù)據(jù)結(jié)構(gòu)精妙設(shè)計(jì)，幫助我們?cè)诿嬖嚭凸ぷ髦写蚝脠?jiān)實(shí)的基礎(chǔ)；