Java集合類簡介
Java集合類主要由兩個接口派生而出： Collection 和 Map 箱锐。Java集合大致可以分為Set、List劳较、Queue和Map四種體系驹止。其繼承樹關(guān)系如圖：
上述類圖中浩聋，實線邊框的是實現(xiàn)類，比如ArrayList臊恋，LinkedList衣洁，HashMap等，折線邊框的是抽象類抖仅，比如AbstractCollection坊夫，AbstractList，AbstractMap等撤卢，而點線邊框的是接口环凿，比如Collection，Iterator放吩，List等智听。各體系集合的特點概述如下：
- Set體系集合：代表無序、不可重復(fù)的集合渡紫；
- List體系集合：代表有序到推、重復(fù)的集合；
- Map體系集合：代表具有映射關(guān)系的集合惕澎；
- Queue體系集合莉测，代表一種隊列集合實現(xiàn)。（Java 5 增加）
Java集合和數(shù)組的區(qū)別
1唧喉、數(shù)組長度在初始化時指定捣卤，意味著只能保存定長的數(shù)據(jù)。而集合可以保存數(shù)量不確定的數(shù)據(jù)欣喧。同時可以保存具有映射關(guān)系的數(shù)據(jù)（即關(guān)聯(lián)數(shù)組腌零，鍵值對 key-value）。
2唆阿、數(shù)組元素即可以是基本類型的值益涧，也可以是對象。集合里只能保存對象（實際上只是保存對象的引用變量）驯鳖，基本數(shù)據(jù)類型的變量要轉(zhuǎn)換成對應(yīng)的包裝類才能放入集合類中闲询。Java 5 增加泛型以后還可以記住容器中對象的數(shù)據(jù)類型。
集合的遍歷
通用方式
Iterator it = list.iterator();
while(it.hasNext()) {
Object obj = it.next();
}
Map遍歷方式
1浅辙、通過獲取所有的key按照key來遍歷
//Set<Integer> set = map.keySet(); //得到所有key的集合
for (Integer in : map.keySet()) {
String str = map.get(in);//得到每個key多對用value的值
}
2扭弧、通過Map.entrySet使用iterator遍歷key和value
Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
3、通過Map.entrySet遍歷key和value记舆，推薦鸽捻，尤其是容量大時
for (Map.Entry<Integer, String> entry : map.entrySet()) {
//Map.entry<Integer,String> 映射項（鍵-值對） 有幾個方法：用上面的名字entry
//entry.getKey() ;entry.getValue(); entry.setValue();
//map.entrySet() 返回此映射中包含的映射關(guān)系的 Set視圖。
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
4、通過Map.values()遍歷所有的value御蒲，但不能遍歷key
for (String v : map.values()) {
System.out.println("value= " + v);
}
List遍歷方式
第一種：
Iterator iterator = list.iterator();
for(iterator.hasNext();){
int i = (Integer) iterator.next();
System.out.println(i);
}
第二種：
Iterator iterator = list.iterator();
while(iterator.hasNext()){
int i = (Integer) iterator.next();
System.out.println(i);
}
第三種：
for (Object object : list) {
System.out.println(object);
}
第四種：
for(int i = 0 ;i<list.size();i++) {
int j= (Integer) list.get(i);
System.out.println(j);
}
數(shù)據(jù)元素是怎樣在內(nèi)存中存放的衣赶？
主要有2種存儲方式：
1、順序存儲厚满，Random Access（Direct Access）：
這種方式府瞄，相鄰的數(shù)據(jù)元素存放于相鄰的內(nèi)存地址中，整塊內(nèi)存地址是連續(xù)的碘箍∽窆荩可以根據(jù)元素的位置直接計算出內(nèi)存地址，直接進行讀取丰榴。讀取一個特定位置元素的平均時間復(fù)雜度為O(1)货邓。正常來說，只有基于數(shù)組實現(xiàn)的集合多艇，才有這種特性逻恐。Java中以ArrayList為代表像吻。
2峻黍、鏈式存儲，Sequential Access：
這種方式拨匆，每一個數(shù)據(jù)元素姆涩，在內(nèi)存中都不要求處于相鄰的位置，每個數(shù)據(jù)元素包含它下一個元素的內(nèi)存地址惭每。不可以根據(jù)元素的位置直接計算出內(nèi)存地址骨饿，只能按順序讀取元素。讀取一個特定位置元素的平均時間復(fù)雜度為O(n)台腥。主要以鏈表為代表宏赘。Java中以LinkedList為代表。
每個遍歷方法的實現(xiàn)原理是什么黎侈？
1察署、傳統(tǒng)的for循環(huán)遍歷，基于計數(shù)器的：
遍歷者自己在集合外部維護一個計數(shù)器峻汉，然后依次讀取每一個位置的元素贴汪，當讀取到最后一個元素后，停止休吠。主要就是需要按元素的位置來讀取元素扳埂。
2、迭代器遍歷瘤礁，Iterator：
每一個具體實現(xiàn)的數(shù)據(jù)集合阳懂，一般都需要提供相應(yīng)的Iterator。相比于傳統(tǒng)for循環(huán)，Iterator取締了顯式的遍歷計數(shù)器岩调。所以基于順序存儲集合的Iterator可以直接按位置訪問數(shù)據(jù)克饶。而基于鏈式存儲集合的Iterator，正常的實現(xiàn)誊辉，都是需要保存當前遍歷的位置矾湃。然后根據(jù)當前位置來向前或者向后移動指針。
3堕澄、foreach循環(huán)遍歷：
根據(jù)反編譯的字節(jié)碼可以發(fā)現(xiàn)邀跃，foreach內(nèi)部也是采用了Iterator的方式實現(xiàn)，只不過Java編譯器幫我們生成了這些代碼蛙紫。
各遍歷方式的適用于什么場合拍屑？
1、傳統(tǒng)的for循環(huán)遍歷坑傅，基于計數(shù)器的：
順序存儲：讀取特定元素平均時間復(fù)雜度是O(1)僵驰，遍歷則只需平均時間復(fù)雜度是O(n)。因此讀取性能比較高唁毒。適用于遍歷順序存儲集合蒜茴。
鏈式存儲：查找特定元素平均時間復(fù)雜度是O(n)，遍歷則只需平均時間復(fù)雜度是O(n^2)浆西。因此時間復(fù)雜度太大粉私，不適用于遍歷鏈式存儲的集合。
2近零、迭代器遍歷诺核，Iterator：
順序存儲：增加了額外的操作，額外的運作時間久信，沒有太大的意義窖杀。若想要代碼更加簡潔，可以使用裙士。
鏈式存儲：因為Iterator內(nèi)部維護了當前遍歷的位置入客，使查找特定元素（移動指針指向下一個）的平均時間復(fù)雜度降為O(n)，即總遍歷的平均時間復(fù)雜度降為O(n)潮售。因此所以推薦此種遍歷方式痊项。
3、foreach循環(huán)遍歷：
foreach能使代碼更加簡潔了酥诽，但是它有一些缺點鞍泉，就是遍歷過程中不能操作數(shù)據(jù)集合（刪除等），所以有些場合不使用肮帐。其本身就是基于Iterator實現(xiàn)的咖驮，由于類型轉(zhuǎn)換的問題边器，所以會比直接使用Iterator慢一點，但是還好托修，時間復(fù)雜度都是一樣的忘巧。
Java的最佳實踐是什么？
Java數(shù)據(jù)集合框架中睦刃，提供了一個RandomAccess接口砚嘴，該接口沒有方法，只是一個標記涩拙。通常被List接口的實現(xiàn)使用际长，用來標記該List的實現(xiàn)是否支持Random Access。
一個數(shù)據(jù)集合實現(xiàn)了該接口兴泥，就意味著它支持Random Access工育，按位置讀取元素的平均時間復(fù)雜度為O(1)。比如ArrayList搓彻。
而沒有實現(xiàn)該接口的如绸，就表示不支持Random Access。比如LinkedList旭贬。
所以看來JDK開發(fā)者也是注意到這個問題的怔接，那么推薦的做法就是，如果想要遍歷一個List骑篙，那么先判斷是否支持Random Access蜕提，也就是 list instanceof RandomAccess森书。
比如：
if (list instanceof RandomAccess) {
//順序存儲結(jié)構(gòu)靶端，使用傳統(tǒng)的for循環(huán)遍歷。
} else {
//非順序存儲結(jié)構(gòu)凛膏，使用Iterator或者foreach杨名。
}
