數組：
數組是一種連續存儲線性結構，元素類型相同，大小相等，數組是多維的，通過使用整型索引值來訪問他們的元素，數組尺寸不能改變。
- 數組的優點：
- 存取速度快
- 數組的缺點：
- 事先必須知道數組的長度
- 插入刪除元素很慢
- 空間通常是有限制的
- 需要大塊連續的內存塊
- 插入刪除元素的效率很低
1.collection 和 collections
collection ：集合類的上層接口，子接口主要有list ，set，queue等
collections：提供對集合進行搜索，排序，替換和線程安全化等操作的工具類。
arrayList，LinkedList，Vector
arraylist：動態數組；基于數組實現；
linkedList：有序數組；基于雙向鏈表實現；
vector：對象容器，可放入不同類的對象（基于數組實現）；
linkedHashMap ，TreeMap ,TreeSet
linkedHashMap：順序存取hashMap（基于數組和雙向鏈表實現）；
TreeMap：內部排序（基于黑色樹實現）；
TreeSet：有序的set集合（基于二叉樹）；
鏈表：
n個節點離散分配，彼此通過指針相連，每個節點只有一個前驅節點，每個節點只有一個后續節點，首節點沒有前驅節點，尾節點沒有后續節點。
確定一個鏈表我們只需要頭指針，通過頭指針就可以把整個鏈表都能推出來。
- 鏈表優點
- 空間沒有限制
- 插入刪除元素很快
- 鏈表缺點
- 存取速度很慢
鏈表又細分了3類：
- 單向鏈表
- 一個節點指向下一個節點。
- 雙向鏈表
- 一個節點有兩個指針域。
- 循環鏈表
- 能通過任何一個節點找到其他所有的節點，將兩種(雙向/單向)鏈表的最后一個結點指向第一個結點從而實現循環。
操作鏈表要時刻記住的是：節點中指針域指向的就是另一個節點！
棧和隊列
數組和鏈表都是線性存儲結構的基礎，棧和隊列都是線性存儲結構的應用。
我們將?？梢钥闯梢粋€放光盤的箱子，箱口與略大與光盤。然后
- 往箱子里面放東西叫做入棧
- 往箱子里面取東西叫做出棧
- 箱子的底部叫做棧底
- 箱子的頂部叫做棧頂
說到棧的特性，有一句經典的言語來概括：先進后出，后進先出。
JAVA實現棧
- 使用數組實現的叫靜態棧
- 使用鏈表實現的叫動態棧
隊列
隊列非常好理解，我們將隊列可以看成我們平時排隊打飯。
- 有新的人加入了 -> 入隊
- 隊頭的人打飯了 -> 出隊
相對于棧而言，隊列的特性是：先進先出，后進后出
隊列
- 使用數組實現的叫靜態隊列
- 使用鏈表實現的叫動態隊列
二叉樹
樹是一種非線性的數據結構，相對于線性的數據結構(鏈表、數組)而言，樹的平均運行時間更短(往往與樹相關的排序時間復雜度都不會高)，
和現實中的樹相比，編程的世界中的樹一般是“倒”過來看，這樣容易我們分析。
現實中的樹是有很多很多個分支的，分支下又有很多很多個分支，如果在程序中實現這個會非常麻煩。因為本來樹就是非線性的，而我們計算機的內存是線性存儲的，太過復雜的話無法設計出來。
因此，就有了簡單又經常用的 -> 二叉樹，顧名思義，就是每個分支最多只有兩個的樹，上圖就是二叉樹。
- 一棵樹至少會有一個節點(根節點)
- 樹由節點組成，每個節點的數據結構包括一個數據和兩個分叉
堆和堆棧
堆內存用來存放由new創建的對象和數組。
在堆中分配的內存，由Java虛擬機的自動垃圾回收器來管理。
'堆棧' 就是 '棧'，稱呼不同而已。
棧的優勢是，存取速度比堆要快，僅次于直接位于CPU中的寄存器。但缺點是，存在棧中的數據大小與生存期必須是確定的，缺乏靈活性。另外，棧數據可以共享。
堆的優勢是可以動態地分配內存大小，生存期也不必事先告訴編譯器，Java的垃圾收集器會自動收走這些不再使用的數據。但缺點是，由于要在運行時動態分配內存，存取速度較慢。
散列表
無論是Set還是Map，我們會發現都會有對應的-->HashSet,HashMap
首先我們也先得回顧一下數據和鏈表：
- 鏈表和數組都可以按照人們的意愿來排列元素的次序，他們可以說是有序的(存儲的順序和取出的順序是一致的)
- 這會帶來缺點：想要獲取某個元素，就要訪問所有的元素，直到找到為止，會消耗很多時間。
所以我們需要另外的存儲結構：不在意元素順序，能快速查找元素。其中就有一種常見方式：散列表。
散列表工作原理
散列表為每個對象計算出一個整數，稱為散列碼。根據這些計算出來的整數(散列碼)保存在對應的位置上！即，散列碼就是索引。
在Java中，散列表用的是鏈表數組實現的，每個列表稱之為桶。
紅黑樹
是一種平衡二叉樹，TreeSet、TreeMap底層都是紅黑樹來實現的。
二叉查找樹也有個例(最壞)的情況(線性)：
上面符合二叉樹的特性，但是它是線性的，完全沒樹的用處，樹是要“均衡”才能將它的優點展示出來，比如下面這種:
因此，就有了平衡樹這么一個概念~紅黑樹就是一種平衡樹，它可以保證二叉樹基本符合均衡的金字塔結構。都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。
它的統計性能要好于平衡二叉樹
上圖就是一個紅黑樹，紅黑樹就字面上的意思，有紅色的節點，有黑色的節點。
- 性質1. 節點是紅色或黑色。
- 性質2. 根節點是黑色。
- 性質3. 每個葉節點（NIL節點，空節點）是黑色的。
- 性質4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
- 性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
b樹：
平衡二叉樹的查找效率為O（log2N）與樹的深度相關，通過降低樹的深度，可以提高查找效率，但是還有一個瓶頸就是，每次查找一次就只能得到一個節點元素，如果查找一次能得到多個節點元素，那么在同樣的高度就能夠查找更多的元素，從而提高查找效率，因此提出多路查找樹。
多路查找樹（muitl-way search tree），其每一個結點的孩子數可以多于兩個，且每個結點出可以存儲多個元素。由于它是查找樹，所有元素之間存在某種特定的排序關系。
B樹就是一種平衡的多路查找樹。
B-樹
中所有結點中孩子結點個數的最大值成為B-樹的階，通常用m表示，從查找效率考慮，一般要求m>=3。一棵m階B-樹或者是一棵空樹，或者是滿足以下條件的m叉樹。
1）每個結點最多有m個分支（子樹）；而最少分支數要看是否為根結點，如果是根結點且不是葉子結點，則至少要有兩個分支，非根非葉結點至少有ceil(m/2)個分支，這里ceil代表向上取整。
2）如果一個結點有n-1個關鍵字，那么該結點有n個分支。這n-1個關鍵字按照遞增順序排列。
3）每個節點的結構為
節點個數：n；
關鍵字數組： k[n]，這n個關鍵字按照遞增順序排列
孩子指針數組：p[n + 1], p0<=k1, 之后所有 ki < pi <= ki+1;
B+樹
1）在B+樹中，具有n個關鍵字的結點有n個分支，而在B-樹中，具有n個關鍵字的結點含有n+1個關鍵字。
2）在B+樹中，每個結點（除根結點外）中的關鍵字個數n的取值為ceil(m/2) <= n <=m,根結點的取值范圍為1<=n<=m，b樹他們的取值范圍分別是ceil(m/2) -1<= n <=m-1和1<=n<=m-1。
3）在B+樹中葉子結點包含信息，并且包含了全部關鍵字，葉子結點引出的指針指向記錄。
4）在B+樹中的所有非葉子結點僅起到一個索引的作用，即結點中的每個索引項只含有對應子樹的最大關鍵字和指向該子樹的指針。
算法：
1.二分查找：又稱折半查找；優點是比較次數少，查詢速度快，平均性能好，占用系統內存較少，其缺點是：要求待查表為有序表，且插入刪除困難。
2.遞歸算法
遞歸簡單理解就是方法自身調用自身。
排序算法：1.直接插入排序；2.希爾排序，3，選擇排序，4.堆排序；5，冒泡排序6，快速排序，7，歸并排序，8.基數排序
1.冒泡排序：他重復地走訪要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來，走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成、整個算法的名字由來是因為越小的元素會經由交換慢慢‘浮’到數列的頂端。
