集合框架
1.常用容器繼承關(guān)系圖
Iterator不是容器古徒，只是一個操作遍歷集合的方法
2.Collection和Map
在Java容器中一共定義了2種集合, 頂層接口分別是Collection和Map。但是這2個接口都不能直接被實現(xiàn)使用，分別代表兩種不同類型的容器钧唐。
Collection：是容器繼承關(guān)系中的頂層接口揖盘。是一組對象元素組。有些容器允許重復(fù)元素有的不允許贴硫，有些有序有些無序炮障。 JDK不直接提供對于這個接口的實現(xiàn)，但是提供繼承與該接口的子接口比如 List Set坤候。
接口定義：
public interface Collection<E> extends Iterable<E> {
...
}
泛型<E>即該Collection中元素對象的類型胁赢，繼承的Iterable是定義的一個遍歷操作接口，采用hasNext next的方式進(jìn)行遍歷白筹。
幾個重要的接口方法：
add(E e)確保此 collection 包含指定的元素（可選操作）智末。
clear()移除此 collection 中的所有元素（可選操作）。
contains(Object o)如果此 collection 包含指定的元素徒河，則返回 true系馆。
isEmpty()如果此 collection 不包含元素，則返回 true顽照。
iterator()返回在此 collection 的元素上進(jìn)行迭代的迭代器由蘑。
remove(Object o)從此 collection 中移除指定元素的單個實例，如果存在的話（可選操作）代兵。
retainAll(Collection<?> c)僅保留此 collection 中那些也包含在指定 collection 的元素（可選操作）尼酿。
size()返回此 collection 中的元素數(shù)
toArray()返回包含此 collection 中所有元素的數(shù)組
toArray(T[] a)返回包含此 collection 中所有元素的數(shù)組；返回數(shù)組的運行時類型與指定數(shù)組的運行時類型相同
Map：一個保存鍵值映射的對象植影。 映射Map中不能包含重復(fù)的key裳擎，每一個key最多對應(yīng)一個value。
Map集合提供3種遍歷訪問方法：
1.獲得所有key的集合然后通過key訪問value思币。
2.獲得value的集合鹿响。
3.獲得key-value鍵值對的集合（key-value鍵值對其實是一個對象羡微，里面分別有key和value）。
Map的訪問順序取決于Map的遍歷訪問方法的遍歷順序惶我。 有的Map妈倔，比如TreeMap可以保證訪問順序，但是有的比如HashMap指孤，無法保證訪問順序启涯。
接口定義如下：
public interface Map<K,V> {
...
interface Entry<K,V> {
K getKey();
V getValue();
...
}
}
泛型<K,V>分別代表key和value的類型。這時候注意到還定義了一個內(nèi)部接口Entry恃轩，其實每一個鍵值對都是一個Entry的實例關(guān)系對象结洼，所以Map實際其實就是Entry的一個Collection，然后Entry里面包含key叉跛，value松忍。再設(shè)定key不重復(fù)的規(guī)則，自然就演化成了Map筷厘。（個人理解）
幾個重要的接口方法：
clear()從此映射中移除所有映射關(guān)系
containsKey(Object key)如果此映射包含指定鍵的映射關(guān)系鸣峭，則返回 true。
containsValue(Object value)如果此映射將一個或多個鍵映射到指定值酥艳，則返回 true摊溶。
entrySet()返回此映射中包含的映射關(guān)系的 Set 視圖。
equals(Object o) 比較指定的對象與此映射是否相等充石。
get(Object key)返回指定鍵所映射的值莫换；如果此映射不包含該鍵的映射關(guān)系，則返回 null骤铃。
isEmpty()如果此映射未包含鍵-值映射關(guān)系拉岁，則返回 true。
keySet()返回此映射中包含的鍵的 Set 視圖惰爬。
put(K key, V value)將指定的值與此映射中的指定鍵關(guān)聯(lián)（可選操作）喊暖。
putAll(Map<? extends K,? extends V> m)從指定映射中將所有映射關(guān)系復(fù)制到此映射中（可選操作）。
remove(Object key)如果存在一個鍵的映射關(guān)系撕瞧，則將其從此映射中移除（可選操作）陵叽。
size()返回此映射中的鍵-值映射關(guān)系數(shù)。
values()返回此映射中包含的值的 Collection 視圖风范。
3個遍歷Map的方法：
1.Set<K> keySet()：
會返回所有key的Set集合咨跌，因為key不可以重復(fù)，所以返回的是Set格式硼婿，而不是List格式锌半。
獲取到所有key的Set集合后，由于Set是Collection類型的，所以可以通過Iterator去遍歷所有的key刊殉，然后再通過get方法獲取value
如下：
Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");
Set<String> keySet = map.keySet();//先獲取map集合的所有鍵的Set集合
Iterator<String> it = keySet.iterator();//有了Set集合殉摔，就可以獲取其迭代器。
while(it.hasNext()) {
String key = it.next();
String value = map.get(key);//有了鍵可以通過map集合的get方法獲取其對應(yīng)的值记焊。
System.out.println("key: "+key+"-->value: "+value);//獲得key和value值
}
2.Collection<V> values()：
直接獲取values的集合逸月，無法再獲取到key。所以如果只需要value的場景可以用這個方法遍膜。獲取到后使用Iterator去遍歷所有的value碗硬。
如下：
Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");
Collection<String> collection = map.values();//返回值是個值的Collection集合
System.out.println(collection);
3.Set< Map.Entry< K, V>> entrySet()：
是將整個Entry對象作為元素返回所有的數(shù)據(jù)。然后遍歷Entry瓢颅，分別再通過getKey和getValue獲取key和value恩尾。
如下：
Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");
//通過entrySet()方法將map集合中的映射關(guān)系取出（這個關(guān)系就是Map.Entry類型）
Set<Map.Entry<String, String>> entrySet = map.entrySet();
//將關(guān)系集合entrySet進(jìn)行迭代，存放到迭代器中
Iterator<Map.Entry<String, String>> it = entrySet.iterator();
while(it.hasNext()) {
Map.Entry<String, String> me = it.next();//獲取Map.Entry關(guān)系對象me
String key = me.getKey();//通過關(guān)系對象獲取key
String value = me.getValue();//通過關(guān)系對象獲取value
}
通過以上3種遍歷方式我們可以知道挽懦，如果你只想獲取key翰意，建議使用keySet。如果只想獲取value信柿，建議使用values冀偶。如果key value希望遍歷，建議使用entrySet渔嚷。
（雖然通過keySet可以獲得key再間接獲得value进鸠，但是效率沒entrySet高，不建議使用這種方法）
3.List形病、Set和Queue
List和Set堤如。他們2個是繼承Collection的子接口，就是說他們也都是負(fù)責(zé)存儲單個元素的容器窒朋。
最大的區(qū)別如下：
1.List是存儲的元素容器是有個有序的可以索引到元素的容器，并且里面的元素可以重復(fù)蝗岖。
2.Set里面和List最大的區(qū)別是Set里面的元素對象不可重復(fù)侥猩。
List:一個有序的Collection（或者叫做序列）。使用這個接口可以精確掌控元素的插入抵赢，還可以根據(jù)index獲取相應(yīng)位置的元素欺劳。
不像Set，list允許重復(fù)元素的插入铅鲤。有人希望自己實現(xiàn)一個list划提，禁止重復(fù)元素，并且在重復(fù)元素插入的時候拋出異常邢享，但是我們不建議這么做鹏往。
List提供了一種特殊的iterator遍歷器，叫做ListIterator骇塘。這種遍歷器允許遍歷時插入伊履，替換韩容，刪除，雙向訪問唐瀑。 并且還有一個重載方法允許從一個指定位置開始遍歷群凶。
List接口新增的接口，會發(fā)現(xiàn)add哄辣，get這些都多了index參數(shù)请梢，說明在原來Collection的基礎(chǔ)上，List是一個可以指定索引力穗，有序的容器毅弧。
在這注意以下添加的2個新Iteractor方法:
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
ListIterator的代碼:
public interface ListIterator<E> extends Iterator<E> {
// Query Operations
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int previousIndex();
void remove();
void set(E e);
void add(E e);
}
一個集合在遍歷過程中進(jìn)行插入刪除操作很容易造成錯誤，特別是無序隊列睛廊，是無法在遍歷過程中進(jìn)行這些操作的形真。
但是List是一個有序集合，所以在這實現(xiàn)了一個ListIteractor超全，可以在遍歷過程中進(jìn)行元素操作咆霜，并且可以雙向訪問。
List的實現(xiàn)類嘶朱，ArrayList和LinkedList.
1.ArrayList
ArrayList是一個實現(xiàn)了List接口的可變數(shù)組可以插入null它的size, isEmpty, get, set, iterator,add這些方法的時間復(fù)雜度是
O(1),如果add n個數(shù)據(jù)則時間復(fù)雜度是O(n).ArrayList不是synchronized的蛾坯。
然后我們來簡單看下ArrayList源碼實現(xiàn)。這里只寫部分源碼分析疏遏。
所有元素都是保存在一個Object數(shù)組中脉课，然后通過size控制長度。
transient Object[] elementData;
private int size;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
其實在每次add的時候會判斷數(shù)據(jù)長度财异，如果不夠的話會調(diào)用Arrays.copyOf倘零，復(fù)制一份更長的數(shù)組，并把前面的數(shù)據(jù)放進(jìn)去戳寸。
我們再看下remove的代碼是如何實現(xiàn)的呈驶。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
其實就是直接使用System.arraycopy把需要刪除index后面的都往前移一位然后再把最后一個去掉。
2.LinkedList
LinkedList是一個鏈表維護的序列容器疫鹊。和ArrayList都是序列容器袖瞻，一個使用數(shù)組存儲，一個使用鏈表存儲拆吆。
數(shù)組和鏈表2種數(shù)據(jù)結(jié)構(gòu)的對比：
1.查找方面聋迎。數(shù)組的效率更高，可以直接索引出查找枣耀，而鏈表必須從頭查找霉晕。
2.插入刪除方面。特別是在中間進(jìn)行插入刪除，這時候鏈表體現(xiàn)出了極大的便利性娄昆，只需要在插入或者刪除的地方斷掉鏈
然后插入或者移除元素佩微，然后再將前后鏈重新組裝，但是數(shù)組必須重新復(fù)制一份將所有數(shù)據(jù)后移或者前移萌焰。
3.在內(nèi)存申請方面哺眯，當(dāng)數(shù)組達(dá)到初始的申請長度后，需要重新申請一個更大的數(shù)組然后把數(shù)據(jù)遷移過去才行扒俯。而鏈表只需
要動態(tài)創(chuàng)建即可奶卓。
如上LinkedList和ArrayList的區(qū)別也就在此.
總結(jié):
List實現(xiàn) 使用場景 數(shù)據(jù)結(jié)構(gòu)
ArrayList 數(shù)組形式訪問List鏈?zhǔn)郊蠑?shù)據(jù)，元素可重復(fù)撼玄，訪問元素較快 數(shù)組
LinkedList 鏈表方式的List鏈?zhǔn)郊隙峁茫乜芍貜?fù)，元素的插入刪除較快 雙向鏈表
Vector: 底層是數(shù)組數(shù)據(jù)結(jié)構(gòu)掌猛。線程同步盏浙。被ArrayList替代了。因為效率低荔茬。
4.Set
Set的核心概念就是集合內(nèi)所有元素不重復(fù)废膘。在Set這個子接口中沒有在Collection特別實現(xiàn)什么額外的方法，應(yīng)該只是定義了一個Set概念慕蔚。下面我們來看Set的幾個常用的實現(xiàn)HashSet丐黄、LinkedHashSet、TreeSet
HashSet:
HashSet實現(xiàn)了Set接口孔飒，基于HashMap進(jìn)行存儲灌闺。遍歷時不保證順序，并且不保證下次遍歷的順序和之前一樣坏瞄。HashSet中允許null元素桂对。
進(jìn)入到HashSet源碼中我們發(fā)現(xiàn)，所有數(shù)據(jù)存儲在:
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
意思就是HashSet的集合其實就是HashMap的key的集合鸠匀，然后HashMap的val默認(rèn)都是PRESENT接校。HashMap的定義即是key不重復(fù)的集合。使用HashMap實現(xiàn)狮崩，這樣HashSet就不需要再實現(xiàn)一遍。
所以所有的add鹿寻，remove等操作其實都是HashMap的add睦柴、remove操作。遍歷操作其實就是HashMap的keySet的遍歷,舉例如下
...
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public void clear() {
map.clear();
}
...
LinkedHashSet:
LinkedHashSet的核心概念相對于HashSet來說就是一個可以保持順序的Set集合毡熏。HashSet是無序的坦敌，LinkedHashSet會根據(jù)add，remove這些操作的順序在遍歷時返回固定的集合順序。這個順序不是元素的大小順序狱窘，而是可以保證2次遍歷的順序是一樣的杜顺。
類似HashSet基于HashMap的源碼實現(xiàn)，LinkedHashSet的數(shù)據(jù)結(jié)構(gòu)是基于LinkedHashMap蘸炸。過多的就不說了躬络。
TreeSet:
TreeSet即是一組有次序的集合，如果沒有指定排序規(guī)則Comparator搭儒，則會按照自然排序穷当。（自然排序即e1.compareTo(e2) == 0作為比較）
注意：TreeSet內(nèi)的元素必須實現(xiàn)Comparable接口。
TreeSet源碼的算法即基于TreeMap淹禾，具體算法在說明TreeMap的時候進(jìn)行解釋馁菜。
總結(jié):
Set實現(xiàn) 使用場景 數(shù)據(jù)結(jié)構(gòu)
HashSet 無序的、無重復(fù)的數(shù)據(jù)集合 基于HashMap
LinkedSet 維護次序的HashSet 基于LinkedHashMap
TreeSet 保持元素大小次序的集合铃岔，元素需要實現(xiàn)Comparable接口 基于TreeMap
4.HashMap汪疮、LinkedHashMap、TreeMap和WeakHashMap
HashMap就是最基礎(chǔ)最常用的一種Map毁习，它無序智嚷，以散列表的方式進(jìn)行存儲。之前提到過蜓洪，HashSet就是基于HashMap纤勒，只使用了HashMap的key作為單個元素存儲。
HashMap的訪問方式就是繼承于Map的最基礎(chǔ)的3種方式隆檀，詳細(xì)見上摇天。在這里我具體分析一下HashMap的底層數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。
在看HashMap源碼前恐仑，先理解一下他的存儲方式-散列表（哈希表）泉坐。像之前提到過的用數(shù)組存儲，用鏈表存儲裳仆。哈希表是使用數(shù)組和鏈表的組合的方式進(jìn)行存儲腕让。(具體哈希表的概念自行搜索)如下圖就是HashMap采用的存儲方法。
Map實現(xiàn) 使用場景 數(shù)據(jù)結(jié)構(gòu)
HashMap 哈希表存儲鍵值對歧斟，key不重復(fù)纯丸，無序 哈希散列表
LinkedHashMap 是一個可以記錄插入順序和訪問順序的HashMap 存儲方式是哈希散列表，但是維護了頭尾指針用來記錄順序
TreeMap 具有元素排序功能 紅黑樹
WeakHashMap 弱鍵映射静袖，映射之外無引用的鍵觉鼻，可以被垃圾回收 哈希散列表
