數(shù)組
- 數(shù)組是一種非常常見的線性數(shù)據(jù)結(jié)構(gòu)
- 它最大的特點(diǎn)是使用一組連續(xù)的內(nèi)存空間，存儲(chǔ)一組相同類型的數(shù)據(jù)：
數(shù)組的存儲(chǔ)形式.jpg
- 之所以強(qiáng)調(diào)相同類型盏筐，是因?yàn)橄嗤念愋偷臄?shù)據(jù)會(huì)占據(jù)相等的存儲(chǔ)空間琢融，因此就可以通過(guò)計(jì)算直接獲取內(nèi)存地址吏奸。
- 優(yōu)點(diǎn)：數(shù)組最大的特性，是支持隨機(jī)訪問烈钞，即可以通過(guò)索引直接訪問某個(gè)數(shù)據(jù)
- 數(shù)組的訪問性能非常高毯欣，還有一個(gè)原因是在硬件層面有CPU的高速緩存（cache）提升性能
- 缺點(diǎn)：數(shù)組的添加酗钞、刪除的性能很低砚作，因?yàn)闀?huì)涉及大量的數(shù)據(jù)搬移工作嘹锁。
- 所以你會(huì)發(fā)現(xiàn)领猾，go 中給數(shù)組和切片的操作很少，低性能可能是其中的原因之一
- 這也是為什么 go 中指定 slice 長(zhǎng)度可以提升性能（減少追加數(shù)據(jù)時(shí)的數(shù)據(jù)搬移工作）
鏈表
- 鏈表是另一種非成傩ⅲ基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)韭山，與數(shù)組不同钱磅，它使用零散的內(nèi)存存儲(chǔ)數(shù)據(jù)：
數(shù)組和鏈表的存儲(chǔ).jpg
單鏈表.jpg
- 由于它的存儲(chǔ)方式和數(shù)組完全不同，所以它和數(shù)組的特性完全不同：
- 優(yōu)點(diǎn)：高效的插入和刪除
鏈表的插入和刪除.jpg
- 缺點(diǎn)：鏈表的查找非常低效褪迟，只能依次遍歷所有節(jié)點(diǎn)
- 在 go 中味赃，container 包里有雙向鏈表心俗、雙向循環(huán)鏈表等容器供我們使用城榛，下面是鏈表的部分方法：
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveAfter(e, mark *Element)
func (l *List) MoveToFront(e *Element)
func (l *List) MoveToBack(e *Element)
func (l *List) Front() *Element
func (l *List) Back() *Element
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
func (l *List) PushFront(v interface{}) *Element
func (l *List) PushBack(v interface{}) *Element
- 單純的鏈表在實(shí)際編程中很少用到狠持，但是如果我們對(duì)鏈表進(jìn)行升級(jí)喘垂，給一些額外的結(jié)構(gòu)正勒，它就會(huì)有非常廣泛的應(yīng)用楚午。
- 簡(jiǎn)單的變型有：雙向鏈表矾柜、循環(huán)鏈表等，復(fù)雜的變型有：紅黑樹丧荐、B+樹等虹统。這種變型非常重要车荔，其中就包括 redis 中實(shí)現(xiàn) zset 的跳表：
跳表-二級(jí)索引.jpg
棧
- 一種操作受到限制的線性表忧便，最大的特點(diǎn)是后進(jìn)先出
- 椫樵觯可以用數(shù)組或者鏈表實(shí)現(xiàn)
- 棧只有兩種操作：入棧和出棧
棧.jpg
- 特定的數(shù)據(jù)結(jié)構(gòu)是特定使用場(chǎng)景的抽象
- 對(duì)于棧來(lái)說(shuō)，主要的使用場(chǎng)景有：括號(hào)匹配凝垛，算數(shù)運(yùn)算苔严，瀏覽器的前進(jìn)后退功能等
- 當(dāng)然，最常見的還是編程中的函數(shù)調(diào)用棧：
def sum(a,b):
return a + b
if __name__ == '__main__':
print(sum(1,2))
下面的圖片展示了這個(gè)程序執(zhí)行的過(guò)程：
函數(shù)調(diào)用棧覆旭，省略了變量名
隊(duì)列
- 隊(duì)列也是一種操作受限的線性表型将，它的特性是先進(jìn)先出
棧和隊(duì)列.jpg
- 隊(duì)列也只有兩種主要操作：從隊(duì)尾入隊(duì)和從隊(duì)首出隊(duì)
- 隊(duì)列也可以有變型：循環(huán)隊(duì)列、阻塞隊(duì)列等：
循環(huán)隊(duì)列.jpg
阻塞隊(duì)列.jpg
- 隊(duì)列可以非常方便地實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者模型腕铸，應(yīng)用有消息隊(duì)列中間件狠裹。
散列表（哈希表）
- 散列表依賴于數(shù)組支持依照下標(biāo)隨機(jī)訪問的特性
- 散列表由三個(gè)部分組成：鍵涛菠、散列函數(shù) 和 散列值俗冻。這個(gè)的過(guò)程是迄薄，鍵通過(guò)散列函數(shù)的計(jì)算得到散列值噪奄，然后去尋找這個(gè)值代表的響應(yīng)的地址：
散列
- 非常常見的一個(gè)問題是勤篮，如果多個(gè)鍵的散列值相同（散列沖突）都毒，該怎么辦？常見的解決辦法有兩種：
- 開放尋址法：
散列沖突-開放尋址法.jpg
- 鏈表法
散列沖突-鏈表法.jpg
- 上面的方法都是最基礎(chǔ)的解決方法碰缔，實(shí)際上账劲，根據(jù)場(chǎng)景的不同，會(huì)有很多種解決方案金抡。例如瀑焦，將鏈表法后接的鏈表設(shè)計(jì)成紅黑樹，可以防止哈希碰撞攻擊榛瓮。
- 你會(huì)發(fā)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)的使用不是孤立的巫击，多種數(shù)據(jù)結(jié)構(gòu)的組合禀晓，會(huì)有超乎想象的結(jié)果。
在這些組合中坝锰，哈希+鏈表就是一個(gè)包打天下的萬(wàn)金油組合粹懒，redis中的zset就是這樣。
樹
- 樹是一種非線性表結(jié)構(gòu)顷级，可以用于表示一對(duì)多的關(guān)系：
樹
-
樹中有一些概念用于描述這個(gè)結(jié)構(gòu)：
樹的描述 - 樹有很多類型凫乖，其中最簡(jiǎn)單的是二叉樹，因?yàn)槎鏄涞男再|(zhì)簡(jiǎn)單，且方便存儲(chǔ)帽芽。
- 樹有很多應(yīng)用删掀，其中就有大家最為熟知的B+樹:
B+樹
-
還有一種比較有意思的應(yīng)用：Trie樹，這個(gè)數(shù)據(jù)結(jié)構(gòu)可以幫助我們實(shí)現(xiàn)關(guān)鍵詞提示功能：
搜索關(guān)鍵詞提示
Trie樹的結(jié)構(gòu)是這樣的：
Trie樹
在這個(gè)樹中嚣镜，存儲(chǔ)了“hello”爬迟、“her”、“hi”菊匿、“how”付呕、“see”、“so” 幾個(gè)查找關(guān)鍵字跌捆，當(dāng)用戶輸入一個(gè)特定字符的時(shí)候徽职，Trie樹會(huì)搜索相關(guān)的節(jié)點(diǎn)，并遍歷到樹的葉子節(jié)點(diǎn)佩厚，途徑的所有路徑都會(huì)被記錄下來(lái)姆钉，用于關(guān)鍵字提示：
Trie樹搜索
實(shí)際上，輸入法的自動(dòng)補(bǔ)全抄瓦，IDE的代碼的自動(dòng)補(bǔ)全潮瓶，瀏覽器網(wǎng)址輸入的自動(dòng)補(bǔ)全，都使用了這種數(shù)據(jù)結(jié)構(gòu)钙姊。
圖
- 圖用于表示一種多對(duì)多關(guān)系
圖
- 多對(duì)多的關(guān)系很比較復(fù)雜毯辅，所以圖的種類也比較多，大體來(lái)說(shuō)有無(wú)向圖煞额、有向圖思恐、帶權(quán)圖等
有向圖.jpg
帶權(quán)圖.jpg
- 圖有兩種存儲(chǔ)方法：使用鄰接矩陣 和 使用鄰接表
圖存儲(chǔ)-鄰接矩陣.jpg
- 臨接矩陣的優(yōu)點(diǎn)：存儲(chǔ)方式簡(jiǎn)單、直接膊毁，可以高效地獲取兩個(gè)點(diǎn)之間的關(guān)系
- 缺點(diǎn)：
1胀莹、如果是無(wú)向圖，鄰接矩陣是關(guān)于主軸對(duì)稱的婚温，這會(huì)浪費(fèi)一般的空間
2描焰、如果各個(gè)點(diǎn)之間的關(guān)聯(lián)非常稀疏，使用鄰接矩陣會(huì)浪費(fèi)大量空間栅螟。例如微信的好友關(guān)系
圖存儲(chǔ)-鄰接表.jpg
優(yōu)點(diǎn)
1栈顷、比較節(jié)省存儲(chǔ)空間
2、你可以根據(jù)業(yè)務(wù)場(chǎng)景改造鄰接表嵌巷，以提升特定場(chǎng)景下的性能。例如將鏈表改造成紅黑樹室抽。缺點(diǎn)
1搪哪、對(duì)緩存不友好
2、鄰接表的查找比鄰接矩陣更加耗時(shí)
3坪圾、如果存儲(chǔ)的圖是有向圖晓折，又要統(tǒng)計(jì)點(diǎn)的出度和入度惑朦，需要添加逆鄰接表圖的應(yīng)用非常廣泛，如保存好友關(guān)系漓概、最短路徑規(guī)劃等
