集合框架（怎么實現(xiàn)、適用場景） hash相關
其中Set代表無序、不可重復的集合；List代表有序、重復的集合；而Map則代表具
有映射關系的集合。Java 5 又增加了Queue體系集合，代表一種隊列集合實現(xiàn)。
1.Java集合和數(shù)組的區(qū)別：
①.數(shù)組長度在初始化時指定，意味著只能保存定長的數(shù)據(jù)。而集合可以保存數(shù)量不
確定的數(shù)據(jù)。同時可以保存具有映射關系的數(shù)據(jù)（即關聯(lián)數(shù)組，鍵值對 keyvalue）。
②.數(shù)組元素即可以是基本類型的值，也可以是對象。集合里只能保存對象（實際上
只是保存對象的引用變量），基本數(shù)據(jù)類型的變量要轉(zhuǎn)換成對應的包裝類才能放入
集合類中。
Java集合框架
集合類主要分為兩大類：Collection和Map
Collection-List接口通常表示一個列表（數(shù)組、隊列、鏈表、棧等），其中的元素可以重復，常用實現(xiàn)類為ArrayList和LinkedList，另外還有不常用的Vector。
Map-Set接口通常表示一個集合，其中的元素不允許重復（通過hashcode和equals函數(shù)保證），常用實現(xiàn)類有HashSet和TreeSet，HashSet是通過Map中的HashMap實現(xiàn)的，而TreeSet是通過Map中的TreeMap實現(xiàn)的。
所有的集合類都必須能提供友好的交互操作，采用了適配器模式，這包括沒有繼承Collection類的數(shù)組對象。因此，框架提供一套方法，讓集合類與數(shù)組可以相互轉(zhuǎn)化，并且可以把Map看作成集合。
Map
Map并不是一個真正意義上的集合，但是這個接口提供了三種“集合視角”，使得可以像操作集合一樣操作它們，具體如下：
- 把map的內(nèi)容看作key的集合
- 把map的內(nèi)容看作value的集合
- 把map的內(nèi)容看作key-value映射的集合
樹是一種由節(jié)點組成的數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點都包含數(shù)據(jù)元素，并且有一個或多個子節(jié)點，每個子節(jié)點指向一個父節(jié)點（除了根節(jié)點）可以表示層級關系或者數(shù)據(jù)元素的順序關系。常用的場景有表示一個組織里的雇員層級關系，XML元素的層級關系，等等。如果樹的每個子節(jié)點最多有兩個葉子節(jié)點，那么這種樹被稱為二叉樹。二叉樹是一種非常常用的樹形結(jié)構(gòu)， 因為它的這種結(jié)構(gòu)使得節(jié)點的插入和刪除都非常高效。樹的邊表示從一個節(jié)點到另外一個節(jié)點的快捷路徑。
二叉樹的遞歸遍歷 P114
先中后
平衡二叉樹
任意子樹都滿足|左深度-右深度|<=1的二叉樹
B-樹 P221
B-樹是一種平衡多路查找樹。一棵m階B-樹，具有下列性質(zhì)：
（1）樹中每個節(jié)點至多有m棵子樹；
（2）若根節(jié)點不是葉子節(jié)點，則至少有2棵子樹；
（3）除根節(jié)點之外的所有非終端節(jié)點至少有[m/2]棵子樹；
（4）每個節(jié)點中的信息結(jié)構(gòu)為（n,A0,K1,A1,K2......Kn,An），其中n表示關鍵字個數(shù)，Ki為關鍵字，Ai為只想字數(shù)根節(jié)點的指針；（指針A(i-1)所指子樹中所有節(jié)點的關鍵字均小于Ki，An所指字數(shù)中所有節(jié)點的關鍵字均大于Kn）
（5）所有的葉子節(jié)點都出現(xiàn)在同一層次上，且不帶任何信息，也是為了保持算法的一致性。
hash相關
散列表（Hash table，也叫哈希表），是依據(jù)鍵值(Key value)直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。它通過把鍵值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
什么叫沖突
key1！= key2，但是value1 = value2
解決沖突的辦法：
（1）線性探查法：沖突后，線性向前試探，找到近期的一個空位置。缺點是會出現(xiàn)堆積現(xiàn)象。存取時，可能不是同義詞的詞也位于探查序列，影響效率。（“同義詞”：兩個元素通過散列函數(shù)得到的地址同樣）
（2）雙散列函數(shù)法：在位置d沖突后，再使用另一個散列函數(shù)產(chǎn)生一個與散列表桶容量m互質(zhì)的數(shù)c，依次試探(d+n*c)%m，使探查序列跳躍式分布。
Hash算法在信息安全方面的應用
（1) 文件校驗（MD5 Hash算法的”數(shù)字指紋”特性，使它成為眼下應用最廣泛的一種文件完整性校驗算法）
（2) 數(shù)字簽名（對 Hash 值，又稱”數(shù)字摘要”進行數(shù)字簽名，在統(tǒng)計上能夠覺得與對文件本身進行數(shù)字簽名是等效的）
（3) 鑒權協(xié)議（在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法）
