摘要：每個(gè)列表中的數(shù)據(jù)項(xiàng)稱為元素。棧被稱為一種后入先出，的數(shù)據(jù)結(jié)構(gòu)。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。不包含任何成員的集合稱為空集，全集則是包含一切可能成員的集合。因此二叉搜索樹(shù)需要平衡，即左右子樹(shù)高度要相近。

樓樓非計(jì)算機(jī)專業(yè)，但是對(duì)計(jì)算機(jī)也還算喜歡。個(gè)人理解若有偏差，歡迎各位批評(píng)指正！

對(duì)于數(shù)據(jù)結(jié)構(gòu)和算法一直是我的薄弱環(huán)節(jié)，相信大多數(shù)前端工程師可能多少會(huì)有些這方面的弱點(diǎn)，加上數(shù)據(jù)結(jié)構(gòu)和算法本來(lái)就有些枯燥，立下個(gè)flag，三天過(guò)后拋之腦后的也時(shí)有發(fā)生，好了，收起老媽子的叨叨叨，畢竟樓樓還是個(gè)美少女，哈哈哈~

在JS中，我所知的稍微復(fù)雜點(diǎn)的數(shù)據(jù)結(jié)構(gòu)有數(shù)組和對(duì)象。

但是統(tǒng)觀大多數(shù)語(yǔ)言，就會(huì)發(fā)現(xiàn)自己知道的太少了，當(dāng)然以下涉及到的我們可能會(huì)用的很少。但是個(gè)人認(rèn)為這些是思想上的沉淀，所發(fā)生的的變化帶給自己的影響也將會(huì)是潛移默化的，就當(dāng)是潤(rùn)物細(xì)無(wú)聲了，哈哈哈~

樓樓借鑒了數(shù)據(jù)結(jié)構(gòu)與算法JavaScript描述一書(shū)，在寫(xiě)這篇帖子時(shí)~

==開(kāi)始----------------------------------------------------------------------------------------------==

數(shù)組：

一個(gè)存儲(chǔ)元素的線性集合（collection），元素可以通過(guò)索引來(lái)任意存取，索引通常是數(shù)字，用來(lái)計(jì)算元素之間存儲(chǔ)位置的偏移量。

數(shù)組的那些方法（js）

es6新增
Array.from()//偽數(shù)組轉(zhuǎn)數(shù)組  不支持的話我們還可以通過(guò)call和apply改變this指向，從而達(dá)到偽數(shù)組調(diào)用數(shù)組的方法
Array.of() //將一組值，轉(zhuǎn)換為數(shù)組
Array.prototype.copyWithin(target, start = 0, end = this.length) //指定位置的成員復(fù)制到其他位置（會(huì)覆蓋原有成員），然后返回當(dāng)前數(shù)組。也就是說(shuō)，使用這個(gè)方法，會(huì)修改當(dāng)前數(shù)組。
    target（必需）：從該位置開(kāi)始替換數(shù)據(jù)。如果為負(fù)值，表示倒數(shù)。
    start（可選）：從該位置開(kāi)始讀取數(shù)據(jù)，默認(rèn)為 0。如果為負(fù)值，表示倒數(shù)。
    end（可選）：到該位置前停止讀取數(shù)據(jù)，默認(rèn)等于數(shù)組長(zhǎng)度。如果為負(fù)值，表示倒數(shù)。
Array.find(item => item > 0) 找到數(shù)組中符合條件的元素返回，如果沒(méi)有符合條件的元素返回undefine
Array.findIndex(item => item > 0) 返回第一個(gè)符合條件的數(shù)組成員的位置，如果所有成員都不符合條件，則返回-1。
Array.fill() //使用一個(gè)值來(lái)填充數(shù)組
entries()【對(duì)鍵值】 keys()【對(duì)鍵】 values()【對(duì)值】 用于遍歷數(shù)組。他們都返回一個(gè)遍歷器對(duì)象。
Array.includes() 這個(gè)方法必須力推，返回布爾值，表示某個(gè)數(shù)組是否包含特定的值，與字符串includes方法類似
    
另外還有這些，就不一一贅述了
join()  push()和pop() shift() 和 unshift() sort()  reverse()  concat()  slice()
splice()  indexOf()和 lastIndexOf() （ES5新增） forEach() （ES5新增）  map() （ES5新增）
filter() （ES5新增）  every() （ES5新增）  some() （ES5新增） reduce()和 reduceRight() （ES5新增）

數(shù)組中較為復(fù)雜的應(yīng)為二維和多維數(shù)組。

JavaScript 只支持一維數(shù)組，但是通過(guò)在數(shù)組里保存數(shù)組元素的方式，可以輕松創(chuàng)建多維數(shù)組。

列表

列表是一組有序的數(shù)據(jù)。每個(gè)列表中的數(shù)據(jù)項(xiàng)稱為元素。在 JavaScript 中，列表中的元素可以是任意數(shù)據(jù)類型。列表中可以保存多少元素并沒(méi)有事先限定，實(shí)際使用時(shí)元素的數(shù)量受到程序內(nèi)存的限制。列表有前有后（分別對(duì)應(yīng) front 和 end）。

棧

棧是一種特殊的列表，棧內(nèi)的元素只能通過(guò)列表的一端訪問(wèn)，這一端稱為棧頂。棧被稱為一種后入先出（LIFO，last-in-first-out）的數(shù)據(jù)結(jié)構(gòu)。入棧使用 push() 方法，出棧使用 pop() 方法。

隊(duì)列

隊(duì)列是一種先進(jìn)先出（First-In-First-Out，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)。插入操作也叫做入隊(duì)，刪除操作也叫做出隊(duì)。入隊(duì)操作在隊(duì)尾插入新元素，出隊(duì)操作刪除隊(duì)頭的元素。

鏈表

==背景：在很多編程語(yǔ)言中，數(shù)組的長(zhǎng)度是固定的，所以當(dāng)數(shù)組已被數(shù)據(jù)填滿時(shí)，再要加入新的元素就會(huì)非常困難。在數(shù)組中，添加和刪除元素也很麻煩，因?yàn)樾枰獙?shù)組中的其他元素向前或向后平移，以反映數(shù)組剛剛進(jìn)行了添加或刪除操作。然而JavaScript 的數(shù)組并不存在上述問(wèn)題，因?yàn)槭褂?split() 方法不需要再訪問(wèn)數(shù)組中的其他元素了。==
鏈表是由一組節(jié)點(diǎn)組成的集合。每個(gè)節(jié)點(diǎn)都使用一個(gè)對(duì)象的引用指向它的后繼。指向另一個(gè)節(jié)點(diǎn)的引用叫做鏈。

我們常說(shuō)的鏈表是單向鏈表

雙向鏈表示意圖：

循環(huán)鏈表示意圖

通過(guò)這三個(gè)圖片希望你對(duì)鏈表有初步認(rèn)知。

字典

字典是一種以鍵 - 值對(duì)形式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，一般大家談到字典會(huì)說(shuō)到電話簿，我覺(jué)得在JS里他更像是Object類，一個(gè)鍵對(duì)應(yīng)一個(gè)值。但是很多教材中會(huì)說(shuō)，Dictionay 類的基礎(chǔ)是 Array 類，而不是 Object 類。OK，That"s OK! 畢竟JavaScript中萬(wàn)物皆對(duì)象。

散列

散列是一種常用的數(shù)據(jù)存儲(chǔ)技術(shù)，散列后的數(shù)據(jù)可以快速地插入或取用。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。在散列表上插入刪除和取用數(shù)據(jù)都非?？?，但是對(duì)于查找操作來(lái)說(shuō)卻效率低下，比如查找一組數(shù)據(jù)中的最大值和最小值。這些操作得求助于其他數(shù)據(jù)結(jié)構(gòu)，二叉查找樹(shù)就是一個(gè)很好的選擇。

即使使用一個(gè)高效的散列函數(shù)，仍然存在將兩個(gè)鍵映射成同一個(gè)值的可能，這種現(xiàn)象稱為碰撞（collision）

==hashTable的實(shí)現(xiàn)就是典型的基于散列的一種數(shù)據(jù)結(jié)構(gòu)，在這里有興趣的話還可以去看一下霍納算法==

當(dāng)散列函數(shù)對(duì)于多個(gè)輸入產(chǎn)生同樣的輸出時(shí)，就產(chǎn)生了碰撞。

碰撞的解決方法：開(kāi)鏈法和線性探測(cè)法

開(kāi)鏈法是指實(shí)現(xiàn)散列表的底層數(shù)組中，每個(gè)數(shù)組元素又是一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，比如另一個(gè)數(shù)組，這樣就能存儲(chǔ)多個(gè)鍵了。使用這種技術(shù)，即使兩個(gè)鍵散列后的值相同，依然被保存在同樣的位置，只不過(guò)它們?cè)诘诙€(gè)數(shù)組中的位置不一樣罷了。

線性探測(cè)法隸屬于一種更一般化的散列技術(shù)：開(kāi)放尋址散列。當(dāng)發(fā)生碰撞時(shí)，線性探測(cè)法檢查散列表中的下一個(gè)位置是否為空。如果為空，就將數(shù)據(jù)存入該位置；如果不為空，則繼續(xù)檢查下一個(gè)位置，直到找到一個(gè)空的位置為止。該技術(shù)是基于這樣一個(gè)事實(shí)：每個(gè)散列表都會(huì)有很多空的單元格，可以使用它們來(lái)存儲(chǔ)數(shù)據(jù)。

集合

集合是由一組無(wú)序但彼此之間又有一定相關(guān)性的成員構(gòu)成的，每個(gè)成員在集合中只能出現(xiàn)一次。

? 不包含任何成員的集合稱為空集，全集則是包含一切可能成員的集合。
? 如果兩個(gè)集合的成員完全相同，則稱兩個(gè)集合相等。
? 如果一個(gè)集合中所有的成員都屬于另外一個(gè)集合，則前一集合稱為后一集合的子集。

對(duì)集合的基本操作有下面幾種。

? 并集
將兩個(gè)集合中的成員進(jìn)行合并，得到一個(gè)新集合。
? 交集
兩個(gè)集合中共同存在的成員組成一個(gè)新的集合。
? 補(bǔ)集
屬于一個(gè)集合而不屬于另一個(gè)集合的成員組成的

樹(shù)：

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式來(lái)存儲(chǔ)數(shù)據(jù)。

樹(shù)：

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式來(lái)存儲(chǔ)數(shù)據(jù)。
其中樹(shù)里面常被提起的應(yīng)當(dāng)是二叉樹(shù)。提起二叉樹(shù)補(bǔ)充一些，這是我一個(gè)朋友寫(xiě)的，感覺(jué)寫(xiě)的比較好。拿出來(lái)分享一下~
表達(dá)順序集比較合適的數(shù)據(jù)結(jié)構(gòu)樹(shù)。。。樹(shù)最合適。為什么？

    二叉搜索樹(shù)天然可用于排序的二分查找，左子樹(shù)小于根節(jié)點(diǎn)，右子樹(shù)大于根節(jié)點(diǎn)，樹(shù)的高度即為最大搜索次數(shù)，是很小的常數(shù)。
    二叉搜索樹(shù) 改進(jìn)為 二叉平衡搜索樹(shù)
    二叉搜索樹(shù)有什么劣勢(shì)？樹(shù)的構(gòu)建受數(shù)據(jù)集合的順序影響，極端情況下，蛻化為單項(xiàng)鏈表，失去二叉樹(shù)的意義，檢索復(fù)雜度退化到順序遍歷。
    因此二叉搜索樹(shù)需要平衡，即左右子樹(shù)高度要相近。
二叉平衡搜索樹(shù) 改進(jìn)為 B樹(shù)
    搜索復(fù)雜度為 log2 (n)，要想進(jìn)一步降低搜索次數(shù)即樹(shù)高度，怎么辦？增大對(duì)數(shù)的底，底越大，對(duì)數(shù)值越小。
    因此改進(jìn)為 m 階樹(shù)，并對(duì)非根節(jié)點(diǎn)的key個(gè)數(shù)進(jìn)行約定(m/2 ~ m)，成為B樹(shù)。
B樹(shù) 改進(jìn)為 B+樹(shù)
    B樹(shù)的劣勢(shì)：B樹(shù)每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)記錄本身或指針，內(nèi)存空間占用大，反復(fù)換頁(yè)導(dǎo)致訪存低效；典型業(yè)務(wù)場(chǎng)景查詢的都是一段范圍的數(shù)據(jù)記錄，不僅僅是單條，B樹(shù)比較慢。
    改進(jìn)措施：樹(shù)的非葉子節(jié)點(diǎn)不包含數(shù)據(jù)記錄，葉子節(jié)點(diǎn)包含數(shù)據(jù)記錄的指針（聚集索引的key），整體減小索引樹(shù)占用的內(nèi)存，提高訪存效率；所有數(shù)據(jù)記錄被葉子節(jié)點(diǎn)覆蓋，葉子節(jié)點(diǎn)天然是有序的，以單項(xiàng)鏈表連接，很方便遍歷一段范圍的記錄。
改進(jìn)后即為 B+ 樹(shù)。mariadb-10.3使用的即為B+樹(shù)。
B+樹(shù) 改進(jìn)為 B*樹(shù)
    B+樹(shù)的劣勢(shì)：每個(gè)非葉子節(jié)點(diǎn)可能只包含 m/2 個(gè)key，有一半空閑，內(nèi)存使用率低。
    改進(jìn)措施：將非葉子節(jié)點(diǎn)的最小key數(shù)增加為 2m/3，提高內(nèi)存使用率。付出的代價(jià)是需要對(duì)非葉子節(jié)點(diǎn)增加指向兄弟的指針，以便于節(jié)點(diǎn)拆分、合并。
    改進(jìn)后即為 B* 樹(shù)。
基于B+樹(shù)的一些推論
select * from xxx offset N limit M，不用特別在意N對(duì)效率的影響。如果N可能很大，例如過(guò)萬(wàn)，區(qū)分維護(hù)冷、熱數(shù)據(jù)，確保N不會(huì)太大。
select * from xxx order by a order by b，聯(lián)合索引受索引樹(shù)的影響，天然要求左匹配原則，能利用到聯(lián)合索引時(shí)查找效率很高。
主鍵用 uuid 還是 int 更好？innobase數(shù)據(jù)引擎下單調(diào)增長(zhǎng)的 int 更好。uuid 32字節(jié)，用于索引必然比 int 4字節(jié)大，索引樹(shù)占用的內(nèi)存越大訪存效率越低，所以 uuid 差；innobase的文件物理存儲(chǔ)結(jié)構(gòu)內(nèi)涵為主鍵索引（聚集索引），單調(diào)遞增的主鍵確保在連續(xù)的disk page 上不斷 append 數(shù)據(jù)，訪存效率高，而uuid導(dǎo)致新增數(shù)據(jù)隨機(jī)插入disk page，需要大量移動(dòng)數(shù)據(jù)，訪存效率低?？傮w上看uuid較差。當(dāng)然id本身也存在生成時(shí)的鎖競(jìng)爭(zhēng)等問(wèn)題。

對(duì)于樹(shù)結(jié)構(gòu)有興趣的可以再深入探討，因?yàn)檫@塊確實(shí)水比較深

圖和圖算法

圖由邊的集合及頂點(diǎn)的集合組成。