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

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲和組織數(shù)據(jù)的的方式

1. 數(shù)組

在Java中，數(shù)組是用來存放同一種數(shù)據(jù)類型的集合，注意只能存放同一種數(shù)據(jù)類型。

數(shù)組的局限性分析：

　?、佟⒉迦肼?，對于無序數(shù)組，上面我們實(shí)現(xiàn)的數(shù)組就是無序的，即元素沒有按照從大到小或者某個(gè)特定的順序排列，只是按照插入的順序排列。無序數(shù)組增加一個(gè)元素很簡單，只需要在數(shù)組末尾添加元素即可，但是有序數(shù)組卻不一定了，它需要在指定的位置插入。

　　②、查找快，當(dāng)然如果根據(jù)下標(biāo)來查找是很快的。但是通常我們都是根據(jù)元素值來查找，給定一個(gè)元素值，對于無序數(shù)組，我們需要從數(shù)組第一個(gè)元素開始遍歷，知道找到那個(gè)元素。有序數(shù)組通過特定的算法查找的速度會比無需數(shù)組快，后面我們會講各種排序算法。

　?、邸h除慢，根據(jù)元素值刪除，我們要先找到該元素所處的位置，然后將元素后面的值整體向前面移動一個(gè)位置。也需要比較多的時(shí)間。

　?、?、數(shù)組一旦創(chuàng)建后，大小就固定了，不能動態(tài)擴(kuò)展數(shù)組的元素個(gè)數(shù)。如果初始化你給一個(gè)很大的數(shù)組大小，那會白白浪費(fèi)內(nèi)存空間，如果給小了，后面數(shù)據(jù)個(gè)數(shù)增加了又添加不進(jìn)去了。

很顯然，數(shù)組雖然查找快，但是插入和刪除都比較慢，所以我們不會用數(shù)組來存儲所有的數(shù)據(jù)，那有沒有什么數(shù)據(jù)結(jié)構(gòu)插入、查找、刪除都很快，而且還能動態(tài)擴(kuò)展存儲個(gè)數(shù)大小

一維數(shù)組

如何定義數(shù)組

數(shù)據(jù)類型[] 數(shù)組名=new 數(shù)據(jù)類型[數(shù)組長度]；

? 數(shù)組類型 數(shù)組名[]=new 數(shù)組類型[數(shù)組長度]；

二維數(shù)組

定義

數(shù)組類型 [][] 數(shù)組名;

數(shù)組類型 數(shù)組 [][];

數(shù)組是可以再內(nèi)存中連續(xù)存儲多個(gè)元素的結(jié)構(gòu)。數(shù)組中的所有元素必須屬于相同的數(shù)據(jù)類型。

數(shù)組中的元素通過數(shù)組下標(biāo)進(jìn)行訪問，數(shù)組下標(biāo)從0開始。

二維數(shù)組實(shí)際上是一個(gè)一維數(shù)組，它的每個(gè)元素又是一個(gè)一維數(shù)組。

使用Array類提供的方法可以方便地對數(shù)組中的元素進(jìn)行排序、查詢等操作。

JDK1.5之后提供了增強(qiáng)for循環(huán)，可以用來實(shí)現(xiàn)對數(shù)組和集合中數(shù)據(jù)的訪問。

1. 棧

又稱為堆棧或堆疊，棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表。它按照先進(jìn)后出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。

棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。

　　由于堆疊數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作。棧也稱為后進(jìn)先出表。

這里以羽毛球筒為例，羽毛球筒就是一個(gè)棧，剛開始羽毛球筒是空的，也就是空棧，然后我們一個(gè)一個(gè)放入羽毛球，也就是一個(gè)一個(gè)push進(jìn)棧，當(dāng)我們需要使用羽毛球的時(shí)候，從筒里面拿，也就是pop出棧，但是第一個(gè)拿到的羽毛球是我們最后放進(jìn)去的。

產(chǎn)生的問題：

　　①、上面棧的實(shí)現(xiàn)初始化容量之后，后面是不能進(jìn)行擴(kuò)容的（雖然棧不是用來存儲大量數(shù)據(jù)的），如果說后期數(shù)據(jù)量超過初始容量之后怎么辦？（自動擴(kuò)容）

　　②、我們是用數(shù)組實(shí)現(xiàn)棧，在定義數(shù)組類型的時(shí)候，也就規(guī)定了存儲在棧中的數(shù)據(jù)類型，那么同一個(gè)棧能不能存儲不同類型的數(shù)據(jù)呢？（聲明為Object）

③、棧需要初始化容量，而且數(shù)組實(shí)現(xiàn)的棧元素都是連續(xù)存儲的，那么能不能不初始化容量呢？（改為由鏈表實(shí)現(xiàn)）

1. 隊(duì)列

隊(duì)列（queue）是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。

隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱為出隊(duì)。因?yàn)殛?duì)列只允許在一端插入，在另一端刪除，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又稱為先進(jìn)先出（FIFO—first in first out）線性表。

　隊(duì)列分為：

　　①、單向隊(duì)列（Queue）：只能在一端插入數(shù)據(jù)，另一端刪除數(shù)據(jù)。

　　②、雙向隊(duì)列（Deque）：每一端都可以進(jìn)行插入數(shù)據(jù)和刪除數(shù)據(jù)操作。

單向隊(duì)列實(shí)現(xiàn)

?、?、與棧不同的是，隊(duì)列中的數(shù)據(jù)不總是從數(shù)組的0下標(biāo)開始的，移除一些隊(duì)頭front的數(shù)據(jù)后，隊(duì)頭指針會指向一個(gè)較高的下標(biāo)位置，如下圖：

　?、?、我們再設(shè)計(jì)時(shí)，隊(duì)列中新增一個(gè)數(shù)據(jù)時(shí)，隊(duì)尾的指針rear 會向上移動，也就是向下標(biāo)大的方向。移除數(shù)據(jù)項(xiàng)時(shí)，隊(duì)頭指針 front 也會向下移動。那么這樣設(shè)計(jì)好像和現(xiàn)實(shí)情況相反，比如排隊(duì)買電影票，隊(duì)頭的買完票就離開了，然后隊(duì)伍整體向前移動。在計(jì)算機(jī)中也可以在隊(duì)列中刪除一個(gè)數(shù)之后，隊(duì)列整體向前移動，但是這樣做效率很差。我們選擇的做法是移動隊(duì)頭和隊(duì)尾的指針。

　　③、如果向第②步這樣移動指針，相信隊(duì)尾指針很快就移動到數(shù)據(jù)的最末端了，這時(shí)候可能移除過數(shù)據(jù)，那么隊(duì)頭會有空著的位置，然后新來了一個(gè)數(shù)據(jù)項(xiàng)，由于隊(duì)尾不能再向上移動了，那該怎么辦呢？如下圖：

　　為了避免隊(duì)列不滿卻不能插入新的數(shù)據(jù)，我們可以讓隊(duì)尾指針繞回到數(shù)組開始的位置，這也稱為“循環(huán)隊(duì)列”。

雙向隊(duì)列

雙端隊(duì)列就是一個(gè)兩端都是結(jié)尾或者開頭的隊(duì)列，?隊(duì)列的每一端都可以進(jìn)行插入數(shù)據(jù)項(xiàng)和移除數(shù)據(jù)項(xiàng)

優(yōu)先級隊(duì)列（priority queue）

是比棧和隊(duì)列更專用的數(shù)據(jù)結(jié)構(gòu)，在優(yōu)先級隊(duì)列中，數(shù)據(jù)項(xiàng)按照關(guān)鍵字進(jìn)行排序，關(guān)鍵字最?。ɑ蛘咦畲螅┑臄?shù)據(jù)項(xiàng)往往在隊(duì)列的最前面，而數(shù)據(jù)項(xiàng)在插入的時(shí)候都會插入到合適的位置以確保隊(duì)列的有序。

　　優(yōu)先級隊(duì)列 是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)，對優(yōu)先級隊(duì)列執(zhí)行的操作有：

　　（1）查找

　?。?）插入一個(gè)新元素

　?。?）刪除

　　一般情況下，查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素 。對于優(yōu)先權(quán)相同的元素，可按先進(jìn)先出次序處理或按任意優(yōu)先權(quán)進(jìn)行。

　　這里我們用數(shù)組實(shí)現(xiàn)優(yōu)先級隊(duì)列，這種方法插入比較慢，但是它比較簡單，適用于數(shù)據(jù)量比較小并且不是特別注重插入速度的情況。

　　后面我們會講解堆，用堆的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)優(yōu)先級隊(duì)列，可以相當(dāng)快的插入數(shù)據(jù)。

數(shù)組實(shí)現(xiàn)優(yōu)先級隊(duì)列，聲明為int類型的數(shù)組，關(guān)鍵字是數(shù)組里面的元素，在插入的時(shí)候按照從大到小的順序排列，也就是越小的元素優(yōu)先級越高。

　通過前面講的棧以及本篇講的隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)，我們稍微總結(jié)一下：

　?、?、棧、隊(duì)列（單向隊(duì)列）、優(yōu)先級隊(duì)列通常是用來簡化某些程序操作的數(shù)據(jù)結(jié)構(gòu)，而不是主要作為存儲數(shù)據(jù)的。

　?、凇⒃谶@些數(shù)據(jù)結(jié)構(gòu)中，只有一個(gè)數(shù)據(jù)項(xiàng)可以被訪問。

　?、邸Ｔ试S在棧頂壓入（插入）數(shù)據(jù)，在棧頂彈出（移除）數(shù)據(jù)，但是只能訪問最后一個(gè)插入的數(shù)據(jù)項(xiàng)，也就是棧頂元素。

　?、堋㈥?duì)列（單向隊(duì)列）只能在隊(duì)尾插入數(shù)據(jù)，對頭刪除數(shù)據(jù)，并且只能訪問對頭的數(shù)據(jù)。而且隊(duì)列還可以實(shí)現(xiàn)循環(huán)隊(duì)列，它基于數(shù)組，數(shù)組下標(biāo)可以從數(shù)組末端繞回到數(shù)組的開始位置。

　?、荨?yōu)先級隊(duì)列是有序的插入數(shù)據(jù)，并且只能訪問當(dāng)前元素中優(yōu)先級別最大（或最?。┑脑?。

　　⑥、這些數(shù)據(jù)結(jié)構(gòu)都能由數(shù)組實(shí)現(xiàn)，但是可以用別的機(jī)制（后面講的鏈表、堆等數(shù)據(jù)結(jié)構(gòu)）實(shí)現(xiàn)。

1. 鏈表

是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個(gè)（或兩個(gè)）節(jié)點(diǎn)里存到下一個(gè)（或上一個(gè)）節(jié)點(diǎn)的指針(Pointer)。

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。

單鏈表是鏈表中結(jié)構(gòu)最簡單的。一個(gè)單鏈表的節(jié)點(diǎn)(Node)分為兩個(gè)部分，第一個(gè)部分(data)保存或者顯示關(guān)于節(jié)點(diǎn)的信息，另一個(gè)部分存儲下一個(gè)節(jié)點(diǎn)的地址。最后一個(gè)節(jié)點(diǎn)存儲地址的部分指向空值。

單向鏈表

只可向一個(gè)方向遍歷，一般查找一個(gè)節(jié)點(diǎn)的時(shí)候需要從第一個(gè)節(jié)點(diǎn)開始每次訪問下一個(gè)節(jié)點(diǎn)，一直訪問到需要的位置。而插入一個(gè)節(jié)點(diǎn)，對于單向鏈表，我們只提供在鏈表頭插入，只需要將當(dāng)前插入的節(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)，next指向原頭節(jié)點(diǎn)即可。刪除一個(gè)節(jié)點(diǎn)，我們將該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

雙端鏈表

1. 二叉樹

樹的每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)

查找某個(gè)節(jié)點(diǎn)，我們必須從根節(jié)點(diǎn)開始遍歷。

　?、佟⒉檎抑当犬?dāng)前節(jié)點(diǎn)值大，則搜索右子樹；

　?、凇⒉檎抑档扔诋?dāng)前節(jié)點(diǎn)值，停止搜索（終止條件）；

　?、?、查找值小于當(dāng)前節(jié)點(diǎn)值，則搜索左子樹；

　 要插入節(jié)點(diǎn)，必須先找到插入的位置。與查找操作相似，由于二叉搜索樹的特殊性，待插入的節(jié)點(diǎn)也需要從根節(jié)點(diǎn)開始進(jìn)行比較，小于根節(jié)點(diǎn)則與根節(jié)點(diǎn)左子樹比較，反之則與右子樹比較，直到左子樹為空或右子樹為空，則插入到相應(yīng)為空的位置，在比較的過程中要注意保存父節(jié)點(diǎn)的信息 及 待插入的位置是父節(jié)點(diǎn)的左子樹還是右子樹，才能插入到正確的位置。

刪除節(jié)點(diǎn)是二叉搜索樹中最復(fù)雜的操作，刪除的節(jié)點(diǎn)有三種情況，前兩種比較簡單，但是第三種卻很復(fù)雜。

　　1、該節(jié)點(diǎn)是葉節(jié)點(diǎn)（沒有子節(jié)點(diǎn)）

　　2、該節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)

　　3、該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)

　　下面我們分別對這三種情況進(jìn)行講解。

　　①、刪除沒有子節(jié)點(diǎn)的節(jié)點(diǎn)

　　要刪除葉節(jié)點(diǎn)，只需要改變該節(jié)點(diǎn)的父節(jié)點(diǎn)引用該節(jié)點(diǎn)的值，即將其引用改為 null 即可。要刪除的節(jié)點(diǎn)依然存在，但是它已經(jīng)不是樹的一部分了，由于Java語言的垃圾回收機(jī)制，我們不需要非得把節(jié)點(diǎn)本身刪掉，一旦Java意識到程序不在與該節(jié)點(diǎn)有關(guān)聯(lián)，就會自動把它清理出存儲器。

刪除節(jié)點(diǎn)，我們要先找到該節(jié)點(diǎn)，并記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)。在檢查該節(jié)點(diǎn)是否有子節(jié)點(diǎn)。如果沒有子節(jié)點(diǎn)，接著檢查其是否是根節(jié)點(diǎn)，如果是根節(jié)點(diǎn)，只需要將其設(shè)置為null即可。如果不是根節(jié)點(diǎn)，是葉節(jié)點(diǎn)，那么斷開父節(jié)點(diǎn)和其的關(guān)系即可。

　?、凇h除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)

　　刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)，我們只需要將其父節(jié)點(diǎn)原本指向該節(jié)點(diǎn)的引用，改為指向該節(jié)點(diǎn)的子節(jié)點(diǎn)即可。

　③、刪除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)

　　當(dāng)刪除的節(jié)點(diǎn)存在兩個(gè)子節(jié)點(diǎn)，那么刪除之后，兩個(gè)子節(jié)點(diǎn)的位置我們就沒辦法處理了。既然處理不了，我們就想到一種辦法，用另一個(gè)節(jié)點(diǎn)來代替被刪除的節(jié)點(diǎn)，那么用哪一個(gè)節(jié)點(diǎn)來代替呢？

　　我們知道二叉搜索樹中的節(jié)點(diǎn)是按照關(guān)鍵字來進(jìn)行排列的，某個(gè)節(jié)點(diǎn)的關(guān)鍵字次高節(jié)點(diǎn)是它的中序遍歷后繼節(jié)點(diǎn)。用后繼節(jié)點(diǎn)來代替刪除的節(jié)點(diǎn)，顯然該二叉搜索樹還是有序的。（這里用后繼節(jié)點(diǎn)代替，如果該后繼節(jié)點(diǎn)自己也有子節(jié)點(diǎn)，我們后面討論。）

　　那么如何找到刪除節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)呢？其實(shí)我們稍微分析，這實(shí)際上就是要找比刪除節(jié)點(diǎn)關(guān)鍵值大的節(jié)點(diǎn)集合中最小的一個(gè)節(jié)點(diǎn)，只有這樣代替刪除節(jié)點(diǎn)后才能滿足二叉搜索樹的特性。

　　后繼節(jié)點(diǎn)也就是：比刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)。

6.紅黑樹

　　有如下兩個(gè)特征：

　?、佟⒐?jié)點(diǎn)都有顏色；

　?、?、在插入和刪除的過程中，要遵循保持這些顏色的不同排列規(guī)則。

　　第一個(gè)很好理解，在紅-黑樹中，每個(gè)節(jié)點(diǎn)的顏色或者是黑色或者是紅色的。當(dāng)然也可以是任意別的兩種顏色，這里的顏色用于標(biāo)記，我們可以在節(jié)點(diǎn)類Node中增加一個(gè)boolean型變量isRed，以此來表示顏色的信息。

　　第二點(diǎn)，在插入或者刪除一個(gè)節(jié)點(diǎn)時(shí)，必須要遵守的規(guī)則稱為紅-黑規(guī)則：

　　1.每個(gè)節(jié)點(diǎn)不是紅色就是黑色的；

　　2.根節(jié)點(diǎn)總是黑色的；

　　3.如果節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的（反之不一定）,(也就是從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))；

　　4.從根節(jié)點(diǎn)到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)的每條路徑，必須包含相同數(shù)目的黑色節(jié)點(diǎn)（即相同的黑色高度）。

　　從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑上的黑色節(jié)點(diǎn)的數(shù)目稱為黑色高度，規(guī)則 4 另一種表示就是從根到葉節(jié)點(diǎn)路徑上的黑色高度必須相同。

注意：新插入的節(jié)點(diǎn)顏色總是紅色的，這是因?yàn)椴迦胍粋€(gè)紅色節(jié)點(diǎn)比插入一個(gè)黑色節(jié)點(diǎn)違背紅-黑規(guī)則的可能性更小，原因是插入黑色節(jié)點(diǎn)總會改變黑色高度（違背規(guī)則4），但是插入紅色節(jié)點(diǎn)只有一半的機(jī)會會違背規(guī)則3（因?yàn)楦腹?jié)點(diǎn)是黑色的沒事，父節(jié)點(diǎn)是紅色的就違背規(guī)則3）。另外違背規(guī)則3比違背規(guī)則4要更容易修正。

紅黑樹和二叉樹的區(qū)別 ：

紅黑樹和之前所講的AVL樹類似，都是在進(jìn)行插入和刪除操作時(shí)通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。自從紅黑樹出來后，AVL樹就被放到了博物館里，據(jù)說是紅黑樹有更好的效率，更高的統(tǒng)計(jì)性能。 紅黑樹和AVL樹的區(qū)別在于它使用顏色來標(biāo)識結(jié)點(diǎn)的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴(yán)格的平衡。AVL樹的復(fù)雜比起紅黑樹來說簡直是小巫見大巫。紅黑樹是真正的變態(tài)級數(shù)據(jù)結(jié)構(gòu)。

(AVL樹,平衡二叉樹)

7.哈希表

Hash表也稱散列表，也有直接譯作哈希表，Hash表是一種根據(jù)關(guān)鍵字值（key - value）而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。它基于數(shù)組，通過把關(guān)鍵字映射到數(shù)組的某個(gè)下標(biāo)來加快查找速度，但是又和數(shù)組、鏈表、樹等數(shù)據(jù)結(jié)構(gòu)不同，在這些數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)關(guān)鍵字，通常要遍歷整個(gè)數(shù)據(jù)結(jié)構(gòu)

哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

?而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對應(yīng)的數(shù)組下標(biāo)，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：不論哈希表中有多少數(shù)據(jù)，查找、插入、刪除（有時(shí)包括刪除）只需要接近常量的時(shí)間即0(1）的時(shí)間級。實(shí)際上，這只需要幾條機(jī)器指令。

哈希表運(yùn)算得非?？?，在計(jì)算機(jī)程序中，如果需要在一秒種內(nèi)查找上千條記錄通常使用哈希表（例如拼寫檢查器)哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時(shí)間級。哈希表不僅速度快，編程實(shí)現(xiàn)也相對容易。

如果不需要有序遍歷數(shù)據(jù)，并且可以提前預(yù)測數(shù)據(jù)量的大小。那么哈希表在速度和易用性方面是無與倫比的。

缺點(diǎn)：它是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展，某些哈希表被基本填滿時(shí)，性能下降得非常嚴(yán)重，所以程序員必須要清楚表中將要存儲多少數(shù)據(jù)（或者準(zhǔn)備好定期地把數(shù)據(jù)轉(zhuǎn)移到更大的哈希表中，這是個(gè)費(fèi)時(shí)的過程）。

（有個(gè)不錯(cuò)的例子，點(diǎn)擊）

8. 堆

堆是一顆完全二叉樹，在這棵樹中，所有父節(jié)點(diǎn)都滿足大于等于其子節(jié)點(diǎn)的堆叫大根堆，所有父節(jié)點(diǎn)都滿足小于等于其子節(jié)點(diǎn)的堆叫小根堆。堆雖然是一顆樹，但是通常存放在一個(gè)數(shù)組中，父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的父子關(guān)系通過數(shù)組下標(biāo)來確定。

堆是弱序的，所以想要遍歷堆是很困難的，基本上，堆是不支持遍歷的。

　　對于查找，由于堆的特性，在查找的過程中，沒有足夠的信息來決定選擇通過節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)中的哪一個(gè)來選擇走向下一層，所以也很難在堆中查找到某個(gè)關(guān)鍵字。

因此，堆這種組織似乎非常接近無序，不過，對于快速的移除最大（或最?。┕?jié)點(diǎn)，也就是根節(jié)點(diǎn)，以及能快速插入新的節(jié)點(diǎn)，這兩個(gè)操作就足夠了。