Set和Map
1.Set和Map的關(guān)系
首先Set是一種集合元素?zé)o序纽帖，不可重復(fù)的集合。而Map則代表一種有多個(gè)key-value對(duì)組成的集合誉己，Map集合類似于傳統(tǒng)的關(guān)聯(lián)數(shù)據(jù)衣盾∈霸停看起來他們沒喲什么關(guān)聯(lián)劲绪，實(shí)際上Set和Map是有莫大的關(guān)聯(lián)的∨璩啵可以說Map是Set集合的擴(kuò)展贾富。
當(dāng)我們只看Map的Key時(shí)，會(huì)發(fā)現(xiàn)所有的key不能重復(fù)牺六，key之間沒有順序颤枪。也就是說將Map所有的key集合起來就組成了一個(gè)set集合。Map也提供了如下方法來返回組成的set集合
Set<K> keySet()
對(duì)于一個(gè)Map集合而言淑际，它本質(zhì)上是一個(gè)關(guān)聯(lián)數(shù)組畏纲，關(guān)聯(lián)數(shù)組中的key-value對(duì)之間有嚴(yán)格的對(duì)應(yīng)關(guān)系扇住，那將key-value對(duì)捆綁在一起對(duì)待，如下所示：
2.HashMap和HashSet
在HashSet里盗胀，系統(tǒng)采用Hash算法決定集合元素的存儲(chǔ)位置艘蹋，這樣可以保證快速存，取集合元素票灰；對(duì)于HashMap而言女阀，系統(tǒng)將value當(dāng)初key的‘附屬物’，系統(tǒng)根據(jù)Hash算法開決定key的存儲(chǔ)位置屑迂，這個(gè)可以保證快速存浸策，取集合key,而value總是緊隨key存儲(chǔ)。
集合號(hào)稱存儲(chǔ)的是Java對(duì)象惹盼，但實(shí)際上并不會(huì)真正將Java對(duì)象放入Set集合中庸汗，而只是在Set集合中保留這些對(duì)象的引用而己。也就是說手报，Java集合實(shí)際上是多個(gè)引用變量所組成的集合蚯舱，這些引用變量指向?qū)嶋H的Java對(duì)象。對(duì)于java集合他只是多個(gè)引用變量的集合昧诱。
當(dāng)程序試圖將一個(gè)key-value對(duì)放入HashMap中時(shí)晓淀，首先根據(jù)該key的hashCade()返回值決定該Entry的存儲(chǔ)位置—如果兩個(gè)Entry的key的hashCade返回值相同，那么它們的存儲(chǔ)位置相同:如果這兩個(gè)Entry的key通過equals比較返回true盏档，則新添加Entry的value將覆蓋集合中原有Entry的value凶掰，但key不會(huì)覆蓋;如果這兩個(gè)Entry的key通過equal比較返回false ,則新添加的Entry將與集合中原有的Entry形成Entry鏈，而且新添加的Entry位于Entry鏈的頭部
當(dāng)系統(tǒng)開始初始化HashMap時(shí)蜈亩，系統(tǒng)會(huì)創(chuàng)建一個(gè)長(zhǎng)度為capacity的Entry數(shù)組懦窘。這個(gè)數(shù)組可以存儲(chǔ)元素的位置被稱為“桶(bucket)”,每個(gè)bucket都有其指定的索引，系統(tǒng)可以根據(jù)其索引快速訪問該bucket里存儲(chǔ)的元素稚配。
無論何時(shí)畅涂，HashMap的每一個(gè)“桶”只存儲(chǔ)一個(gè)元素(即一個(gè)Entry).由于Entry對(duì)象可以包含一個(gè)引用變量（就是Entry構(gòu)造器的最后一個(gè)參數(shù)）用于指向下一個(gè)Entry，因此可能出現(xiàn)：HashMap的bucket中只有一個(gè)Entry,但這個(gè)Entry指向另一個(gè)Entry這就形成一個(gè)Entry鏈道川，如圖:
HashMap在每一個(gè)bucket里只有一個(gè)Entry,所以可以根據(jù)索引快速取出該bucket里的Enrty.當(dāng)發(fā)生hash沖突時(shí)午衰，單個(gè)bucket里存儲(chǔ)的不是一個(gè)Entry,而是一個(gè)Entry鏈，系統(tǒng)會(huì)按順序遍歷每個(gè)Entry,知道找到想搜到的Entry為止冒萄，即使要搜索的末端臊岸，系統(tǒng)也會(huì)循環(huán)到最后找到該元素。
3.TreeMap和TreeSet
TreeSet底層實(shí)際使用的容器就是TrenMap.絕大部分的方法都是直接調(diào)用TreeMap的方法來實(shí)現(xiàn)的尊流。而對(duì)于TreeMap而言帅戒，它采用一種被稱為‘紅黑樹’的排序二叉樹來保存Map中的每個(gè)Entry即每個(gè)Entry都是紅黑樹的一個(gè)節(jié)點(diǎn)。
對(duì)于TreeMap向言崖技，由于它底層采用一棵紅黑樹來保存集合中的Entry逻住，這意味著TreeMap添加元素钟哥、取出元素的性能都比HashMap低。當(dāng)TreeMag添加元素時(shí)瞎访，需要通過循壞找到新
增Entry的插入位置腻贰，因此比較耗性能;當(dāng)從TreeMap中取出元素時(shí)，需要通過循環(huán)才能找到合適的Entry装诡，也比較耗性能·但TreeMap, TreeSet相比HashMag,HashSet的優(yōu)勢(shì)在于:'TreeMap中的所有Entry總是按key根據(jù)指定的排序規(guī)則保持有序狀態(tài)银受，TreeSet中的所有元素總是根據(jù)指定的排序規(guī)則保持有序狀態(tài)。
Map和List
1.Map的values()方法
不管是HashIvlap鸦采，還是TreeMap宾巍，它們的values()方法都可返回其所有value組成的Collection集合。按照通常理解渔伯，這個(gè)Collection集合應(yīng)該是一個(gè)List集合顶霞，因?yàn)镸ap的多個(gè)valu。允許重復(fù)锣吼。
但實(shí)際上选浑，HashMap,TreeMap的values()方法的實(shí)現(xiàn)要更巧妙。這兩個(gè)Mad對(duì)象的values()方法返回的是一個(gè)不存儲(chǔ)元素的Collection集合玄叠，當(dāng)程序遍歷Collection集合時(shí)古徒，實(shí)際上就是遍歷Map對(duì)象的value
HashMap和TreeMap的values()方法并未把Map中的value重新組合成一個(gè)包含元素的集合對(duì)象，這樣就可以降低系統(tǒng)內(nèi)存開銷读恃。
2.Map和List的關(guān)系
- 從底層實(shí)現(xiàn)來看隧膘，Set和Map很相似；從用法的角度來看寺惫，Map和List也有很大的相似之處疹吃。
1.Map接口提供了get(K key)方法，允許Map對(duì)象根據(jù)key來取得value.
2.List接口提供了get(int index)方法西雀，允許list對(duì)象根據(jù)元素索引來取得value
Map和List在底層實(shí)現(xiàn)上沒有太大的相似之處萨驶，只是用法有一些相似之處。
ArrayList和LinkedList
1.Vector和ArrayList的區(qū)別
Vector和ArrayList這個(gè)兩個(gè)集合類的本質(zhì)并沒有太大的不同艇肴，它們都實(shí)現(xiàn)了List接口腔呜，而且底層都是基于Java數(shù)組來存儲(chǔ)集合元素的。
此外從序列化機(jī)制的角度看再悼，ArrayList的實(shí)現(xiàn)比Vector的實(shí)現(xiàn)更安全
另外Vector是ArrayList的線程安全版本核畴，ArrayList和Vector覺大部分方法的實(shí)現(xiàn)都是相同的，只是Vector的方法增加了synchronized修飾帮哈。
2.ArrayList和LinkedList的實(shí)現(xiàn)差異
List代表一種線性表的數(shù)據(jù)結(jié)構(gòu)。ArrayList則是一種順序存儲(chǔ)的線性表锰镀，ArrayList底層采用數(shù)組來保存每個(gè)集合元素娘侍，LinkedList則是一種鏈?zhǔn)酱鎯?chǔ)的線性表咖刃，其本質(zhì)上就是一個(gè)雙向鏈表，但它不僅實(shí)現(xiàn)了List接口憾筏，還實(shí)現(xiàn)了Deque接口嚎杨。也就是說，LinkedList既可以當(dāng)成雙向鏈表使用氧腰，也可以當(dāng)成隊(duì)列使用枫浙，還可以當(dāng)成棧來使用(Deque代表雙端隊(duì)列，既具有隊(duì)列的特征.也具有棧的特征)古拴。
ArrayList
因?yàn)锳rrayList底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組箩帚，所以我們插入元素是需要完成兩件事:
- 保證ArrayList底層封裝的數(shù)組長(zhǎng)度大于集合數(shù)據(jù)長(zhǎng)度
- 插入之前將所有元素“整體搬家”，向后移動(dòng)一格
同理在刪除元素是也要對(duì)元素進(jìn)行“整體搬家”黄痪，這就導(dǎo)致增加和刪除的性能非常差紧帕，當(dāng)時(shí)在取出數(shù)據(jù)元素時(shí)，性能基本和數(shù)組是一樣的桅打。
LinkedList
因?yàn)長(zhǎng)inkedSet是采用雙向鏈表的是嗜，如果單純的添加某個(gè)節(jié)點(diǎn)性能是很好的，當(dāng)時(shí)如果需要指定索引處添加節(jié)點(diǎn)挺尾，LinkedList必須必須先找到索引處的節(jié)點(diǎn)鹅搪，這個(gè)搜索過程系統(tǒng)開銷也是不少的，刪除也同理遭铺，如下圖所示：
不過弊端是對(duì)于ArrayList而言丽柿，由于它底層采用數(shù)組來保存集合元素，因此可以直接根據(jù)數(shù)組索引取出index位置的元素;但對(duì)于LinkedList就比較麻煩掂僵，LinkedList必須逐個(gè)元素地搜索航厚，直到找到第index個(gè)元素為止。所以性能相對(duì)較低锰蓬。
3.ArrayList和LinkedList的性能分析和適用場(chǎng)景
當(dāng)程序需要以get(int index)獲取List集合指定的索引出的元素幔睬，ArrayList性能大大的優(yōu)于LinkedList。因?yàn)锳rrayList底層以數(shù)組來保存集合元素芹扭，所以調(diào)用get(int index)方法獲取指定索引處的元素時(shí)麻顶，底層實(shí)際調(diào)用elementData[index]來返回改元素，因此性能非常好舱卡，而LinkedList則必須逐個(gè)的搜索辅肾。
當(dāng)程序調(diào)用add(int index,Object obj)向List添加數(shù)據(jù)是，ArrayList需要“整體搬家”才能實(shí)現(xiàn)添加轮锥，而LinkedList需要找到索引而不用整體搬家矫钓，當(dāng)時(shí)找索引也需要消耗一些系統(tǒng)性能，因?yàn)樗侵饌€(gè)搜索。同理新娜，刪除也是這樣子赵辕。
當(dāng)添加的數(shù)據(jù)個(gè)數(shù)大于底層數(shù)組的長(zhǎng)度時(shí)，那么ArrayList必須創(chuàng)建一個(gè)長(zhǎng)度為原來長(zhǎng)度1.5倍的數(shù)組概龄，再由垃圾回收機(jī)制進(jìn)行回收还惠。這樣系統(tǒng)開銷也有點(diǎn)大了。而LinkedList就不存在這個(gè)問題私杜。
不過從大多數(shù)應(yīng)用場(chǎng)景來說ArrayList總體性能還是優(yōu)于LinkedList蚕键。
Iterator迭代器
1.Iterator實(shí)現(xiàn)類與迭代器模式
Java的lteratar和Enumeration兩個(gè)接口都是迭代器模式的代表之作，它們就是迭代器模式里的“迭代器接口”衰粹。所謂迭代器模式指的是锣光，系統(tǒng)為遍歷多種數(shù)據(jù)列表、集合寄猩，容器提供一個(gè)標(biāo)準(zhǔn)的“迭代器接口”嫉晶，這些數(shù)據(jù)列表、集合田篇、容器就可面向相同的“迭代器接口”編程替废，通過相同的迭代器接口訪問不同數(shù)據(jù)列表‘集合、容器里的數(shù)據(jù).不同的數(shù)據(jù)列表泊柬、集合椎镣、容器如何實(shí)現(xiàn)這個(gè)“迭代器接口”，
則交給各數(shù)據(jù)列表兽赁、集合状答、容器自己完成。
2.迭代是刪除指定元素
對(duì)于TreeSet, HashSet等Set集合而言刀崖，當(dāng)使用Iterator遍歷它們時(shí)惊科，如果正在遍歷最后一個(gè)集合元素，那么使用Set集合的remove()方法刪除集合的任意元素并不會(huì)引發(fā)ConcurrentModificatianException異常亮钦，當(dāng)正在遍歷其他元素時(shí)刪除集合的任意元素都將引發(fā)該異常馆截。
