數(shù)組：

數(shù)組是一種連續(xù)存儲(chǔ)線性結(jié)構(gòu)，元素類(lèi)型相同，大小相等，數(shù)組是多維的，通過(guò)使用整型索引值來(lái)訪問(wèn)他們的元素，數(shù)組尺寸不能改變。

數(shù)組的優(yōu)點(diǎn)：
存取速度快
數(shù)組的缺點(diǎn)：
事先必須知道數(shù)組的長(zhǎng)度
插入刪除元素很慢
空間通常是有限制的
需要大塊連續(xù)的內(nèi)存塊
插入刪除元素的效率很低

1.collection 和 collections

collection ：集合類(lèi)的上層接口，子接口主要有l(wèi)ist ，set，queue等

collections：提供對(duì)集合進(jìn)行搜索，排序，替換和線程安全化等操作的工具類(lèi)。

arrayList，LinkedList，Vector

arraylist：動(dòng)態(tài)數(shù)組；基于數(shù)組實(shí)現(xiàn)；

linkedList：有序數(shù)組；基于雙向鏈表實(shí)現(xiàn)；

vector：對(duì)象容器，可放入不同類(lèi)的對(duì)象（基于數(shù)組實(shí)現(xiàn)）；

linkedHashMap ，TreeMap ,TreeSet

linkedHashMap：順序存取hashMap（基于數(shù)組和雙向鏈表實(shí)現(xiàn)）；

TreeMap：內(nèi)部排序（基于黑色樹(shù)實(shí)現(xiàn)）；

TreeSet：有序的set集合（基于二叉樹(shù)）；

鏈表：

n個(gè)節(jié)點(diǎn)離散分配，彼此通過(guò)指針相連，每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn)，首節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒(méi)有后續(xù)節(jié)點(diǎn)。

確定一個(gè)鏈表我們只需要頭指針，通過(guò)頭指針就可以把整個(gè)鏈表都能推出來(lái)。

鏈表優(yōu)點(diǎn)
空間沒(méi)有限制
插入刪除元素很快
鏈表缺點(diǎn)
存取速度很慢

鏈表又細(xì)分了3類(lèi)：

單向鏈表
一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)。
雙向鏈表
一個(gè)節(jié)點(diǎn)有兩個(gè)指針域。
循環(huán)鏈表
能通過(guò)任何一個(gè)節(jié)點(diǎn)找到其他所有的節(jié)點(diǎn)，將兩種(雙向/單向)鏈表的最后一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)從而實(shí)現(xiàn)循環(huán)。

操作鏈表要時(shí)刻記住的是：節(jié)點(diǎn)中指針域指向的就是另一個(gè)節(jié)點(diǎn)！

棧和隊(duì)列

數(shù)組和鏈表都是線性存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)，棧和隊(duì)列都是線性存儲(chǔ)結(jié)構(gòu)的應(yīng)用。

我們將棧可以看成一個(gè)放光盤(pán)的箱子，箱口與略大與光盤(pán)。然后

往箱子里面放東西叫做入棧
往箱子里面取東西叫做出棧
箱子的底部叫做棧底
箱子的頂部叫做棧頂

說(shuō)到棧的特性，有一句經(jīng)典的言語(yǔ)來(lái)概括：先進(jìn)后出，后進(jìn)先出。

JAVA實(shí)現(xiàn)棧

使用數(shù)組實(shí)現(xiàn)的叫靜態(tài)棧
使用鏈表實(shí)現(xiàn)的叫動(dòng)態(tài)棧

隊(duì)列

隊(duì)列非常好理解，我們將隊(duì)列可以看成我們平時(shí)排隊(duì)打飯。

有新的人加入了 -> 入隊(duì)
隊(duì)頭的人打飯了 -> 出隊(duì)

相對(duì)于棧而言，隊(duì)列的特性是：先進(jìn)先出，后進(jìn)后出

隊(duì)列

使用數(shù)組實(shí)現(xiàn)的叫靜態(tài)隊(duì)列
使用鏈表實(shí)現(xiàn)的叫動(dòng)態(tài)隊(duì)列

二叉樹(shù)

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，相對(duì)于線性的數(shù)據(jù)結(jié)構(gòu)(鏈表、數(shù)組)而言，樹(shù)的平均運(yùn)行時(shí)間更短(往往與樹(shù)相關(guān)的排序時(shí)間復(fù)雜度都不會(huì)高)，

和現(xiàn)實(shí)中的樹(shù)相比，編程的世界中的樹(shù)一般是“倒”過(guò)來(lái)看，這樣容易我們分析。

現(xiàn)實(shí)中的樹(shù)是有很多很多個(gè)分支的，分支下又有很多很多個(gè)分支，如果在程序中實(shí)現(xiàn)這個(gè)會(huì)非常麻煩。因?yàn)楸緛?lái)樹(shù)就是非線性的，而我們計(jì)算機(jī)的內(nèi)存是線性存儲(chǔ)的，太過(guò)復(fù)雜的話無(wú)法設(shè)計(jì)出來(lái)。

因此，就有了簡(jiǎn)單又經(jīng)常用的 -> 二叉樹(shù)，顧名思義，就是每個(gè)分支最多只有兩個(gè)的樹(shù)，上圖就是二叉樹(shù)。

一棵樹(shù)至少會(huì)有一個(gè)節(jié)點(diǎn)(根節(jié)點(diǎn))
樹(shù)由節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)包括一個(gè)數(shù)據(jù)和兩個(gè)分叉

堆和堆棧

堆內(nèi)存用來(lái)存放由new創(chuàng)建的對(duì)象和數(shù)組。

在堆中分配的內(nèi)存，由Java虛擬機(jī)的自動(dòng)垃圾回收器來(lái)管理。

'堆棧' 就是 '棧'，稱呼不同而已。

棧的優(yōu)勢(shì)是，存取速度比堆要快，僅次于直接位于CPU中的寄存器。但缺點(diǎn)是，存在棧中的數(shù)據(jù)大小與生存期必須是確定的，缺乏靈活性。另外，棧數(shù)據(jù)可以共享。

堆的優(yōu)勢(shì)是可以動(dòng)態(tài)地分配內(nèi)存大小，生存期也不必事先告訴編譯器，Java的垃圾收集器會(huì)自動(dòng)收走這些不再使用的數(shù)據(jù)。但缺點(diǎn)是，由于要在運(yùn)行時(shí)動(dòng)態(tài)分配內(nèi)存，存取速度較慢。

散列表

無(wú)論是Set還是Map，我們會(huì)發(fā)現(xiàn)都會(huì)有對(duì)應(yīng)的-->HashSet,HashMap

首先我們也先得回顧一下數(shù)據(jù)和鏈表：

鏈表和數(shù)組都可以按照人們的意愿來(lái)排列元素的次序，他們可以說(shuō)是有序的(存儲(chǔ)的順序和取出的順序是一致的)
這會(huì)帶來(lái)缺點(diǎn)：想要獲取某個(gè)元素，就要訪問(wèn)所有的元素，直到找到為止，會(huì)消耗很多時(shí)間。

所以我們需要另外的存儲(chǔ)結(jié)構(gòu)：不在意元素順序，能快速查找元素。其中就有一種常見(jiàn)方式：散列表。

散列表工作原理

散列表為每個(gè)對(duì)象計(jì)算出一個(gè)整數(shù)，稱為散列碼。根據(jù)這些計(jì)算出來(lái)的整數(shù)(散列碼)保存在對(duì)應(yīng)的位置上！即，散列碼就是索引。

在Java中，散列表用的是鏈表數(shù)組實(shí)現(xiàn)的，每個(gè)列表稱之為桶。

紅黑樹(shù)

是一種平衡二叉樹(shù)，TreeSet、TreeMap底層都是紅黑樹(shù)來(lái)實(shí)現(xiàn)的。

二叉查找樹(shù)也有個(gè)例(最壞)的情況(線性)：

上面符合二叉樹(shù)的特性，但是它是線性的，完全沒(méi)樹(shù)的用處，樹(shù)是要“均衡”才能將它的優(yōu)點(diǎn)展示出來(lái)，比如下面這種:

因此，就有了平衡樹(shù)這么一個(gè)概念~紅黑樹(shù)就是一種平衡樹(shù)，它可以保證二叉樹(shù)基本符合均衡的金字塔結(jié)構(gòu)。都是在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持二叉查找樹(shù)的平衡，從而獲得較高的查找性能。

它的統(tǒng)計(jì)性能要好于平衡二叉樹(shù)

上圖就是一個(gè)紅黑樹(shù)，紅黑樹(shù)就字面上的意思，有紅色的節(jié)點(diǎn)，有黑色的節(jié)點(diǎn)。

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。
性質(zhì)2. 根節(jié)點(diǎn)是黑色。
性質(zhì)3. 每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。
性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

b樹(shù)：

平衡二叉樹(shù)的查找效率為O（log2N）與樹(shù)的深度相關(guān)，通過(guò)降低樹(shù)的深度，可以提高查找效率，但是還有一個(gè)瓶頸就是，每次查找一次就只能得到一個(gè)節(jié)點(diǎn)元素，如果查找一次能得到多個(gè)節(jié)點(diǎn)元素，那么在同樣的高度就能夠查找更多的元素，從而提高查找效率，因此提出多路查找樹(shù)。

多路查找樹(shù)（muitl-way search tree），其每一個(gè)結(jié)點(diǎn)的孩子數(shù)可以多于兩個(gè)，且每個(gè)結(jié)點(diǎn)出可以存儲(chǔ)多個(gè)元素。由于它是查找樹(shù)，所有元素之間存在某種特定的排序關(guān)系。

B樹(shù)就是一種平衡的多路查找樹(shù)。

B-樹(shù)

中所有結(jié)點(diǎn)中孩子結(jié)點(diǎn)個(gè)數(shù)的最大值成為B-樹(shù)的階，通常用m表示，從查找效率考慮，一般要求m>=3。一棵m階B-樹(shù)或者是一棵空樹(shù)，或者是滿足以下條件的m叉樹(shù)。

1）每個(gè)結(jié)點(diǎn)最多有m個(gè)分支（子樹(shù)）；而最少分支數(shù)要看是否為根結(jié)點(diǎn)，如果是根結(jié)點(diǎn)且不是葉子結(jié)點(diǎn)，則至少要有兩個(gè)分支，非根非葉結(jié)點(diǎn)至少有ceil(m/2)個(gè)分支，這里ceil代表向上取整。

2）如果一個(gè)結(jié)點(diǎn)有n-1個(gè)關(guān)鍵字，那么該結(jié)點(diǎn)有n個(gè)分支。這n-1個(gè)關(guān)鍵字按照遞增順序排列。

3）每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)為

節(jié)點(diǎn)個(gè)數(shù)：n；

關(guān)鍵字?jǐn)?shù)組： k[n]，這n個(gè)關(guān)鍵字按照遞增順序排列

孩子指針數(shù)組：p[n + 1], p0<=k1, 之后所有 ki < pi <= ki+1;

B+樹(shù)

1）在B+樹(shù)中，具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)有n個(gè)分支，而在B-樹(shù)中，具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)含有n+1個(gè)關(guān)鍵字。

2）在B+樹(shù)中，每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)外）中的關(guān)鍵字個(gè)數(shù)n的取值為ceil(m/2) <= n <=m,根結(jié)點(diǎn)的取值范圍為1<=n<=m，b樹(shù)他們的取值范圍分別是ceil(m/2) -1<= n <=m-1和1<=n<=m-1。

3）在B+樹(shù)中葉子結(jié)點(diǎn)包含信息，并且包含了全部關(guān)鍵字，葉子結(jié)點(diǎn)引出的指針指向記錄。

4）在B+樹(shù)中的所有非葉子結(jié)點(diǎn)僅起到一個(gè)索引的作用，即結(jié)點(diǎn)中的每個(gè)索引項(xiàng)只含有對(duì)應(yīng)子樹(shù)的最大關(guān)鍵字和指向該子樹(shù)的指針。

算法：

1.二分查找：又稱折半查找；優(yōu)點(diǎn)是比較次數(shù)少，查詢速度快，平均性能好，占用系統(tǒng)內(nèi)存較少，其缺點(diǎn)是：要求待查表為有序表，且插入刪除困難。

2.遞歸算法

遞歸簡(jiǎn)單理解就是方法自身調(diào)用自身。

排序算法：1.直接插入排序；2.希爾排序，3，選擇排序，4.堆排序；5，冒泡排序6，快速排序，7，歸并排序，8.基數(shù)排序

1.冒泡排序：他重復(fù)地走訪要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)，走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成、整個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢‘浮’到數(shù)列的頂端。