JAVA集合框架
一、Java集合框架概述
1、數(shù)組與集合的區(qū)別：
1） 數(shù)組長(zhǎng)度不可變化而且無(wú)法保存具有映射關(guān)系的數(shù)據(jù)；集合類用于保存數(shù)量不確定的數(shù)據(jù)，以及保存具有映射關(guān)系的數(shù)據(jù)。
2）數(shù)組元素既可以是基本類型的值，也可以是對(duì)象；集合只能保存對(duì)象。
2、Java集合類主要由兩個(gè)根接口Collection和Map派生出來(lái)的，Collection派生出了三個(gè)子接口：List、Set、Queue（Java5新增的隊(duì)列），因此Java集合大致也可分成List（有序、可重復(fù)集合、可直接根據(jù)元素的索引來(lái)訪問(wèn)）、Set（無(wú)序、不可重復(fù)集合、只能根據(jù)元素本身來(lái)訪問(wèn)）、Queue（隊(duì)列集合）、Map（存儲(chǔ)key-value對(duì)的集合，可根據(jù)元素的key來(lái)訪問(wèn)value）這四種。
二、Java集合常見(jiàn)接口及實(shí)現(xiàn)類
1、Collection接口常見(jiàn)方法
2、 List集合
實(shí)現(xiàn)List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。
它們都可以容納所有類型的對(duì)象，包括 null，允許重復(fù)，并且都保證元素的存儲(chǔ)順序。 （ 可重復(fù)，有順序）
1）ArrayList
ArrayList 對(duì)數(shù)組進(jìn)行了封裝，實(shí)現(xiàn)了長(zhǎng)度可變的數(shù)組（動(dòng)態(tài)數(shù)組），和數(shù)組采用相同存儲(chǔ)方式，在內(nèi)存中分配連續(xù)的空間，它的優(yōu)點(diǎn)在于遍歷元素和隨即訪問(wèn)元素的效率比較高。
ArrayList特點(diǎn)：線程不安全，查詢速度快 ； 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組結(jié)構(gòu) ； 擴(kuò)容增量：原容量的 1.5倍 ， 如 ArrayList的容量為10，一次擴(kuò)容后是容量為15 。
2）LinkedList
LinkedList是List接口的另一個(gè)實(shí)現(xiàn)，除了可以根據(jù)索引訪問(wèn)集合元素外，LinkedList還實(shí)現(xiàn)了Deque接口，可以當(dāng)作雙端隊(duì)列來(lái)使用，也就是說(shuō)，既可以當(dāng)作“棧”使用，又可以當(dāng)作隊(duì)列使用。
LinkedList 采用鏈表存儲(chǔ)方式，優(yōu)點(diǎn)在于插入、刪除元素時(shí)效率比較高，它提供了額外的 addFirst()、addLast()、removeFirst()和 removeLast()等方法，可以在LinkedList 的首部或尾部進(jìn)行插入或者刪除操作。
3)Vector
與ArrayList相似，但是Vector是同步的。所以說(shuō)Vector是線程安全的動(dòng)態(tài)數(shù)組。它的操作與ArrayList幾乎一樣。
3、 Set集合
實(shí)現(xiàn)Set集合的接口主要有：HashSet、TreeSet、LinkedHashSet；
Set集合與Collection的方法相同，由于Set集合不允許存儲(chǔ)相同的元素，所以如果把兩個(gè)相同元素添加到同一個(gè)Set集合，則添加操作失敗，新元素不會(huì)被加入，add()方法返回false。（無(wú)序、不重復(fù)）
1）HashSet
HashSet是按照hash算法來(lái)存儲(chǔ)元素的，因此具有很好的存取和查找性能。
HashSet存儲(chǔ)原理如下：
當(dāng)向HashSet集合存儲(chǔ)一個(gè)元素時(shí)，HashSet會(huì)調(diào)用該對(duì)象的hashCode()方法得到其hashCode值，然后根據(jù)hashCode值決定該對(duì)象的存儲(chǔ)位置。HashSet集合判斷兩個(gè)元素相等的標(biāo)準(zhǔn)是(1)兩個(gè)對(duì)象通過(guò)equals()方法比較返回true；(2)兩個(gè)對(duì)象的hashCode()方法返回值相等。因此，如果(1)和(2)有一個(gè)不滿足條件，則認(rèn)為這兩個(gè)對(duì)象不相等，可以添加成功。如果兩個(gè)對(duì)象的hashCode()方法返回值相等，但是兩個(gè)對(duì)象通過(guò)equals()方法比較返回false，HashSet會(huì)以鏈?zhǔn)浇Y(jié)構(gòu)將兩個(gè)對(duì)象保存在同一位置，這將導(dǎo)致性能下降，因此在編碼時(shí)應(yīng)避免出現(xiàn)這種情況。
HashSet查找原理如下：
基于HashSet以上的存儲(chǔ)原理，在查找元素時(shí)，HashSet先計(jì)算元素的HashCode值（也就是調(diào)用對(duì)象的hashCode方法的返回值），然后直接到hashCode值對(duì)應(yīng)的位置去取出元素即可，這就是HashSet速度很快的原因。
HashSet特點(diǎn)：
不能保證元素的順序；集合元素值可以是null；線程不安全，存取速度快； 底層實(shí)現(xiàn)是一個(gè) HashMap（保存數(shù)據(jù)），實(shí)現(xiàn)Set接口； 默認(rèn)初始容量為 16； 加載因子為 0.75：即當(dāng) 元素個(gè)數(shù) 超過(guò) 容量長(zhǎng)度的0.75倍 時(shí)，進(jìn)行擴(kuò)容； 擴(kuò)容增量：原容量的 1 倍； 如 HashSet的容量為16，一次擴(kuò)容后是容量為32。
2）LinkedHashSet
LinkedHashSet是HashSet的一個(gè)子類，具有HashSet的特性，也是根據(jù)元素的hashCode值來(lái)決定元素的存儲(chǔ)位置。但它使用鏈表維護(hù)元素的次序，元素的順序與添加順序一致。由于LinkedHashSet需要維護(hù)元素的插入順序，因此性能略低于HashSet，但在迭代訪問(wèn)Set里的全部元素時(shí)由很好的性能。
3)TreeSet
TreeSet可以保證元素處于排序狀態(tài)，它采用紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)集合元素。TreeSet支持兩種排序方法：自然排序和定制排序，默認(rèn)采用自然排序。
♦ 自然排序
TreeSet會(huì)調(diào)用集合元素的compareTo(Object obj)方法來(lái)比較元素的大小關(guān)系，然后將元素按照升序排列，這就是自然排序。如果試圖將一個(gè)對(duì)象添加到TreeSet集合中，則該對(duì)象必須實(shí)現(xiàn)Comparable接口，否則會(huì)拋出異常。當(dāng)一個(gè)對(duì)象調(diào)用方法與另一個(gè)對(duì)象比較時(shí)，例如obj1.compareTo(obj2)，如果該方法返回0，則兩個(gè)對(duì)象相等；如果返回一個(gè)正數(shù)，則obj1大于obj2；如果返回一個(gè)負(fù)數(shù)，則obj1小于obj2。
♦ 定制排序
想要實(shí)現(xiàn)定制排序，需要在創(chuàng)建TreeSet集合對(duì)象時(shí)，提供一個(gè)Comparator對(duì)象與該TreeSet集合關(guān)聯(lián)，由Comparator對(duì)象負(fù)責(zé)集合元素的排序邏輯。
綜上：自然排序?qū)崿F(xiàn)的是Comparable接口，定制排序?qū)崿F(xiàn)的是Comparator接口。
4、Map集合
Map接口采用鍵值對(duì)Map<K,V>的存儲(chǔ)方式，保存具有映射關(guān)系的數(shù)據(jù)，因此，Map集合里保存兩組值，一組值用于保存Map里的key，另外一組值用于保存Map里的value，key和value可以是任意引用類型的數(shù)據(jù)。key值不允許重復(fù)，可以為null。如果添加key-value對(duì)時(shí)Map中已經(jīng)有重復(fù)的key，則新添加的value會(huì)覆蓋該key原來(lái)對(duì)應(yīng)的value。
常用實(shí)現(xiàn)類主要有HashMap、LinkedHashMap、TreeMap。
1）HashMap
對(duì)于 HashMap而言，key是唯一的，不可以重復(fù)的 。 所以，以相同的 key 把不同的value插入到 Map中會(huì)導(dǎo)致舊元素被覆蓋，只留下最后插入的元素 。 不過(guò)，同一個(gè)對(duì)象可以作為值插入到 map中，只要對(duì)應(yīng)的key不一樣 。
HashMap由 數(shù)組 +鏈表 組成的 ，數(shù)組是 HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的 。
HashMap工作原理如下：
HashMap基于hashing原理，通過(guò)put()和get()方法存儲(chǔ)和獲取對(duì)象。當(dāng)我們將鍵值對(duì)傳遞給put()方法時(shí)，它調(diào)用建對(duì)象的hashCode()方法來(lái)計(jì)算hashCode值，然后找到bucket位置來(lái)儲(chǔ)存值對(duì)象。當(dāng)獲取對(duì)象時(shí)，通過(guò)建對(duì)象的equals()方法找到正確的鍵值對(duì)，然后返回對(duì)象。HashMap使用鏈表來(lái)解決碰撞問(wèn)題，當(dāng)發(fā)生碰撞了，對(duì)象將會(huì)存儲(chǔ)在鏈表的下一個(gè)節(jié)點(diǎn)中。
HashMap特點(diǎn)：
- Map提供了一種映射關(guān)系，元素是以鍵值對(duì)（key-value）的形式存儲(chǔ)的，能根據(jù)key快速查找value；
- Map 中的鍵值對(duì)以 Entry 類型的對(duì)象實(shí)例形式存在；
- key 值不能重復(fù)， value 值可以重復(fù)；
- key 對(duì) value 是多（一）對(duì)一的關(guān)系；
- Map 接口提供了返回 key 值集合、 value 值集合、 Entry 值集合，的方法；
- Map 支持泛型，形式如： Map<K,V>；
- 默認(rèn)初始容量為 16 ；
- 加載因子為 0.75：即當(dāng) 元素個(gè)數(shù) 超過(guò) 容量長(zhǎng)度的0.75倍 時(shí)，進(jìn)行擴(kuò)容 ；
- 擴(kuò)容增量：原容量的 1 倍。
2）LinkedHashMap
LinkedHashMap使用雙向鏈表來(lái)維護(hù)key-value對(duì)的次序（其實(shí)只需要考慮key的次序即可），該鏈表負(fù)責(zé)維護(hù)Map的迭代順序，與插入順序一致，因此性能比HashMap低，但在迭代訪問(wèn)Map里的全部元素時(shí)有較好的性能。
大多數(shù)情況下，只要不涉及線程安全問(wèn)題， Map基本都可以使用HashMap，不過(guò)HashMap有一個(gè)問(wèn)題，是 迭代 HashMap的順序并不是HashMap放置的順序 ， 也就是無(wú)序。 HashMap的這一缺點(diǎn)往往會(huì)帶來(lái)困擾，因?yàn)橛行﹫?chǎng)景，我們期待一個(gè)有序的Map。這個(gè)時(shí)候，LinkedHashMap就閃亮登場(chǎng)了，它雖然增加了時(shí)間和空間上的開(kāi)銷，但是 通過(guò)維護(hù)一個(gè)運(yùn)行于所有條目的雙向鏈表， LinkedHashMap保證了元素迭代的順序 。 該迭代順序可以是插入順序或者是訪問(wèn)順序。
LinkedHashMap可以認(rèn)為是 HashMap+LinkedList ， 即它既使用 HashMap操作數(shù)據(jù)結(jié)構(gòu)，又使用LinkedList維護(hù)插入元素的先后順序。
LinkedHashMap的基本實(shí)現(xiàn)思想就是---- 多態(tài) 。
3)TreeMap
TreeMap是SortedMap的實(shí)現(xiàn)類，是一個(gè)紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)，每個(gè)key-value對(duì)作為紅黑樹(shù)的一個(gè)節(jié)點(diǎn)。TreeMap存儲(chǔ)key-value對(duì)時(shí)，需要根據(jù)key對(duì)節(jié)點(diǎn)進(jìn)行排序。TreeMap也有兩種排序方式：
♦ 自然排序：TreeMap的所有key必須實(shí)現(xiàn)Comparable接口，而且所有的key應(yīng)該是同一個(gè)類的對(duì)象，否則會(huì)拋出ClassCastException。
♦ 定制排序：創(chuàng)建TreeMap時(shí)，傳入一個(gè)Comparator對(duì)象，該對(duì)象負(fù)責(zé)對(duì)TreeMap中的所有key進(jìn)行排序。
TreeMap特點(diǎn):
· TreeMap是非線程安全的；
·TreeMap是用鍵來(lái)進(jìn)行升序順序來(lái)排序的。通過(guò)Comparable 或 Comparator來(lái)排序；
· 和 HashMap一樣，如果插入重復(fù)的元素，后面的元素會(huì)覆蓋前面的 ；
· 鍵不可以為 null（如果比較器對(duì)null做了處理，就可以為null）,但是值可以為null。
5、遍歷
第一種： for循環(huán)遍歷
1 for (int i = 0; i < heros.size(); i++) {2 Hero h = heros.get(i);3 System.out.println(h);4 }
第二種：迭代器遍歷
1 System.out.println("--------使用while的iterator-------"); 2 Iterator<Hero> it= heros.iterator(); 3 //從最開(kāi)始的位置判斷"下一個(gè)"位置是否有數(shù)據(jù) 4 //如果有就通過(guò)next取出來(lái)，并且把指針向下移動(dòng) 5 //直到"下一個(gè)"位置沒(méi)有數(shù)據(jù) 6 while(it.hasNext()){ 7 Hero h = it.next(); 8 System.out.println(h); 9 }10 //迭代器的for寫法11 System.out.println("--------使用for的iterator-------");12 for (Iterator<Hero> iterator = heros.iterator(); iterator.hasNext();) {13 Hero hero = (Hero) iterator.next();14 System.out.println(hero);15 }
第三種：增強(qiáng) for循環(huán)
1 System.out.println("--------增強(qiáng)型for循環(huán)-------");2 for (Hero h : heros) {3 System.out.println(h);4 }
