一、Set和Map
Set代表一種集合元素?zé)o序咐扭、集合元素不可重復(fù)的集合华弓，Map代表一種由多個key-value對組成的集合食零，可以這么說，Map集合是Set集合的拓展寂屏。
Map和Set的關(guān)系：Map集合的Key具有一個特征：所有key不能重復(fù)贰谣，并且沒有順序，也就是說迁霎，如果將Map集合中的所有Key集中起來吱抚，那這些key就組成了一個set集合。對于map而言考廉，相當于每個元素都是key-value的Set集合秘豹。
1、HashMap和HashSet
HashSet：系統(tǒng)采用Hash算法決定集合元素的存儲位置昌粤，這樣可以保證快速存取集合元素既绕。
HashMap：系統(tǒng)將Value作為key的附屬，系統(tǒng)根據(jù)Hash算法來決定key的存儲位置涮坐，這樣可以保證快速存取集合Key凄贩，而value總是跟隨key存儲。
note：集合存放的只是對象的引用袱讹。
HashMap put步驟：
1疲扎，根據(jù)key的keyCode計算Hash值
2，搜索指定hash值在對應(yīng)table中的索引
3，如果i處索引處的Entry不為null椒丧，通過循環(huán)不斷遍歷e元素的下一個元素
4壹甥，找到指定key與需要放入的key相等，新添加Entry的value將覆蓋原有Entry的value瓜挽，但key不會覆蓋
5盹廷，如果i索引處的Entry為null征绸，表明此處還沒有Entry
6久橙，將key，value添加到i索引處
note：當系統(tǒng)決定存儲HashMap中的key-value對時管怠，完全沒有考慮Entry中的value淆衷，而僅僅只是根據(jù)key來計算并決定每個Entry的存儲位置，在key的hash如果通過equals比較兩個Entry的key發(fā)現(xiàn)相等渤弛，就會替換掉原有entry中value值祝拯，如果不相等，新添加的Entry將與原有Entry形成Entry鏈她肯。addEntry（）方法佳头。
HashMap構(gòu)造器，默認初始容量為16晴氨，如果需要指定初始容量康嘉，最好指定為2的n次方。
當HashMap的每個bucket里存儲的Entry只是單個Entry籽前，即沒有通過指針產(chǎn)生Entry鏈時亭珍，此時的HashMap具有最好的性能。
負載因子：默認為0.75枝哄，增大負載因子可以減小Hash表（實際上就是Entry數(shù)組）所占用的內(nèi)存空間肄梨，但會增加查詢數(shù)據(jù)的時間開銷，減小負載因子會提高數(shù)據(jù)查詢的性能挠锥，但會增加Hash表所占用的內(nèi)存空間众羡。
HashSet是基于HashMap實現(xiàn)的，底層仍然采用HashMap來保存所有的元素蓖租。封裝了一個HashMap對象來存儲所有的集合元素粱侣。所有放入HashSet中的集合元素實際上由HashMap的key來保存，而HashMap的value則存儲了一個靜態(tài)的Object對象菜秦。因此HashSet和HashMap在實現(xiàn)本質(zhì)上是相同的甜害。
當試圖把某個類的對象當成HashMap的key，或者試圖將這個類的對象放入HashSet中保存時球昨，重寫equals方法和hashCode方法很重要尔店，而且這兩個方法的返回值必需保持一致。
2、TreeMap和TreeSet
HashSet底層依賴于HashMap實現(xiàn)嚣州，TreeSet底層則采用一個NavigableMap來保存TreeSet集合的元素鲫售，由于NavigableMap只是一個接口，因此底層仍然采用TreeMap來保存Set集合中的所有元素该肴。
TreeMap情竹，底層采用紅黑樹的排序二叉樹來保存Map中的每個Entry，每個Entry都被當成紅黑樹的一個節(jié)點來看待匀哄。
TreeMap添加元素秦效、取出元素的性能都比HashMap低，這些操作都需要通過循環(huán)找到新增Entry的插入位置涎嚼，因此比較好性能阱州，優(yōu)勢在于：TreeMap中所有的Entry總是按key根據(jù)指定排序規(guī)則保存有序狀態(tài)，TreeSet中所有元素總是根據(jù)指定排序規(guī)則保持有序狀態(tài)法梯。
二苔货、Map和List
Map接口提供了get(Key)方法允許對象根據(jù)key獲取value.
List接口提供了get(int index)方法允許List對象根據(jù)元素索引來取得value.
List相當于所有key都是int類型的Map,也可以說Map相當于索引是任意類型的List.
ArrayList和LinkedList
List三個主要實現(xiàn)類：ArrayList、Vector立哑、LinkedList
Vector還有一個Stack子類夜惭，僅在Vector的基礎(chǔ)上增加了5個方法，Stack和Vector都是線程安全的類铛绰。
在無需保證線程安全的情況下诈茧，推薦使用ArrayDeque來代替Stack類。
Deque代表雙端隊列這種數(shù)據(jù)結(jié)構(gòu)至耻，他既有隊列的先進先出性質(zhì)若皱，也具有棧的性質(zhì)，既是隊列尘颓，也是棧走触。
ArrayList和ArrayDeque底層都是基于數(shù)組實現(xiàn)的，只是所提供的方法不同疤苹。
Vector和ArrayList的區(qū)別
1互广，Vector和ArrayList都繼承自List，底層都是基于數(shù)組卧土，但是ArrayList使用transient修飾底層數(shù)組惫皱，保證序列化ArrayList對象的時候不會直接序列化底層數(shù)組，而是通過writeObject和readObject來實現(xiàn)定制序列化尤莺，Vector沒有實現(xiàn)旅敷。
因此ArrayList比Vector的序列化實現(xiàn)更安全。
2颤霎，Vector是線程安全的媳谁，ArrayList不是涂滴。
3，數(shù)組擴充：
ArrayList:int newCapacity = (oldCapacity3)/2+1 //將新容量擴充為原來的1.5倍
Vector：int newCapacity = (capacityIncrement>0)?(oldCapacity+capacityIncrement):(oldCapacity2); //如果capacityIncrement>0晴音，新容量 = oldCapacity+capacityIncrement柔纵，否則擴充為原來的兩倍。
ArrayList和LinkedList的實現(xiàn)差異
1锤躁，List代表一種線性表的數(shù)據(jù)結(jié)構(gòu)搁料，ArrayList則是一種順序存儲的線性表。
2系羞，ArrayList底層采用數(shù)組來存儲每個集合元素郭计。LinkedList是一種鏈式存儲的線性表。其本質(zhì)上是一個雙向鏈表觉啊，不僅實現(xiàn)了List接口拣宏，還實現(xiàn)了Deque接口沈贝。也就是說LinkedList不僅可以當成雙向鏈表使用杠人，還可以當成棧來使用，還可以當成隊列來使用宋下。
3嗡善，ArrayList添加、刪除集合元素時学歧，ArrayList底層都需要對數(shù)組進行“整體搬家”罩引，性能非常差。
ArrayList和LinkedList的性能分析和使用場景
1枝笨，當程序需要以get(int index)方法獲取指定索引處的元素時袁铐，ArrayList>LinkedList,
2，當程序調(diào)用add(int index,Object obj)向List集合添加元素時横浑，ArrayList需要對底層數(shù)組元素進行整體搬家剔桨，如果添加元素導(dǎo)致集合長度將要超過底層數(shù)組長度，ArrayList必須新建一個長度為原來長度1.5倍的數(shù)組徙融，再有垃圾回收機制回收原有數(shù)組洒缀，系統(tǒng)開銷較大。對于LinkedList而言欺冀，他的開銷主要集中在根據(jù)index找到元素的過程树绩，即使如此：LinkedList>ArrayList
3，當程序調(diào)用remove(int index)方法刪除index處的元素時隐轩，ArrayList同樣需要對底層數(shù)組元素進行整體搬家饺饭，但是無需考慮創(chuàng)建新的數(shù)組，因此：LinkedList約等于ArrayList
4职车，當程序調(diào)用add(Object obj)時瘫俊，大多數(shù)時候無需對數(shù)組進行整體搬家蛛芥，但是如果添加元素導(dǎo)致集合大小大于數(shù)組大小，ArrayList必須新建一個長度為原來長度1.5倍的數(shù)組军援，這樣開銷就比較大了仅淑，LinkedList則有比較好的性能。因此：LinkedList>ArrayList
