集合與數(shù)組

數(shù)組（可以存儲基本數(shù)據(jù)類型）是用來存現(xiàn)對象的一種容器，但是數(shù)組的長度固定秽褒，不適合在對象數(shù)量未知的情況下使用壶硅。

集合（只能存儲對象威兜，對象類型可以不一樣）的長度可變，可在多數(shù)情況下使用庐椒。

集合類存放于java.util包中椒舵。

集合類存放的都是對象的引用，而非對象本身约谈，出于表達(dá)上的便利笔宿，我們稱集合中的對象就是指集合中對象的引用（reference)。

集合類型主要有3種：Set(集）窗宇、List(列表）和Map(映射)措伐。

層次關(guān)系

如圖所示：圖中，實(shí)線邊框的是實(shí)現(xiàn)類军俊，折線邊框的是抽象類侥加，而點(diǎn)線邊框的是接口;

Collection接口是集合類的根接口，Java中沒有提供這個接口的直接的實(shí)現(xiàn)類粪躬。但是卻讓其被繼承產(chǎn)生了兩個接口担败，就是Set和List。Set中不能包含重復(fù)的元素镰官。List是一個有序的集合提前，可以包含重復(fù)的元素，提供了按索引訪問的方式泳唠。

Map是Java.util包中的另一個接口狈网，它和Collection接口沒有關(guān)系，是相互獨(dú)立的笨腥，但是都屬于集合類的一部分拓哺。Map包含了key-value對。Map不能包含重復(fù)的key脖母，但是可以包含相同的value士鸥。

Iterator，所有的集合類谆级，都實(shí)現(xiàn)了Iterator接口烤礁，這是一個用于遍歷集合中元素的接口，主要包含以下三種方法：

1.hasNext()是否還有下一個元素肥照。

2.next()返回下一個元素脚仔。

3.remove()刪除當(dāng)前元素。

重要的接口和類簡介

1舆绎、List（有序鲤脏、可重復(fù)）

List里存放的對象是有序的，同時也是可以重復(fù)的亿蒸，List關(guān)注的是索引凑兰，擁有一系列和索引相關(guān)的方法，查詢速度快边锁。因?yàn)橥鵏ist集合里插入或刪除數(shù)據(jù)時姑食，會伴隨著后面數(shù)據(jù)的移動，所有插入刪除數(shù)據(jù)速度慢茅坛。

2音半、Set（無序、不能重復(fù)）

Set里存放的對象是無序贡蓖，不能重復(fù)的曹鸠，集合中的對象不按特定的方式排序，只是簡單地把對象加入集合中斥铺。

3彻桃、Map（鍵值對、鍵唯一晾蜘、值不唯一）

Map集合中存儲的是鍵值對邻眷，鍵不能重復(fù)，值可以重復(fù)剔交。根據(jù)鍵得到值肆饶，對map集合遍歷時先得到鍵的set集合，對set集合進(jìn)行遍歷岖常，得到相應(yīng)的值驯镊。

總的說來，Java API中所用的集合類竭鞍，都是實(shí)現(xiàn)了Collection接口板惑，他的一個類繼承結(jié)構(gòu)如下：

Collection<--List<--Vector

Collection<--List<--ArrayList

Collection<--List<--LinkedList

Collection<--Set<--HashSet

Collection<--Set<--HashSet<--LinkedHashSet

Collection<--Set<--SortedSet<--TreeSet

Vector : 基于Array的List，其實(shí)就是封裝了Array所不具備的一些功能方便我們使用笼蛛，它不可能走出Array的限制洒放。性能也就不可能超越Array。所以滨砍，在可能的情況下往湿，我們要多運(yùn)用Array。另外很重要的一點(diǎn)就是Vector“synchronized”的惋戏，這個也是Vector和ArrayList的唯一的區(qū)別领追。ArrayList：同Vector一樣是一個基于數(shù)組實(shí)現(xiàn)的，但是不同的是ArrayList不是同步的响逢。所以在性能上要比Vector優(yōu)越一些绒窑，但是當(dāng)運(yùn)行到多線程環(huán)境中時，可需要自己在管理線程的同步問題舔亭。LinkedList：LinkedList不同于前面兩種List些膨，它不是基于Array的蟀俊，所以不受Array性能的限制。它每一個節(jié)點(diǎn)（Node）都包含兩方面的內(nèi)容：1.節(jié)點(diǎn)本身的數(shù)據(jù)（data）订雾；2.下一個節(jié)點(diǎn)的信息（nextNode）肢预。所以當(dāng)對LinkedList做添加，刪除動作的時候就不用像基于Array的List一樣洼哎，必須進(jìn)行大量的數(shù)據(jù)移動烫映。只要更改nextNode的相關(guān)信息就可以實(shí)現(xiàn)了。這就是LinkedList的優(yōu)勢噩峦。

List總結(jié)

1. 所有的List中只能容納單個不同類型的對象組成的表锭沟，而不是Key－Value鍵值對。例如：[ tom,1,c ]识补；

2. 所有的List中可以有相同的元素族淮，例如Vector中可以有 [ tom,koo,too,koo ]；

3. 所有的List中可以有null元素李请，例如[ tom,null,1 ]瞧筛；

4. 基于Array的List（Vector，ArrayList）適合查詢导盅，而LinkedList（鏈表）適合添加较幌，刪除操作。

HashSet：雖然Set同List都實(shí)現(xiàn)了Collection接口白翻，但是他們的實(shí)現(xiàn)方式卻大不一樣乍炉。List基本上都是以Array為基礎(chǔ)。但是Set則是 在HashMap的基礎(chǔ)上來實(shí)現(xiàn)的滤馍，這個就是Set和List的根本區(qū)別岛琼。HashSet的存儲方式是把HashMap中的Key作為Set的對應(yīng)存儲項(xiàng)词裤√枧欤看看 HashSet的add（Object obj）方法的實(shí)現(xiàn)就可以一目了然了。

public boolean add(Object obj)

{

return map.put(obj, PRESENT) == null;

}

這個也是為什么在Set中不能像在List中一樣有重復(fù)的項(xiàng)的根本原因崎页，因?yàn)镠ashMap的key是不能有重復(fù)的阁苞。

LinkedHashSet：HashSet的一個子類困檩，一個鏈表。

TreeSet：SortedSet的子類那槽，它不同于HashSet的根本就是TreeSet是有序的悼沿。它是通過SortedMap來實(shí)現(xiàn)的。（HashSet是無序的,TreeSet是有序的）

Set總結(jié)

1. Set實(shí)現(xiàn)的基礎(chǔ)是Map（HashMap）骚灸；

2. Set中的元素是不能重復(fù)的糟趾，如果使用add(Object obj)方法添加已經(jīng)存在的對象，則會覆蓋前面的對象為什么要使用集合類，當(dāng)你事先不知道要存放數(shù)據(jù)的個數(shù)义郑，或者你需要一種比數(shù)組下標(biāo)存取機(jī)制更靈活的方法時蝶柿，你就需要用到集合類。

理解集合類

(1)集

集（Set）是最簡單的一種集合非驮，它的對象不按特定方式排序只锭，只是簡單的把對象加入集合中，就像往口袋里放東西院尔。

對集中成員的訪問和操作是通過集中對象的引用進(jìn)行的，所以集中不能有重復(fù)對象喉誊。

集也有多種變體邀摆，可以實(shí)現(xiàn)排序等功能，如TreeSet伍茄，它把對象添加到集中的操作將變?yōu)榘凑漳撤N比較規(guī)則將其插入到有序的對象序列中栋盹。它實(shí)現(xiàn)的是SortedSet接口，也就是加入了對象比較的方法敷矫。通過對集中的對象迭代例获，我們可以得到一個升序的對象集合。

(2)列表

列表的主要特征是其對象以線性方式存儲曹仗，沒有特定順序榨汤，只有一個開頭和一個結(jié)尾，當(dāng)然怎茫，它與根本沒有順序的集是不同的收壕。

列表在數(shù)據(jù)結(jié)構(gòu)中分別表現(xiàn)為：數(shù)組和向量、鏈表轨蛤、堆棧蜜宪、隊(duì)列。

關(guān)于實(shí)現(xiàn)列表的集合類祥山，是我們?nèi)粘９ぷ髦薪?jīng)常用到的圃验，將在后邊的筆記詳細(xì)介紹。

(3)映射

映射與集或列表有明顯區(qū)別缝呕，映射中每個項(xiàng)都是成對的澳窑。映射中存儲的每個對象都有一個相關(guān)的關(guān)鍵字（Key）對象，關(guān)鍵字決定了 對象在映射中的存儲位置岳颇，檢索對象時必須提供相應(yīng)的關(guān)鍵字照捡，就像在字典中查單詞一樣。關(guān)鍵字應(yīng)該是唯一的话侧。

關(guān)鍵字本身并不能決定對象的存儲位置栗精，它需要對過一種散列(hashing)技術(shù)來處理，產(chǎn)生一個被稱作散列碼(hash code)的整數(shù)值，

散列碼通常用作一個偏置量悲立，該偏置量是相對于分配給映射的內(nèi)存區(qū)域起始位置的鹿寨，由此確定關(guān)鍵字/對象對的存儲位置。理想情況 下薪夕，散列處理應(yīng)該產(chǎn)生給定范圍內(nèi)均勻分布的值脚草，而且每個關(guān)鍵字應(yīng)得到不同的散列碼。

集合類簡介

java.util中共有13個類可用于管理集合對象原献，它們支持集馏慨、列表或映射等集合，以下是這些類的簡單介紹

集：

HashSet： 使用HashMap的一個集的實(shí)現(xiàn)姑隅。雖然集定義成無序写隶，但必須存在某種方法能相當(dāng)高效地找到一個對象。使用一個HashMap對象實(shí)現(xiàn)集的存儲和檢索操作是在固定時間內(nèi)實(shí)現(xiàn)的.

TreeSet： 在集中以升序?qū)ο笈判虻募膶?shí)現(xiàn)讲仰。這意味著從一個TreeSet對象獲得第一個迭代器將按升序提供對象慕趴。TreeSet類使用 了一個TreeMap.

列表：

Vector： 實(shí)現(xiàn)一個類似數(shù)組一樣的表，自動增加容量來容納你所需的元素鄙陡。使用下標(biāo)存儲和檢索對象就象在一個標(biāo)準(zhǔn)的數(shù)組中一樣 冕房。你也可以用一個迭代器從一個Vector中檢索對象。Vector是唯一的同步容器類??當(dāng)兩個或多個線程同時訪問時也是性能良好的趁矾。

Stack: 這個類從Vector派生而來耙册，并且增加了方法實(shí)現(xiàn)棧??一種后進(jìn)先出的存儲結(jié)構(gòu)。

LinkedList: 實(shí)現(xiàn)一個鏈表毫捣。由這個類定義的鏈表也可以像椕俨＃或隊(duì)列一樣被使用。

ArrayList: 實(shí)現(xiàn)一個數(shù)組培漏，它的規(guī)南澹可變并且能像鏈表一樣被訪問。它提供的功能類似Vector類但不同步牌柄。

映射：

Hashtable： 實(shí)現(xiàn)一個映象畸悬，所有的鍵必須非空。為了能高效的工作珊佣，定義鍵的類必須實(shí)現(xiàn)hashcode()方法和equal()方法蹋宦。這個類 是前面java實(shí)現(xiàn)的一個繼承，并且通常能在實(shí)現(xiàn)映象的其他類中更好的使用咒锻。

HashMap： 實(shí)現(xiàn)一個映象冷冗，允許存儲空對象，而且允許鍵是空（由于鍵必須是唯一的惑艇，當(dāng)然只能有一個）蒿辙。

WeakHashMap： 實(shí)現(xiàn)這樣一個映象：通常如果一個鍵對一個對象而言不再被引用拇泛，鍵/對象對將被舍棄。這與HashMap形成對照思灌，映象 中的鍵維持鍵/對象對的生命周期俺叭，盡管使用映象的程序不再有對鍵的引用，并且因此不能檢索對象泰偿。

TreeMap： 實(shí)現(xiàn)這樣一個映象熄守，對象是按鍵升序排列的。

Set和List都是由公共接口Collection擴(kuò)展而來耗跛，所以它們都可以使用一個類型為Collection的變量來引用裕照。這就意味著任何列表或集構(gòu)成的集合都可以用這種方式引用，只有映射類除外（但也不是完全排除在外调塌，因?yàn)榭梢詮挠成浍@得一個列表牍氛。）所以說，把一個

列表或集傳遞給方法的標(biāo)準(zhǔn)途徑是使用Collection類型的參數(shù)烟阐。

Vector和ArrayList

1.Vector是線程同步的，所以它也是線程安全的紊扬，而Arraylist是線程異步的蜒茄，是不安全的。如果不考慮到線程的安全因素餐屎，一般用Arraylist效率比較高檀葛。

2.如果集合中的元素的數(shù)目大于目前集合數(shù)組的長度時，vector增長率為目前數(shù)組長度的100%腹缩，而Arraylist增長率為目前數(shù)組長度的50%屿聋。如果在集合中使用數(shù)據(jù)量比較大的數(shù)據(jù)，用vector有一定的優(yōu)勢藏鹊。

3.如果查找一個指定位置的數(shù)據(jù)润讥，Vector和arraylist使用的時間是相同的，如果頻繁的訪問數(shù)據(jù)盘寡，這個時候使用Vector和Arraylist都可以楚殿。而如果移動一個指定位置會導(dǎo)致后面的元素都發(fā)生移動，這個時候就應(yīng)該考慮到使用Linklist,因?yàn)樗苿右粋€指定位置的數(shù)據(jù)時其它元素不移動竿痰。

ArrayList 和Vector是采用數(shù)組方式存儲數(shù)據(jù)脆粥，此數(shù)組元素數(shù)大于實(shí)際存儲的數(shù)據(jù)以便增加和插入元素，都允許直接序號索引元素影涉，但是插入數(shù)據(jù)要涉及到數(shù)組元素移動等內(nèi)存操作变隔，所以索引數(shù)據(jù)快，插入數(shù)據(jù)慢蟹倾，Vector由于使用了synchronized方法（線程安全）所以性能上比ArrayList要差匣缘，LinkedList使用雙向鏈表實(shí)現(xiàn)存儲，按序號索引數(shù)據(jù)需要進(jìn)行向前或向后遍歷，但是插入數(shù)據(jù)時只需要記錄本項(xiàng)的前后項(xiàng)即可孵户，所以插入數(shù)度較快萧朝。

Arraylist和Linkedlist

1.ArrayList是實(shí)現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)夏哭。

2.對于隨機(jī)訪問get和set检柬，ArrayList覺得優(yōu)于LinkedList，因?yàn)長inkedList要移動指針竖配。

3.對于新增和刪除操作add和remove何址，LinedList比較占優(yōu)勢，因?yàn)锳rrayList要移動數(shù)據(jù)进胯。?這一點(diǎn)要看實(shí)際情況的用爪。若只對單條數(shù)據(jù)插入或刪除，ArrayList的速度反而優(yōu)于LinkedList胁镐。但若是批量隨機(jī)的插入刪除數(shù)據(jù)偎血，LinkedList的速度大大優(yōu)于ArrayList. 因?yàn)锳rrayList每插入一條數(shù)據(jù)，要移動插入點(diǎn)及之后的所有數(shù)據(jù)盯漂。

HashMap與TreeMap

1.HashMap通過hashcode對其內(nèi)容進(jìn)行快速查找颇玷，而TreeMap中所有的元素都保持著某種固定的順序，如果你需要得到一個有序的結(jié)果你就應(yīng)該使用TreeMap（HashMap中元素的排列順序是不固定的）就缆。

2.在Map 中插入帖渠、刪除和定位元素，HashMap是最好的選擇竭宰。但如果您要按自然順序或自定義順序遍歷鍵空郊，那么TreeMap會更好。使用HashMap要求添加的鍵類明確定義了hashCode()和 equals()的實(shí)現(xiàn)切揭。

兩個map中的元素一樣狞甚，但順序不一樣，導(dǎo)致hashCode()不一樣廓旬。

同樣做測試：

在HashMap中入愧，同樣的值的map,順序不同，equals時嗤谚，false;

而在TreeMap中棺蛛，同樣的值的map,順序不同,equals時，true巩步，說明旁赊，TreeMap在equals()時是整理了順序了的。

HashTable與HashMap

1.同步性:Hashtable是線程安全的椅野，也就是說是同步的终畅，而HashMap是線程序不安全的籍胯，不是同步的。

2.HashMap允許存在一個為null的key离福，多個為null的value 杖狼。

3.Hashtable的key和value都不允許為null。