Java集合詳解

[if !supportLists]一爽彤、????[endif]集合的由來

通常推溃，我們的程序需要根據(jù)程序運行時才知道創(chuàng)建多少個對象昂利。但若非程序運行，程序開發(fā)階段铁坎，我們根本不知道到底需要多少個數(shù)量的對象蜂奸，甚至不知道它的準(zhǔn)確類型。為了滿足這些常規(guī)的編程需要厢呵，我們要求能在任何時候窝撵，任何地點創(chuàng)建任意數(shù)量的對象，而這些對象用什么來容納呢襟铭？我們首先想到了數(shù)組碌奉，但是數(shù)組只能放統(tǒng)一類型的數(shù)據(jù)，而且其長度是固定的寒砖，那怎么辦呢赐劣？集合便應(yīng)運而生了！

[if !supportLists]二哩都、????[endif]集合是什么魁兼？

　Java集合類存放于 java.util 包中，是一個用來存放對象的容器漠嵌。

注意：①咐汞、集合只能存放對象。比如你存一個 int 型數(shù)據(jù) 1放入集合中儒鹿，其實它是自動轉(zhuǎn)換成 Integer 類后存入的化撕，Java中每一種基本類型都有對應(yīng)的引用類型。

②约炎、集合存放的是多個對象的引用植阴，對象本身還是放在堆內(nèi)存中蟹瘾。

③、集合可以存放不同類型掠手，不限數(shù)量的數(shù)據(jù)類型憾朴。?????

[if !supportLists]三、????[endif]數(shù)組Array和集合的區(qū)別

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

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

[if !supportLists]四剖淀、????[endif]Java集合框架圖

圖一這個比較簡單

[if !vml]

[endif]

圖二完整

[if !vml]

[endif]

發(fā)現(xiàn)一個特點，上述所有的集合類纤房，除了 map 系列的集合纵隔，即左邊集合都實現(xiàn)了Iterator接口，這是一個用于遍歷集合中元素的接口炮姨，主要hasNext(),next(),remove()三種方法捌刮。它的一個子接口ListIterator在它的基礎(chǔ)上又添加了三種方法，分別是 add(),previous(),hasPrevious()舒岸。也就是說如果實現(xiàn)Iterator 接口绅作，那么在遍歷集合中元素的時候，只能往后遍歷蛾派，被遍歷后的元素不會再被遍歷到俄认，通常無序集合實現(xiàn)的都是這個接口，比如HashSet洪乍；而那些元素有序的集合眯杏，實現(xiàn)的一般都是 LinkedIterator接口，實現(xiàn)這個接口的集合可以雙向遍歷壳澳，既可以通過next()訪問下一個元素岂贩，又可以通過previous()訪問前一個 元素，比如ArrayList巷波。

list,set,map對比

接口子接口是否有序是否允許元素重復(fù)

Collection　　　　　　　　　　否

List 　　ArrayList否是

　　　　　　LinkedList否是

　　　　　　Vector否是

SetAbstractSet否否

　　HashSet否否

　　TreeSet是（用二叉排序樹）否

MapAbstractMap否使用key-value來映射和存儲數(shù)據(jù)萎津，key必須唯一，value可以重復(fù)

　　HashMap否

　　TreeMap是（用二叉排序樹）使用key-value來映射和存儲數(shù)據(jù)抹镊，key必須唯一锉屈，value可以重復(fù)

list（有序、可重復(fù)）

List里存放的對象是有序的髓考，同時也是可以重復(fù)的部念，List關(guān)注的是索引，擁有一系列和索引相關(guān)的方法，查詢速度快儡炼。因為往list集合里插入或刪除數(shù)據(jù)時妓湘，會伴隨著后面數(shù)據(jù)的移動，所有插入刪除數(shù)據(jù)速度慢乌询。

ArrayList

ArrayList是基于數(shù)組的榜贴，在初始化ArrayList時，會構(gòu)建空數(shù)組（Object[] elementData={}）妹田。ArrayList是一個無序的唬党，它是按照添加的先后順序排列，當(dāng)然鬼佣，他也提供了sort方法驶拱，如果需要對ArrayList進(jìn)行排序，只需要調(diào)用這個方法晶衷，提供Comparator比較器即可

add操作：

1）如果是第一次添加元素蓝纲，數(shù)組的長度被擴容到默認(rèn)的capacity，也就是10.

2) 當(dāng)發(fā)覺同時添加一個或者是多個元素晌纫，數(shù)組長度不夠時税迷，就擴容，這里有兩種情況：

只添加一個元素锹漱，例如：原來數(shù)組的capacity為10箭养，size已經(jīng)為10，不能再添加了哥牍。需要擴容毕泌，新的capacity=old capacity+old capacity>>1=10+10/2=15.即新的容量為15。

當(dāng)同時添加多個元素時砂心，原來數(shù)組的capacity為10懈词，size為10，當(dāng)同時添加6個元素時辩诞。它需要的min capacity為16坎弯，而按照capacity=old capacity+old

capacity>>1=10+10/2=15。new capacity小于min capacity译暂，則取min capacity抠忘。

對于添加，如果不指定下標(biāo)外永，就直接添加到數(shù)組后面崎脉，不涉及元素的移動，如果要添加到某個特定的位置伯顶，那需要將這個位置開始的元素往后挪一個位置囚灼，然后再對這個位置設(shè)置骆膝。

Remove操作：

Remove提供兩種，按照下標(biāo)和value灶体。

1）remove(int

index)：首先需要檢查Index是否在合理的范圍內(nèi)阅签。其次再調(diào)用System.arraycopy將index之后的元素向前移動。

2）remove(Object

o)：首先遍歷數(shù)組蝎抽，獲取第一個相同的元素政钟，獲取該元素的下標(biāo)。其次再調(diào)用System.arraycopy將index之后的元素向前移動樟结。

Get操作：

這個比較簡單养交，直接對數(shù)組進(jìn)行操作即可。

LinkedList

LinkedList是基于鏈表的瓢宦，它是一個雙向鏈表碎连，每個節(jié)點維護(hù)了一個prev和next指針。同時對于這個鏈表刁笙，維護(hù)了first和last指針破花，first指向第一個元素，last指向最后一個元素疲吸。LinkedList是一個無序的鏈表，按照插入的先后順序排序前鹅，不提供sort方法對內(nèi)部元素排序摘悴。

Add元素：

LinkedList提供了幾個添加元素的方法：addFirst、addLast舰绘、addAll蹂喻、add等，時間復(fù)雜度為O(1)捂寿。

Remove元素：

LinkedList提供了幾個移除元素的方法：removeFirst口四、removeLast、removeFirstOccurrence秦陋、remove等蔓彩，時間復(fù)雜度為O(1)。

Get元素：

根據(jù)給定的下標(biāo)index驳概，判斷它first節(jié)點赤嚼、last直接距離，如果index<size（數(shù)組元素個數(shù))/2,就從first開始顺又。如果大于更卒，就從last開始。這個和我們平常思維不太一樣稚照，也許按照我們的習(xí)慣蹂空，從first開始俯萌。這也算是一點小心的優(yōu)化吧。

遍歷

在類集中提供了以下四種的常見輸出方式：

1）Iterator：迭代輸出上枕，是使用最多的輸出方式咐熙。

2）ListIterator：是Iterator的子接口，專門用于輸出List中的內(nèi)容姿骏。

3）foreach輸出：JDK1.5之后提供的新功能糖声，可以輸出數(shù)組或集合。

4）for循環(huán)

代碼示例如下：

for的形式：for（int i=0;i<arr.size();i++）{...}

foreach的形式：?for（inti：arr）{...}

iterator的形式：

Iterator it = arr.iterator();

while(it.hasNext()){ object o =it.next(); ...}

Set（無序分瘦、不能重復(fù)）

Set里存放的對象是無序蘸泻，不能重復(fù)的，集合中的對象不按特定的方式排序嘲玫，只是簡單地把對象加入集合中悦施。

HashSet

HashSet是基于HashMap來實現(xiàn)的，操作很簡單去团，更像是對HashMap做了一次“封裝”抡诞，而且只使用了HashMap的key來實現(xiàn)各種特性，而HashMap的value始終都是PRESENT土陪。

HashSet不允許重復(fù)（HashMap的key不允許重復(fù)昼汗，如果出現(xiàn)重復(fù)就覆蓋），允許null值鬼雀，非線程安全顷窒。

構(gòu)造方法

HashSet()?構(gòu)造一個新的空 set，其底層HashMap 實例的默認(rèn)初始容量是 16源哩，加載因子是0.75鞋吉。HashSet(Collection c)

構(gòu)造一個包含指定 collection 中的元素的新 set。HashSet(int initialCapacity)?構(gòu)造一個新的空 set励烦，其底層HashMap 實例具有指定的初始容量和默認(rèn)的加載因子（0.75）谓着。HashSet(int initialCapacity, float loadFactor)構(gòu)造一個新的空 set，其底層HashMap 實例具有指定的初始容量和指定的加載因子坛掠。

方法

boolean add(E e)?如果此 set 中尚未包含指定元素赊锚，則添加指定元素。

void clear()

從此 set 中移除所有元素却音。** Object clone()?返回此 HashSet 實例的淺表副本：并沒有復(fù)制這些元素本身改抡。boolean contains(Object o)?如果此 set 包含指定元素，則返回true系瓢。boolean isEmpty()**如果此 set 不包含任何元素阿纤，則返回 true。** Iterator?iterator()?返回對此 set 中元素進(jìn)行迭代的迭代器夷陋。boolean remove(Object o)?如果指定元素存在于此 set 中欠拾，則將其移除胰锌。int size()**返回此 set 中的元素的數(shù)量（set的容量）。

TreeSet

基于 TreeMap 的 NavigableSet 實現(xiàn)藐窄。使用元素的自然順序?qū)υ剡M(jìn)行排序资昧，或者根據(jù)創(chuàng)建 set時提供的 Comparator進(jìn)行排序，具體取決于使用的構(gòu)造方法荆忍。

構(gòu)造方法和方法比較類似就不說了

遍歷（和list相似）

對 set 的遍歷

1.迭代遍歷：

Set set = new HashSet();?

Iterator it = set.iterator();?

while (it.hasNext()) {?

? String str =it.next();?

?System.out.println(str);?

}?

2.for(foreach)循環(huán)遍歷：

for (String str : set) {?

?????System.out.println(str);?

}?

Map（鍵值對格带、鍵唯一、值不唯一）

Map集合中存儲的是鍵值對刹枉，鍵不能重復(fù)叽唱，值可以重復(fù)。根據(jù)鍵得到值微宝，對map集合遍歷時先得到鍵的set集合棺亭，對set集合進(jìn)行遍歷，得到相應(yīng)的值蟋软。

HashMap

數(shù)組方式存儲key/value镶摘，線程非安全，允許null作為key和value岳守，key不可以重復(fù)凄敢，value允許重復(fù)，不保證元素迭代順序是按照插入時的順序湿痢，key的hash值是先計算key的hashcode值贡未，然后再進(jìn)行計算，每次容量擴容會重新計算所以key的hash值蒙袍，會消耗資源，要求key必須重寫equals和hashcode方法

默認(rèn)初始容量16嫩挤，加載因子0.75害幅，擴容為舊容量乘2，查找元素快岂昭，如果key一樣則比較value以现，如果value不一樣，則按照鏈表結(jié)構(gòu)存儲value约啊，就是一個key后面有多個value邑遏；

方法

1、添加：

V put(K key, V value)?（可以相同的key值恰矩，但是添加的value值會覆蓋前面的记盒，返回值是前一個，如果沒有就返回null）

putAll(Map<? extends K,?

extends V> m)?從指定映射中將所有映射關(guān)系復(fù)制到此映射中（可選操作）外傅。

2纪吮、刪除

remove()?刪除關(guān)聯(lián)對象俩檬，指定key對象

clear()?清空集合對象

3、獲取

value get(key)?可以用于判斷鍵是否存在的情況碾盟。當(dāng)指定的鍵不存在的時候棚辽，返回的是null。

４冰肴、判斷：

boolean isEmpty()?長度為0返回true否則false

boolean containsKey(Object

key)?判斷集合中是否包含指定的key

boolean containsValue(Object

value)?判斷集合中是否包含指定的value

4屈藐、長度：

Int size（）

map的主要的方法就這幾個

Hashtable

Hashtable與HashMap類似，是HashMap的線程安全版熙尉，它支持線程的同步联逻，即任一時刻只有一個線程能寫Hashtable，因此也導(dǎo)致了Hashtale在寫入時會比較慢骡尽，它繼承自Dictionary類遣妥，不同的是它不允許記錄的鍵或者值為null，同時效率較低攀细。

LinkedHashMap

LinkedHashMap保存了記錄的插入順序箫踩，在用Iteraor遍歷LinkedHashMap時，先得到的記錄肯定是先插入的谭贪，在遍歷的時候會比HashMap慢境钟，有HashMap的全部特性。

TreeMap

基于紅黑二叉樹的NavigableMap的實現(xiàn)俭识，線程非安全慨削，不允許null，key不可以重復(fù)套媚，value允許重復(fù)缚态，存入TreeMap的元素應(yīng)當(dāng)實現(xiàn)Comparable接口或者實現(xiàn)Comparator接口，會按照排序后的順序迭代元素堤瘤，兩個相比較的key不得拋出classCastException玫芦。主要用于存入元素的時候?qū)υ剡M(jìn)行自動排序，迭代輸出的時候就按排序順序輸出

遍歷

第一種：KeySet()

將Map中所有的鍵存入到set集合中本辐。因為set具備迭代器桥帆。所有可以迭代方式取出所有的鍵，再根據(jù)get方法慎皱。獲取每一個鍵對應(yīng)的值老虫。 keySet():迭代后只能通過get()取key 。取到的結(jié)果會亂序茫多，是因為取得數(shù)據(jù)行主鍵的時候祈匙，使用了HashMap.keySet()方法，而這個方法返回的Set結(jié)果地梨，里面的數(shù)據(jù)是亂序排放的菊卷。

??? Map map = newHashMap();

???map.put("key1","lisi1");

???map.put("key2","lisi2");

???map.put("key3","lisi3");

???map.put("key4","lisi4");?

??? //先獲取map集合的所有鍵的set集合缔恳，keyset（）

??? Iterator it = map.keySet().iterator();

??? //獲取迭代器

???while(it.hasNext()){

??????? Object key =it.next();

???????System.out.println(map.get(key));

??? }

第二種： values()?獲取所有的值.

Collection?values()

不能獲取到key對象

???????Collection vs = map.values();

???????Iterator it = vs.iterator();

??????? while(it.hasNext()) {

??????????? Stringvalue = it.next();

???????????System.out.println(" value=" + value);

??????? }

第三種：entrySet（）

Set> entrySet() //

返回此映射中包含的映射關(guān)系的 Set 視圖。（一個關(guān)系就是一個鍵-值對）洁闰，就是把(key-value)作為一個整體一對一對地存放到Set集合當(dāng)中的歉甚。Map.Entry表示映射關(guān)系。entrySet()：迭代后可以e.getKey()扑眉，e.getValue()兩種方法來取key和value纸泄。返回的是Entry接口。典型用法如下：

// 返回的Map.Entry對象的Set集合 Map.Entry包含了key和value對象

???????Set> es = map.entrySet();

???????Iterator> it = es.iterator();

??????? while(it.hasNext()) {

??????????? //返回的是封裝了key和value對象的Map.Entry對象

???????????Map.Entry en = it.next();

??????????? //獲取Map.Entry對象中封裝的key和value對象

??????????? Integer key= en.getKey();

??????????? Stringvalue = en.getValue();

???????????System.out.println("key=" + key + " value=" +value);

??????? }

推薦使用第三種方式腰素，即entrySet()方法聘裁，效率較高。對于keySet其實是遍歷了2次弓千，一次是轉(zhuǎn)為iterator衡便，一次就是從HashMap中取出key所對于的value。而entryset只是遍歷了第一次洋访，它把key和value都放到了entry中镣陕，所以快了。兩種遍歷的遍歷時間相差還是很明顯的姻政。

總結(jié)：

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,因為它移動一個指定位置的數(shù)據(jù)時其它元素不移動芦拿。

ArrayList 和Vector是采用數(shù)組方式存儲數(shù)據(jù)士飒，此數(shù)組元素數(shù)大于實際存儲的數(shù)據(jù)以便增加和插入元素查邢，都允許直接序號索引元素，但是插入數(shù)據(jù)要涉及到數(shù)組元素移動等內(nèi)存操作艘希，所以索引數(shù)據(jù)快侮腹，插入數(shù)據(jù)慢槽奕，Vector由于使用了synchronized方法（線程安全）所以性能上比ArrayList要差，LinkedList使用雙向鏈表實現(xiàn)存儲邓深，按序號索引數(shù)據(jù)需要進(jìn)行向前或向后遍歷，但是插入數(shù)據(jù)時只需要記錄本項的前后項即可笔刹，所以插入數(shù)度較快芥备。

arraylist和linkedlist

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

2.對于隨機訪問get和set萌壳，ArrayList覺得優(yōu)于LinkedList，因為LinkedList要移動指針日月。

3.對于新增和刪除操作add和remove袱瓮，LinedList比較占優(yōu)勢，因為ArrayList要移動數(shù)據(jù)山孔。 這一點要看實際情況的懂讯。若只對單條數(shù)據(jù)插入或刪除，ArrayList的速度反而優(yōu)于LinkedList台颠。但若是批量隨機的插入刪除數(shù)據(jù)褐望，LinkedList的速度大大優(yōu)于ArrayList. 因為ArrayList每插入一條數(shù)據(jù)，要移動插入點及之后的所有數(shù)據(jù)串前。

HashMap與TreeMap

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

2、在Map中插入坛吁、刪除和定位元素劳殖，HashMap是最好的選擇。但如果您要按自然順序或自定義順序遍歷鍵拨脉，那么TreeMap會更好哆姻。使用HashMap要求添加的鍵類明確定義了hashCode()和 equals()的實現(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窿吩。