集合
集合類(lèi)是一種工具類(lèi)，存儲(chǔ)數(shù)量不等的對(duì)象击儡，可以實(shí)現(xiàn)棧塔沃，隊(duì)列等數(shù)據(jù)結(jié)構(gòu)⊙舻可以分為：Set：無(wú)序蛀柴，不可重復(fù)的集合； List：有序矫夯，重復(fù)的集合鸽疾； Queue：隊(duì)列集合實(shí)現(xiàn)； Map：具有映射關(guān)系的集合 四種训貌。
集合類(lèi)主要由：Collection和Map兩個(gè)接口派生而出.
Map保存的的每項(xiàng)數(shù)據(jù)都是由key-value對(duì)即兩個(gè)值組成制肮，key用來(lái)標(biāo)識(shí)集合里面的每項(xiàng)數(shù)據(jù)并且不可以重復(fù)，根據(jù)key值來(lái)獲取value數(shù)據(jù)递沪。
Stream
對(duì)java集合進(jìn)行操作豺鼻，將要處理的集合的元素看成一種流，流在管道中傳輸款慨，在管道的節(jié)點(diǎn)上進(jìn)行處理儒飒，并支持聚合操作。stream的聚合檩奠、消費(fèi)或收集操作只能進(jìn)行一次桩了，再次操作會(huì)報(bào)錯(cuò)。
Set集合
Set集合不能記住元素的添加順序埠戳，不允許包含重復(fù)元素井誉。
所有Set接口的內(nèi)部都是Map做支撐，
HashSet
按照Hash算法來(lái)存儲(chǔ)集合中的元素乞而，底層的數(shù)據(jù)結(jié)構(gòu)是Hash表送悔。
HashSet不是同步的。集合的元素值可以是空爪模。
根據(jù)hashCode值決定元素在集合中的存儲(chǔ)位置欠啤，HashSet判斷兩個(gè)對(duì)象相等的標(biāo)準(zhǔn)：兩個(gè)對(duì)象通過(guò)equals()方法比較相等，并且兩個(gè)對(duì)象的hashCode()方法返回值也相等屋灌。
兩個(gè)對(duì)象的hashCode值不同洁段，但是兩個(gè)對(duì)象的equals()方法返回相同，會(huì)把兩個(gè)對(duì)象保存在hash表的不同位置共郭。
兩個(gè)對(duì)象hashCode值相同祠丝，但是equals()方法比較不同疾呻，會(huì)在同一個(gè)位置用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)保存多個(gè)對(duì)象。
重寫(xiě)hashCode()方法的基本規(guī)則
兩個(gè)對(duì)象通過(guò)equals()方法比較返回true写半，這兩個(gè)對(duì)象的hashCode值也應(yīng)該相同岸蜗。
LinkedHashSet：是HashSet的子類(lèi)。也是根據(jù)hashCode值來(lái)決定元素在集合中的存儲(chǔ)位置叠蝇。使用雙重鏈表維護(hù)元素的插入次序璃岳。遍歷集合中的元素時(shí)會(huì)按元素的添加順序來(lái)訪(fǎng)問(wèn)集合中的元素。
TreeSet
是SortedSet接口的實(shí)現(xiàn)類(lèi)悔捶，可以確保集合元素處于排序狀態(tài)铃慷。不是根據(jù)元素的插入順序進(jìn)行排序，根據(jù)實(shí)際值的大小進(jìn)行排序蜕该。
TreeSet采用紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)集合元素犁柜。分為自然排序和定制排序。
自然排序：TreeSet調(diào)用集合元素的comparaTo()方法來(lái)比較元素之間的大小堂淡，然后按升序排列馋缅。敲重點(diǎn)：1. 加入TreeSet的元素都要實(shí)現(xiàn)Comparable接口 2.加入的最好都是同一個(gè)類(lèi)型的元素。3. 兩個(gè)元素相等的依據(jù)是兩個(gè)對(duì)象的comparaTo()方法返回為0淤齐；4. 注意不要修改可變對(duì)象的實(shí)例變量股囊。
兩個(gè)對(duì)象通過(guò)equals()方法返回true時(shí)，兩個(gè)對(duì)象的comparaTo()方法比較應(yīng)返回0更啄。
定制排序：在創(chuàng)建TreeSet集合時(shí)稚疹，創(chuàng)建一個(gè)Comparator對(duì)象，與TreeSet集合關(guān)聯(lián)祭务，Comparator負(fù)責(zé)排序邏輯内狗，通過(guò)Comparator接口的幫助，通過(guò)利用該函數(shù)式接口的compara()方法來(lái)實(shí)現(xiàn)义锥。
EnumSet
為枚舉類(lèi)設(shè)計(jì)的集合類(lèi)柳沙，所有元素必須是指定枚舉類(lèi)型的枚舉值。是有序的集合拌倍，以枚舉值在Enum類(lèi)中的定義順序來(lái)決定集合元素的順序赂鲤。不允許加入null元素。EnumSet沒(méi)有暴露任何構(gòu)造器來(lái)創(chuàng)建該類(lèi)的實(shí)例柱恤。
這三個(gè)Set的實(shí)現(xiàn)類(lèi)都是線(xiàn)程不安全的数初。
List集合
代表元素有序可以重復(fù)的集合。每個(gè)元素都有其對(duì)應(yīng)的順序索引梗顺，通過(guò)索引來(lái)訪(fǎng)問(wèn)指定位置的元素泡孩。List判斷兩個(gè)對(duì)象相等的標(biāo)準(zhǔn)：通過(guò)equals()方法比較返回true即可。
List的listIterator()方法：返回一個(gè)ListIterator對(duì)象寺谤，ListIterator接口繼承自Iterator接口仑鸥，提供了操作List集合的方法吮播。ListIterator增加了向前迭代的功能，還可以向List集合里面添加元素眼俊。
兩個(gè)實(shí)現(xiàn)類(lèi)：ArrayList和Vector意狠，都是基于數(shù)組實(shí)現(xiàn)的List類(lèi)。封裝了一個(gè)動(dòng)態(tài)的疮胖，允許再分配的Object[]數(shù)組摄职，可以設(shè)置數(shù)組的長(zhǎng)度，當(dāng)數(shù)組中的元素超過(guò)設(shè)置的數(shù)組長(zhǎng)度時(shí)获列，數(shù)組長(zhǎng)度會(huì)增加。
創(chuàng)建時(shí)不指定集合的大小時(shí)蛔垢，動(dòng)態(tài)的Object[]數(shù)組的長(zhǎng)度默認(rèn)為10击孩。
ArrayList：是線(xiàn)程不安全的，
Vector：是線(xiàn)程安全的鹏漆，性能低于A(yíng)rrayList巩梢。
ArrayDeque也是List的實(shí)現(xiàn)類(lèi)，同時(shí)也實(shí)現(xiàn)了Deque接口艺玲。實(shí)現(xiàn)了Deque接口括蝠，因此可以當(dāng)作棧來(lái)使用，它的底層也是基于數(shù)組的實(shí)現(xiàn)饭聚。
Queue集合
用于模擬隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)忌警。
PriorityQueue
隊(duì)列的實(shí)現(xiàn)類(lèi)，保存隊(duì)列元素的順序不是按加入隊(duì)列的順序秒梳，是按照隊(duì)列元素的大小進(jìn)行重新排序法绵。不允許加入null元素。有兩種排序方式：自然排序和定制排序酪碘。
Deque接口
是Queue接口的子接口朋譬，代表一個(gè)雙端隊(duì)列。包含一些棧方法兴垦。
ArrayDeque：基于數(shù)組實(shí)現(xiàn)的雙端隊(duì)列徙赢。可以當(dāng)作棧來(lái)使用探越。
LinkedList
是List接口的實(shí)現(xiàn)類(lèi)狡赐，還實(shí)現(xiàn)了Deque接口。內(nèi)部以鏈表的形式來(lái)保存集合中的元素扶关。
提供了List的功能阴汇，還提供了雙端隊(duì)列和棧的功能。
Map集合
保存具有映射關(guān)系的數(shù)據(jù)节槐，集合里面保存著兩組值搀庶，一組用于保存key拐纱，另一組保存value，key和value都可以是任何引用類(lèi)型的數(shù)據(jù)哥倔。key不允許重復(fù)秸架。key集的存儲(chǔ)形式和Set集合中元素的存儲(chǔ)形式相似。Map提供了一個(gè)Entry內(nèi)部類(lèi)來(lái)封裝key-value對(duì)咆蒿，在計(jì)算Entry存儲(chǔ)時(shí)只考慮Entry封裝的key东抹。
-
HashMap
線(xiàn)程不安全的實(shí)現(xiàn)。允許使用null值作為key和value沃测。 -
Hashtable
線(xiàn)程安全的Map實(shí)現(xiàn)缭黔。不允許使用null值作為key和value。
HashMap和Hashtable中用作key的對(duì)象必須實(shí)現(xiàn)hashCode()方法和equals()方法蒂破，并且這兩個(gè)map集合也不能保證其中的key-value的順序馏谨。
1. 判斷key值相等的標(biāo)準(zhǔn)：通過(guò)equals()方法返回true，hashCode值也相等附迷。2. 判斷兩個(gè)value相等的標(biāo)準(zhǔn)：只要兩個(gè)對(duì)象通過(guò)equals()方法比較返回true
-
LinkedHashMap
是HashMap的子類(lèi)惧互。使用雙向鏈表來(lái)維護(hù)key-value對(duì)的次序，與插入順序保持一致喇伯。 -
Properties
是Hashtable的子類(lèi)喊儡。處理屬性文件，將map對(duì)象和屬性文件關(guān)聯(lián)起來(lái)稻据。相對(duì)于key,value都是String類(lèi)型的Map艾猜。 -
SortedMap接口和TreeMap實(shí)現(xiàn)類(lèi)
TreeMap是一個(gè)紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)。key-value對(duì)作為紅黑樹(shù)的一個(gè)節(jié)點(diǎn)攀甚，在存儲(chǔ)key-value對(duì)時(shí)箩朴，會(huì)根據(jù)key對(duì)節(jié)點(diǎn)進(jìn)行排序。
自然排序
定制排序· -
WeakHashMap
key的類(lèi)型是WeakRerfence秋度，key被回收炸庞，key對(duì)應(yīng)的指向的對(duì)象會(huì)被從Map容器中移除。 -
IdentityHashMap
實(shí)現(xiàn)機(jī)制與HashMap基本相似荚斯，但在處理兩個(gè)key相等時(shí)：要求兩個(gè)key嚴(yán)格相等時(shí)才認(rèn)為兩個(gè)key相等埠居。 -
EnumHashMap
在內(nèi)部以數(shù)組形式存儲(chǔ)。不允許使用null作為key事期。
HashSet與HashMap
HashSet采用hash算法來(lái)決定集合中元素的存儲(chǔ)位置滥壕，通過(guò)hash算法控制集合的大小。
HashMap類(lèi)似HashSet兽泣，采用hash算法決定集合中key的存儲(chǔ)位置绎橘，也通過(guò)hash算法來(lái)增加key集合的大小。
遍歷集合
- Iterable接口的forEach()方法來(lái)遍歷集合：傳給該方法的參數(shù)是一個(gè)目標(biāo)類(lèi)型為Consumer類(lèi)型的Lambda表達(dá)式。
- Iterator遍歷集合元素：
Iterator對(duì)象是迭代器称鳞，必須依附于Collection對(duì)象涮较。
Iterator遍歷集合時(shí)，不是將集合元素本身傳給了Iterator迭代變量冈止，是將集合元素的值傳給了迭代變量狂票。
Iterator迭代訪(fǎng)問(wèn)集合的元素時(shí)，集合里的元素不能被改變熙暴，否則會(huì)引發(fā)ConcurrentModificationException異常闺属。只有使用Iterator的remove()方法刪除上一次next()方法返回的集合元素才可以。
Iterator采用快速失敗機(jī)制(fail-fast)周霉，在迭代過(guò)程中檢測(cè)到集合元素已經(jīng)被修改掂器，立即引發(fā)ConcurrentModification異常。
快速失敗機(jī)制(fail-fast)
對(duì)集合修改次數(shù)的期望值：
對(duì)集合的修改次數(shù):每次調(diào)用集合的add()方法或者remove()方法就會(huì)將該值加1或者減1俱箱。
修改次數(shù)的期望值剛剛開(kāi)始時(shí)是等于修改次數(shù)的唉匾。
檢查修改次數(shù)和修改次數(shù)的期望值是否相等，不等時(shí)拋出ConcurrentModificationException異常匠楚。
在Iterator的next()方法中，先會(huì)檢查修改次數(shù)和修改次數(shù)的期望值是否相等厂财，然后再得到集合里的下一個(gè)元素芋簿。
在Iterator實(shí)現(xiàn)類(lèi)的remove()方法中，刪除一個(gè)元素時(shí)璃饱，是調(diào)用集合自己的刪除函數(shù)与斤，并會(huì)將修改次數(shù)加一，并將修改次數(shù)的值賦值給修改次數(shù)的期望值荚恶。
沒(méi)有調(diào)用Iterator的remove()方法進(jìn)行刪除操作撩穿，使用集合的刪除函數(shù)來(lái)進(jìn)行刪除操作時(shí)，修改次數(shù)會(huì)加1谒撼，但是不會(huì)將修改次數(shù)的值賦值為修改次數(shù)的期望值食寡，導(dǎo)致修改次數(shù)的值和修改次數(shù)期望值的值不一致，在進(jìn)行下一次next()迭代時(shí)廓潜，會(huì)檢測(cè)出兩者不相等抵皱，然后拋出ConcurrentModificationException異常。
單線(xiàn)程環(huán)境下：將使用集合進(jìn)行刪除操作修改為使用Iterator對(duì)象進(jìn)行刪除就會(huì)正確辩蛋，不會(huì)拋出異常呻畸。
多線(xiàn)程環(huán)境下：就是使用Iterator的刪除函數(shù)進(jìn)行刪除也還是會(huì)拋出異常。
因?yàn)樵诙嗑€(xiàn)程環(huán)境下悼院，每個(gè)線(xiàn)程是不同的Iterator對(duì)象伤为，修改次數(shù)的期望值是線(xiàn)程私有的，修改次數(shù)是共享的据途。
當(dāng)一個(gè)線(xiàn)程使用Iterator對(duì)象進(jìn)行remove()刪除時(shí)绞愚，這時(shí)候共享的修改次數(shù)值和這個(gè)線(xiàn)程的修改次數(shù)期望值都會(huì)自增叙甸；但是其他線(xiàn)程的私有的修改次數(shù)期望值沒(méi)有自增，所以其他線(xiàn)程就會(huì)拋出ConcurrentModificationException異常了爽醋。
- Lambda表達(dá)式遍歷：類(lèi)似第一種蚁署。
- foreach循環(huán)遍歷
迭代變量是集合元素的值，不是集合本身蚂四。
使用循環(huán)進(jìn)行遍歷時(shí)光戈，也不能改變集合，否則會(huì)引發(fā)ConcurrentModificationException異常遂赠。
Hash算法
散列表
也叫哈希表久妆，基于高速存取角度設(shè)計(jì)的，是以空間換時(shí)間跷睦，其中的元素不是緊密排列的筷弦，可能存在空隙。
以一種鍵-值(key-indexed)存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)抑诸，輸入key烂琴，可查找到對(duì)應(yīng)的值。
通過(guò)關(guān)鍵碼值(key)直接進(jìn)行訪(fǎng)問(wèn)存放記錄(indexed值)的數(shù)組(散列表)蜕乡。把關(guān)鍵碼值通過(guò)映射函數(shù)(散列函數(shù))映射到散列表中的一個(gè)位置來(lái)訪(fǎng)問(wèn)散列表中的記錄奸绷。
表中存儲(chǔ)元素的位置稱(chēng)為桶。
哈希表包含的屬性
容量(capacity)：表中桶的數(shù)量层玲。
初始化容量：創(chuàng)建哈希表時(shí)桶的數(shù)量号醉。
尺寸：當(dāng)前哈希表中記錄的數(shù)量。
負(fù)載因子：等于尺寸/容量辛块。
負(fù)載極限：是一個(gè)0-1的數(shù)值畔派。默認(rèn)的負(fù)載極限為0.75。決定了hash表的最大填滿(mǎn)程度润绵。當(dāng)負(fù)載因子達(dá)到負(fù)載極限時(shí)线椰，哈希表會(huì)自動(dòng)成倍的增加桶的數(shù)量，并會(huì)將原有的對(duì)象重新分配尘盼，放入新的桶中士嚎。
hash沖突
兩個(gè)元素通過(guò)映射函數(shù)得到的在散列表中的存儲(chǔ)位置相同。
發(fā)生沖突的兩個(gè)元素稱(chēng)為同義詞悔叽。
解決沖突
取決于3點(diǎn)：
a.散列函數(shù)莱衩，散列函數(shù)計(jì)算得到的表中的存儲(chǔ)位置應(yīng)平均分布。
b.處理沖突的方法娇澎。
c.負(fù)載因子的大小笨蚁。
方法：
a.線(xiàn)性探測(cè)法：沖突后，線(xiàn)性向前探測(cè)，找到最近的一個(gè)空位置括细。
b.雙散列函數(shù)法：
CopyOnWriteArrayList
HashSet同步
LinkedHashSet的底層的鏈表
- ClassCastException：JVM在檢測(cè)到兩個(gè)類(lèi)型間轉(zhuǎn)換不兼容時(shí)引發(fā)的運(yùn)行時(shí)異常伪很。
