集合

集合與數(shù)組

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

集合（只能存儲(chǔ)對(duì)象，對(duì)象類型可以不一樣）的長度可變，可在多數(shù)情況下使用浴骂。
注：數(shù)組我在前面的博客講了大家可以看下

集合中接口和類的關(guān)系

Collection接口是集合類的根接口，Java中沒有提供這個(gè)接口的直接的實(shí)現(xiàn)類。但是卻讓其被繼承產(chǎn)生了兩個(gè)接口终抽，就是Set和List。Set中不能包含重復(fù)的元素桶至。List是一個(gè)有序的集合昼伴，可以包含重復(fù)的元素，提供了按索引訪問的方式镣屹。

Map是Java.util包中的另一個(gè)接口圃郊，它和Collection接口沒有關(guān)系，是相互獨(dú)立的女蜈，但是都屬于集合類的一部分持舆。Map包含了key-value對(duì)色瘩。Map不能包含重復(fù)的key，但是可以包含相同的value逸寓。

Iterator所有的集合類居兆，都實(shí)現(xiàn)了Iterator接口，這是一個(gè)用于遍歷集合中元素的接口席覆，主要包含以下三種方法：
1.hasNext()是否還有下一個(gè)元素史辙。
2.next()返回下一個(gè)元素。
3.remove()刪除當(dāng)前元素佩伤。

層次圖

圖一這個(gè)比較簡單

這里寫圖片描述

圖二完整

這里寫圖片描述

圖三詳細(xì)

image

此圖來源于：http://blog.csdn.net/u010887744/article/details/50575735

list,set,map對(duì)比

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

List里存放的對(duì)象是有序的孤荣，同時(shí)也是可以重復(fù)的，List關(guān)注的是索引盐股，擁有一系列和索引相關(guān)的方法钱豁，查詢速度快。因?yàn)橥鵯ist集合里插入或刪除數(shù)據(jù)時(shí)疯汁，會(huì)伴隨著后面數(shù)據(jù)的移動(dòng)牲尺，所有插入刪除數(shù)據(jù)速度慢。

ArrayList

ArrayList是基于數(shù)組的幌蚊，在初始化ArrayList時(shí)谤碳，會(huì)構(gòu)建空數(shù)組（Object[] elementData={}）。ArrayList是一個(gè)無序的溢豆，它是按照添加的先后順序排列蜒简，當(dāng)然，他也提供了sort方法漩仙，如果需要對(duì)ArrayList進(jìn)行排序搓茬，只需要調(diào)用這個(gè)方法，提供Comparator比較器即可

add操作：

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

2) 當(dāng)發(fā)覺同時(shí)添加一個(gè)或者是多個(gè)元素，數(shù)組長度不夠時(shí)漱挎，就擴(kuò)容系枪，這里有兩種情況：

只添加一個(gè)元素，例如：原來數(shù)組的capacity為10磕谅，size已經(jīng)為10私爷，不能再添加了雾棺。需要擴(kuò)容，新的capacity=old capacity+old capacity>>1=10+10/2=15.即新的容量為15衬浑。

當(dāng)同時(shí)添加多個(gè)元素時(shí)捌浩，原來數(shù)組的capacity為10，size為10工秩，當(dāng)同時(shí)添加6個(gè)元素時(shí)尸饺。它需要的min capacity為16，而按照capacity=old capacity+old capacity>>1=10+10/2=15助币。new capacity小于min capacity浪听，則取min capacity。

對(duì)于添加眉菱，如果不指定下標(biāo)迹栓，就直接添加到數(shù)組后面，不涉及元素的移動(dòng)俭缓，如果要添加到某個(gè)特定的位置克伊，那需要將這個(gè)位置開始的元素往后挪一個(gè)位置，然后再對(duì)這個(gè)位置設(shè)置华坦。

Remove操作：

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

1）remove(int index)：首先需要檢查Index是否在合理的范圍內(nèi)惜姐。其次再調(diào)用System.arraycopy將index之后的元素向前移動(dòng)洗搂。

2）remove(Object o)：首先遍歷數(shù)組，獲取第一個(gè)相同的元素载弄，獲取該元素的下標(biāo)。其次再調(diào)用System.arraycopy將index之后的元素向前移動(dòng)撵颊。

Get操作：

這個(gè)比較簡單宇攻，直接對(duì)數(shù)組進(jìn)行操作即可。

LinkedList

LinkedList是基于鏈表的倡勇，它是一個(gè)雙向鏈表逞刷，每個(gè)節(jié)點(diǎn)維護(hù)了一個(gè)prev和next指針。同時(shí)對(duì)于這個(gè)鏈表妻熊，維護(hù)了first和last指針夸浅，first指向第一個(gè)元素，last指向最后一個(gè)元素扔役。LinkedList是一個(gè)無序的鏈表帆喇，按照插入的先后順序排序，不提供sort方法對(duì)內(nèi)部元素排序亿胸。

Add元素：

LinkedList提供了幾個(gè)添加元素的方法：addFirst坯钦、addLast预皇、addAll、add等婉刀，時(shí)間復(fù)雜度為O(1)吟温。

Remove元素：

LinkedList提供了幾個(gè)移除元素的方法：removeFirst、removeLast突颊、removeFirstOccurrence鲁豪、remove等，時(shí)間復(fù)雜度為O(1)律秃。

Get元素：

根據(jù)給定的下標(biāo)index爬橡，判斷它first節(jié)點(diǎn)、last直接距離友绝，如果index<size（數(shù)組元素個(gè)數(shù))/2,就從first開始堤尾。如果大于，就從last開始迁客。這個(gè)和我們平常思維不太一樣郭宝，也許按照我們的習(xí)慣，從first開始掷漱。這也算是一點(diǎn)小心的優(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（int　i：arr）{...}

iterator的形式：
Iterator it = arr.iterator();
while(it.hasNext()){ object o =it.next(); ...}

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

Set里存放的對(duì)象是無序奥裸，不能重復(fù)的险掀，集合中的對(duì)象不按特定的方式排序，只是簡單地把對(duì)象加入集合中湾宙。

HashSet

HashSet是基于HashMap來實(shí)現(xiàn)的樟氢，操作很簡單，更像是對(duì)HashMap做了一次“封裝”侠鳄，而且只使用了HashMap的key來實(shí)現(xiàn)各種特性埠啃，而HashMap的value始終都是PRESENT。

HashSet不允許重復(fù)（HashMap的key不允許重復(fù)伟恶，如果出現(xiàn)重復(fù)就覆蓋）碴开，允許null值，非線程安全博秫。

構(gòu)造方法

**HashSet() **
　　構(gòu)造一個(gè)新的空 set叹螟，其底層 HashMap 實(shí)例的默認(rèn)初始容量是 16鹃骂，加載因子是 0.75。
**HashSet(Collection<? extends E> c) **
　　構(gòu)造一個(gè)包含指定 collection 中的元素的新 set罢绽。
**HashSet(int initialCapacity) **
　　構(gòu)造一個(gè)新的空 set畏线，其底層 HashMap 實(shí)例具有指定的初始容量和默認(rèn)的加載因子（0.75）。
HashSet(int initialCapacity, float loadFactor)
　　構(gòu)造一個(gè)新的空 set良价，其底層 HashMap 實(shí)例具有指定的初始容量和指定的加載因子寝殴。

方法

boolean add(E e) **
　　如果此 set 中尚未包含指定元素，則添加指定元素明垢。
void clear()
　　從此 set 中移除所有元素蚣常。
** Object clone()
　　返回此 HashSet 實(shí)例的淺表副本：并沒有復(fù)制這些元素本身。
boolean contains(Object o)
　　如果此 set 包含指定元素痊银，則返回 true抵蚊。
boolean isEmpty()
　　如果此 set 不包含任何元素，則返回 true溯革。
** Iterator iterator()
　　返回對(duì)此 set 中元素進(jìn)行迭代的迭代器贞绳。
boolean remove(Object o)
　　如果指定元素存在于此 set 中，則將其移除致稀。
int size()**
　　返回此 set 中的元素的數(shù)量（set 的容量）冈闭。

TreeSet

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

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

遍歷（和list相似）

對(duì) set 的遍歷

1.迭代遍歷：

Set<String> set = new HashSet<String>();  
Iterator<String> 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（鍵值對(duì)矛绘、鍵唯一耍休、值不唯一）

Map集合中存儲(chǔ)的是鍵值對(duì)，鍵不能重復(fù)货矮，值可以重復(fù)羊精。根據(jù)鍵得到值，對(duì)map集合遍歷時(shí)先得到鍵的set集合次屠，對(duì)set集合進(jìn)行遍歷，得到相應(yīng)的值雳刺。

HashMap

數(shù)組方式存儲(chǔ)key/value劫灶，線程非安全，允許null作為key和value掖桦，key不可以重復(fù)本昏，value允許重復(fù)，不保證元素迭代順序是按照插入時(shí)的順序枪汪，key的hash值是先計(jì)算key的hashcode值涌穆，然后再進(jìn)行計(jì)算怔昨，每次容量擴(kuò)容會(huì)重新計(jì)算所以key的hash值，會(huì)消耗資源宿稀，要求key必須重寫equals和hashcode方法

默認(rèn)初始容量16趁舀，加載因子0.75，擴(kuò)容為舊容量乘2祝沸，查找元素快矮烹，如果key一樣則比較value，如果value不一樣罩锐，則按照鏈表結(jié)構(gòu)存儲(chǔ)value奉狈，就是一個(gè)key后面有多個(gè)value；

方法

1涩惑、添加：

V put(K key, V value) （可以相同的key值仁期，但是添加的value值會(huì)覆蓋前面的，返回值是前一個(gè)竭恬，如果沒有就返回null）

putAll(Map<? extends K,? extends V> m) 從指定映射中將所有映射關(guān)系復(fù)制到此映射中（可選操作）跛蛋。

2、刪除

remove() 刪除關(guān)聯(lián)對(duì)象萍聊，指定key對(duì)象

clear() 清空集合對(duì)象

3问芬、獲取

value get(key) 可以用于判斷鍵是否存在的情況。當(dāng)指定的鍵不存在的時(shí)候寿桨，返回的是null此衅。

４、判斷：

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

boolean containsKey(Object key) 判斷集合中是否包含指定的key

boolean containsValue(Object value) 判斷集合中是否包含指定的value

4亭螟、長度：

Int size（）

map的主要的方法就這幾個(gè)

Hashtable

Hashtable與HashMap類似挡鞍，是HashMap的線程安全版，它支持線程的同步预烙，即任一時(shí)刻只有一個(gè)線程能寫Hashtable墨微，因此也導(dǎo)致了Hashtale在寫入時(shí)會(huì)比較慢，它繼承自Dictionary類扁掸，不同的是它不允許記錄的鍵或者值為null翘县，同時(shí)效率較低。

LinkedHashMap

LinkedHashMap保存了記錄的插入順序谴分，在用Iteraor遍歷LinkedHashMap時(shí)锈麸，先得到的記錄肯定是先插入的，在遍歷的時(shí)候會(huì)比HashMap慢牺蹄，有HashMap的全部特性忘伞。

TreeMap

基于紅黑二叉樹的NavigableMap的實(shí)現(xiàn)，線程非安全，不允許null氓奈，key不可以重復(fù)翘魄，value允許重復(fù)，存入TreeMap的元素應(yīng)當(dāng)實(shí)現(xiàn)Comparable接口或者實(shí)現(xiàn)Comparator接口舀奶，會(huì)按照排序后的順序迭代元素暑竟，兩個(gè)相比較的key不得拋出classCastException。主要用于存入元素的時(shí)候?qū)υ剡M(jìn)行自動(dòng)排序伪节，迭代輸出的時(shí)候就按排序順序輸出

遍歷

第一種：KeySet()
　　將Map中所有的鍵存入到set集合中光羞。因?yàn)閟et具備迭代器。所有可以迭代方式取出所有的鍵怀大，再根據(jù)get方法纱兑。獲取每一個(gè)鍵對(duì)應(yīng)的值。 keySet():迭代后只能通過get()取key 化借。
　　取到的結(jié)果會(huì)亂序潜慎，是因?yàn)槿〉脭?shù)據(jù)行主鍵的時(shí)候，使用了HashMap.keySet()方法蓖康，而這個(gè)方法返回的Set結(jié)果铐炫，里面的數(shù)據(jù)是亂序排放的。

    Map map = new HashMap();
    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對(duì)象

        Collection<String> vs = map.values();
        Iterator<String> it = vs.iterator();
        while (it.hasNext()) {
            String value = it.next();
            System.out.println(" value=" + value);
        }

第三種：entrySet（）
Set<Map.Entry<K,V>> entrySet() //返回此映射中包含的映射關(guān)系的 Set 視圖倒信。（一個(gè)關(guān)系就是一個(gè)鍵-值對(duì)），就是把(key-value)作為一個(gè)整體一對(duì)一對(duì)地存放到Set集合當(dāng)中的泳梆。Map.Entry表示映射關(guān)系鳖悠。entrySet()：迭代后可以e.getKey()，e.getValue()兩種方法來取key和value优妙。返回的是Entry接口乘综。
典型用法如下：

// 返回的Map.Entry對(duì)象的Set集合 Map.Entry包含了key和value對(duì)象
        Set<Map.Entry<Integer, String>> es = map.entrySet();

        Iterator<Map.Entry<Integer, String>> it = es.iterator();

        while (it.hasNext()) {

            // 返回的是封裝了key和value對(duì)象的Map.Entry對(duì)象
            Map.Entry<Integer, String> en = it.next();

            // 獲取Map.Entry對(duì)象中封裝的key和value對(duì)象
            Integer key = en.getKey();
            String value = en.getValue();

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

推薦使用第三種方式，即entrySet()方法套硼，效率較高卡辰。
　　對(duì)于keySet其實(shí)是遍歷了2次，一次是轉(zhuǎn)為iterator邪意，一次就是從HashMap中取出key所對(duì)于的value九妈。而entryset只是遍歷了第一次，它把key和value都放到了entry中雾鬼，所以快了萌朱。兩種遍歷的遍歷時(shí)間相差還是很明顯的。

總結(jié)：

Vector和ArrayList

1呆贿，vector是線程同步的嚷兔，所以它也是線程安全的，而arraylist是線程異步的做入，是不安全的冒晰。如果不考慮到線程的安全因素，一般用arraylist效率比較高竟块。

2壶运，如果集合中的元素的數(shù)目大于目前集合數(shù)組的長度時(shí)，vector增長率為目前數(shù)組長度的100%浪秘，而arraylist增長率為目前數(shù)組長度的50%蒋情。如果在集合中使用數(shù)據(jù)量比較大的數(shù)據(jù)，用vector有一定的優(yōu)勢(shì)耸携。

3棵癣，如果查找一個(gè)指定位置的數(shù)據(jù)，vector和arraylist使用的時(shí)間是相同的夺衍，如果頻繁的訪問數(shù)據(jù)狈谊，這個(gè)時(shí)候使用vector和arraylist都可以。而如果移動(dòng)一個(gè)指定位置會(huì)導(dǎo)致后面的元素都發(fā)生移動(dòng)沟沙，這個(gè)時(shí)候就應(yīng)該考慮到使用linklist,因?yàn)樗苿?dòng)一個(gè)指定位置的數(shù)據(jù)時(shí)其它元素不移動(dòng)河劝。

ArrayList 和Vector是采用數(shù)組方式存儲(chǔ)數(shù)據(jù)，此數(shù)組元素?cái)?shù)大于實(shí)際存儲(chǔ)的數(shù)據(jù)以便增加和插入元素矛紫，都允許直接序號(hào)索引元素赎瞎，但是插入數(shù)據(jù)要涉及到數(shù)組元素移動(dòng)等內(nèi)存操作，所以索引數(shù)據(jù)快颊咬，插入數(shù)據(jù)慢务甥，Vector由于使用了synchronized方法（線程安全）所以性能上比ArrayList要差，LinkedList使用雙向鏈表實(shí)現(xiàn)存儲(chǔ)贪染，按序號(hào)索引數(shù)據(jù)需要進(jìn)行向前或向后遍歷缓呛，但是插入數(shù)據(jù)時(shí)只需要記錄本項(xiàng)的前后項(xiàng)即可，所以插入數(shù)度較快杭隙。

arraylist和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)長inkedList要移動(dòng)指針。

3.對(duì)于新增和刪除操作add和remove铣耘，LinedList比較占優(yōu)勢(shì)洽沟，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)。 這一點(diǎn)要看實(shí)際情況的蜗细。若只對(duì)單條數(shù)據(jù)插入或刪除裆操，ArrayList的速度反而優(yōu)于LinkedList怒详。但若是批量隨機(jī)的插入刪除數(shù)據(jù)，LinkedList的速度大大優(yōu)于ArrayList. 因?yàn)锳rrayList每插入一條數(shù)據(jù)踪区，要移動(dòng)插入點(diǎn)及之后的所有數(shù)據(jù)昆烁。

HashMap與TreeMap

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

2传泊、在Map 中插入鼠渺、刪除和定位元素，HashMap是最好的選擇眷细。但如果您要按自然順序或自定義順序遍歷鍵拦盹，那么TreeMap會(huì)更好。使用HashMap要求添加的鍵類明確定義了hashCode()和 equals()的實(shí)現(xiàn)溪椎。

兩個(gè)map中的元素一樣掌敬，但順序不一樣，導(dǎo)致hashCode()不一樣池磁。

同樣做測試：
　　　　在HashMap中奔害，同樣的值的map,順序不同，equals時(shí)地熄，false;
　　　　而在treeMap中华临，同樣的值的map,順序不同,equals時(shí)，true端考，說明雅潭，treeMap在equals()時(shí)是整理了順序了的。

HashTable與HashMap

1却特、同步性:Hashtable是線程安全的扶供，也就是說是同步的，而HashMap是線程序不安全的裂明，不是同步的椿浓。

2、HashMap允許存在一個(gè)為null的key闽晦，多個(gè)為null的value 扳碍。

3、hashtable的key和value都不允許為null仙蛉。