1.為什么要有集合
世間上本來(lái)沒有集合,但有人想要,所以有了集合
有人想有可以自動(dòng)擴(kuò)展的數(shù)組,所以有了List
有的人想有沒有重復(fù)的數(shù)組,所以有了set
有人想有自動(dòng)排序的數(shù)組,所以有了TreeSet
因?yàn)榧鲜菍?duì)數(shù)組做的封裝,所以,數(shù)組永遠(yuǎn)比任何一個(gè)集合要快
但任何一個(gè)集合,比數(shù)組提供的功能要多
數(shù)組是一種可讀/可寫數(shù)據(jù)結(jié)構(gòu)－－－沒有辦法創(chuàng)建一個(gè)只讀數(shù)組丸边。然而可以使用collections提供的UnmodifiableCollection方法列敲，以只讀方式來(lái)使用集合抵皱。該方法將返回一個(gè)集合的只讀版本(final修飾)。
集合類型主要有3種：set(集）缚柏、list(列表）和map(映射)苹熏。
幾個(gè)常用類的區(qū)別
1．ArrayList: 元素單個(gè)，效率高币喧，多用于查詢
2．Vector: 元素單個(gè)轨域，線程安全，多用于查詢
3．LinkedList:元素單個(gè)粱锐，多用于插入和刪除
4．HashMap: 元素成對(duì)，元素可為空
5．HashTable: 元素成對(duì)扛邑，線程安全怜浅，元素不可為空
問題
1.HashSet為什么無(wú)序，ArrayList為什么有序
2.HashMap是如何解決Hash沖突（下標(biāo)沖突）的
3.ArrayList和Vector有何不同
4.HashMap初始容量是多少蔬崩，什么時(shí)候會(huì)擴(kuò)容恶座，會(huì)擴(kuò)容多少
自動(dòng)擴(kuò)容
初始大小:調(diào)用無(wú)參構(gòu)造函數(shù)時(shí)默認(rèn)的容量
加載因子:超過 (當(dāng)前容量*加載因子) 時(shí)會(huì)進(jìn)行擴(kuò)容
擴(kuò)容因子:擴(kuò)容時(shí)增加的容量為 (當(dāng)前容量*擴(kuò)容因子)
容器? ? ? ? ? 初始容量? ? ? ? ? ? ? ? ? 加載因子? ? ? ? ? ? ? 擴(kuò)容因子
ArrayList:? ? ? ? 10? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1? ? ? ? ? ? ? ? ? ? ? 0.5
HashMap:? ? ? 16? ? ? ? ? ? ? ? ? ? ? ? ? ? 0.75? ? ? ? ? ? ? ? ? ? 1
HashSet:? ? 同HashMap
一般而言, 以哈希表 (鏈表+數(shù)組) 作為底層數(shù)據(jù)結(jié)構(gòu)的容器, 當(dāng)元素超過加載因子，同時(shí)每個(gè)Entry(或者叫桶)里面至少有一個(gè)元素的時(shí)候就會(huì)進(jìn)行擴(kuò)容(1.7)沥阳。,如HashMap,HashSet(默認(rèn)16跨琳，超過12時(shí)擴(kuò)容兩倍)
以數(shù)組作為底層數(shù)據(jù)結(jié)構(gòu)的容器, 當(dāng)元素超過數(shù)組大小時(shí)會(huì)進(jìn)行擴(kuò)容,如ArrayList
以鏈表作為底層數(shù)據(jù)結(jié)構(gòu)的容器, 容量沒有限制, 不會(huì)進(jìn)行擴(kuò)容,如LinkedList,TreeMap
2.map
子類:hashmap,hashtable,linkedhashmap,TreeMap
2.1hashmap與hashtable
--HashMap和Hashtable的區(qū)別
線程安全性，同步(synchronization)桐罕，以及速度脉让。
HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行
Hashtable是synchronized功炮，這意味著Hashtable是線程安全的溅潜，Java 5提供了ConcurrentHashMap，它是HashTable的替代薪伏，比HashTable的擴(kuò)展性更好
HashMap可以使用collections.synchronizedMap實(shí)現(xiàn)同步
存放數(shù)據(jù)
indexFor是通過key的hash值&當(dāng)前數(shù)組長(zhǎng)度-1獲得元素下標(biāo)
元素個(gè)數(shù)超過臨界值滚澜，擴(kuò)容并重新計(jì)算下標(biāo)
重新計(jì)算臨界值，最大容量為int類型的最大值（2的31次方-1）
hash沖突
,hashmap底層是散列表嫁怀，散列表要解決的一個(gè)問題就是散列值的沖突問題设捐，通常是兩種方法：鏈表法和開放地址法借浊。鏈表法就是將相同hash值的對(duì)象組織成一個(gè)鏈表放在hash值對(duì)應(yīng)的槽位；開放地址法是通過一個(gè)探測(cè)算法萝招，當(dāng)某個(gè)槽位已經(jīng)被占據(jù)的情況下繼續(xù)查找下一個(gè)可以使用的槽位蚂斤。HashMap采用的鏈表法的方式，鏈表是單向鏈表即寒。這也是為什么用散列表
下標(biāo)下取出元素橡淆，將舊元素放到新元素的next中
存放空key
永遠(yuǎn)放在數(shù)組的第一位
獲取數(shù)據(jù)
通過key的hash值&當(dāng)前數(shù)組長(zhǎng)度-1獲得元素下標(biāo),下標(biāo)中的entry可能是多個(gè)元素，所以用的是循環(huán)母赵，比對(duì)key相同并且hash值相同的元素取出
LinkedHashMap
LinkedHashMap是HashMap的子類逸爵，與HashMap有著同樣的存儲(chǔ)結(jié)構(gòu)，但它加入了一個(gè)雙向鏈表的頭結(jié)點(diǎn)凹嘲，將所有put到LinkedHashmap的節(jié)點(diǎn)一一串成了一個(gè)雙向循環(huán)鏈表师倔，因此它保留了節(jié)點(diǎn)插入的順序，可以使節(jié)點(diǎn)的輸出順序與輸入順序相同周蹭，put方法用的父類hashmap的put方法趋艘，重寫了recordAccess方法
TreeMap
TreeMap 的實(shí)現(xiàn)使用了紅黑樹數(shù)據(jù)結(jié)構(gòu)，也就是一棵自平衡的排序二叉樹凶朗，這樣就可以保證快速檢索指定節(jié)點(diǎn)瓷胧。對(duì)于 TreeMap 而言，它采用一種被稱為“紅黑樹”的排序二叉樹來(lái)保存 Map 中每個(gè) Entry —— 每個(gè) Entry 都被當(dāng)成“紅黑樹”的一個(gè)節(jié)點(diǎn)對(duì)待棚愤。
因此它便有一些擴(kuò)展的方法搓萧，比如firstKey(),lastKey()等
3.List
3.1ArrayList與linkedList
1.ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)宛畦。
2.對(duì)于隨機(jī)訪問get和set瘸洛，ArrayList覺得優(yōu)于LinkedList，因?yàn)長(zhǎng)inkedList要移動(dòng)指針次和。
3.對(duì)于新增和刪除操作add和remove反肋，LinedList比較占優(yōu)勢(shì)，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)踏施。
arraylist
先對(duì)元素?cái)?shù)量+1
當(dāng)前元素位置-元素?cái)?shù)量>0,就是數(shù)據(jù)位置不夠了石蔗，開始擴(kuò)容
>>1相當(dāng)于除以2
LinkedList
Linkedlist有add,addFirst和addLast方法，add和adLast方法相同
3.2ArrayList與Vector
Vector與ArrayList一樣畅形，也是通過數(shù)組實(shí)現(xiàn)的抓督，不同的是它支持線程的同步，即某一時(shí)刻只有一個(gè)線程能夠?qū)慥ector束亏，避免多線程同時(shí)寫而引起的不一致性铃在，但實(shí)現(xiàn)同步需要很高的花費(fèi)，因此，訪問它比訪問ArrayList慢定铜。
CopyOnWriteArrayList
CopyOnWrite容器即寫時(shí)復(fù)制的容器阳液。通俗的理解是當(dāng)我們往一個(gè)容器添加元素的時(shí)候，不直接往當(dāng)前容器添加揣炕，而是先將當(dāng)前容器進(jìn)行Copy帘皿，復(fù)制出一個(gè)新的容器，然后新的容器里添加元素畸陡，添加完元素之后鹰溜，再將原容器的引用指向新的容器。這樣做的好處是我們可以對(duì)CopyOnWrite容器進(jìn)行并發(fā)的讀丁恭，而不需要加鎖曹动，因?yàn)楫?dāng)前容器不會(huì)添加任何元素。所以CopyOnWrite容器也是一種讀寫分離的思想牲览，讀和寫不同的容器
添加的時(shí)候是需要加鎖的墓陈，否則多線程寫的時(shí)候會(huì)Copy出N個(gè)副本出來(lái)
讀的時(shí)候不需要加鎖，如果讀的時(shí)候有多個(gè)線程正在向CopyOnWriteArrayList添加數(shù)據(jù)第献，讀還是會(huì)讀到舊的數(shù)據(jù)贡必，因?yàn)閷懙臅r(shí)候不會(huì)鎖住舊的
Stack
Stack實(shí)際上也是通過數(shù)組去實(shí)現(xiàn)的。
執(zhí)行push時(shí)(即庸毫，將元素推入棧中)仔拟，是通過將元素追加的數(shù)組的末尾中。
執(zhí)行peek時(shí)(即飒赃，取出棧頂元素利花，不執(zhí)行刪除)，是返回?cái)?shù)組末尾的元素盒揉。
執(zhí)行pop時(shí)(即晋被，取出棧頂元素兑徘，并將該元素從棧中刪除)刚盈，是取出數(shù)組末尾的元素，然后將該元素從數(shù)組中刪除挂脑。
Stack繼承于Vector藕漱，意味著Vector擁有的屬性和功能，Stack都擁有
3.Set
子類:HashSet,LinkedHashSet,TreeSet 與List不同的是set底層是map實(shí)現(xiàn)的肋联，所以不可重復(fù)
HsahSet
HashSet 的絕大部分方法都是通過調(diào)用 HashMap 的方法來(lái)實(shí)現(xiàn)的，因此 HashSet 和 HashMap 兩個(gè)集合在實(shí)現(xiàn)本質(zhì)上是相同的刁俭。
它只是封裝了一個(gè) HashMap 對(duì)象來(lái)存儲(chǔ)所有的集合元素橄仍，所有放入 HashSet 中的集合元素實(shí)際上由 HashMap 的 key 來(lái)保存，而 HashMap 的 value 則存儲(chǔ)了一個(gè) PRESENT，它是一個(gè)靜態(tài)的 Object 對(duì)象侮繁。
4.Collections和Arrays
想必大家不會(huì)忘記“折半查找”虑粥、“排序”等經(jīng)典算法吧，Collections類提供了豐富的靜態(tài)方法幫助我們輕松完成這些煩人的工作：
binarySearch：折半查找宪哩。傳入list和要尋找的值娩贷，返回元素下標(biāo),需要保證是有序的，也就是需要先排序sort(List list)
sort(List list)：對(duì)List里的元素根據(jù)自然升序排序
reverse(List list)：反轉(zhuǎn)指定List集合中元素的順序
shuffle(List list)：對(duì)List中的元素進(jìn)行隨機(jī)排序（洗牌）
sort(List list, Comparator c)：自定義比較器進(jìn)行排序
swap(List list, int i, int j)：將指定List集合中i處元素和j出元素進(jìn)行交換
rotate(List list, int distance)：將所有元素向右移位指定長(zhǎng)度锁孟，如果distance等于size那么結(jié)果不變
max(Collection coll)：返回最大元素
max(Collection coll, Comparator comp)：根據(jù)自定義比較器彬祖，返回最大元素
min(Collection coll)：返回最小元素
min(Collection coll, Comparator comp)：根據(jù)自定義比較器，返回最小元素
fill(List list, Object obj)：使用指定對(duì)象填充
frequency(Collection Object o)：返回指定集合中指定對(duì)象出現(xiàn)的次數(shù)
replaceAll(List list, Object old, Object new)：替換
Collections還有一個(gè)重要功能就是“封裝器”（Wrapper）品抽，它提供了一些方法可以把一個(gè)集合轉(zhuǎn)換成一個(gè)特殊的集合储笑，如下：
unmodifiableXXX：轉(zhuǎn)換成只讀集合，這里XXX代表六種基本集合接口：Collection桑包、List南蓬、Map、Set哑了、SortedMap和SortedSet赘方。如果你對(duì)只讀集合進(jìn)行插入刪除操作，將會(huì)拋出UnsupportedOperationException異常弱左。
synchronizedXXX：轉(zhuǎn)換成同步集合窄陡。
singleton：創(chuàng)建一個(gè)僅有一個(gè)元素的集合，這里singleton生成的是單元素Set拆火，
singletonList和singletonMap分別生成單元素的List和Map跳夭。
空集：由Collections的靜態(tài)屬性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示们镜。
6.commons collectionUtils
集合判斷：
例1: 判斷集合是否為空:
CollectionUtils.isEmpty(null): true
CollectionUtils.isEmpty(new ArrayList()): true
CollectionUtils.isEmpty({a,b}): false
例2: 判斷集合是否不為空:
CollectionUtils.isNotEmpty(null): false
CollectionUtils.isNotEmpty(new ArrayList()): false
CollectionUtils.isNotEmpty({a,b}): true
2個(gè)集合間的操作：
集合a: {1,2,3,3,4,5}
集合b: {3,4,4,5,6,7}
CollectionUtils.union(a, b)(并集): {1,2,3,3,4,4,5,6,7}
CollectionUtils.intersection(a, b)(交集): {3,4,5}
CollectionUtils.disjunction(a, b)(交集的補(bǔ)集): {1,2,3,4,6,7}
CollectionUtils.disjunction(b, a)(交集的補(bǔ)集): {1,2,3,4,6,7}
CollectionUtils.subtract(a, b)(A與B的差): {1,2,3}
CollectionUtils.subtract(b, a)(B與A的差): {4,6,7}
3.其他
CollectionUtils.unmodifiableCollection(c);? 不可修改的集合
問題
1.HashSet為什么無(wú)序币叹，ArrayList為什么有序
2.HashMap是如何解決Hash沖突（下標(biāo)沖突）的
3.ArrayList和Vector有何不同
4.HashMap初始容量是多少，什么時(shí)候會(huì)擴(kuò)容模狭，會(huì)擴(kuò)容多少
