一. 容器簡介
1. 容器的分類
1.1. Collection：一組各自獨立的元素，即其內的每個位置僅持有一個元素。
1) List：以元素安插的次序來放置元素，不會重新排列。
2) Set：不接愛重復元素，它會使用自己內部的一個排列機制
1.2. Map：一群成對的key-value對象，即所持有的是key-value pairs。
Map中不能有重復的key，它擁有自己的內部排列機制。
2. 容器中的元素類型都為Object。從容器取得元素時，必須把它轉換成原來的類型。
二. 容器的詳細介紹
1． Collection
Collection不提供get()方法。如果要遍歷Collectin中的元素，就必須用Iterator。
1.1. List
1.1.1 List（interface）：List為Collectin加入了一些函數(shù)，使它可以在List內進行安插和移除動作。List會產生ListIterator，通過它可以從兩個方向來對List進行走訪，也可以在List之內進行元素的安插和移除。
1.1.2 ArrayList：可以快速隨機訪問；但當元素的安插或移除發(fā)生在List中央位置時，效率很差。不宜用ArrayList來進行安插和移除操作。
1.1.3 LinkedList：與ArrayList相反，適合用來進行安插和移除，但隨機訪問的速度較慢。此外，可以通過LinkedList來實現(xiàn)stack、queue、deque。
1) LinkedList中的addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()函數(shù)未定義于任何一個interface或base class中，所以只能用于LinkedList中。
1.2. Set
1.2.1 Set（interface）：Set具有和Collection一模一樣的interface（區(qū)別：List加入了自己的函數(shù)），所以Set就是一個Collection，只不過其行為不同罷了。加至Set內的每個元素都必須獨一無二，不與其他元素重復；Set不允許持有重復元素，每個元素都必須定義equals()以判斷所謂的獨一性。
1.2.2 HashSet：一種把查找時間看得很重要的Sets。所有元素都必須定義hashCode()。
1.2.3 TreeSet：底層結構為tree的一種有序的Set。
2． Map
2.1. Map：維護key-value的關聯(lián)性，使你可以使用key來查找value。
1) KeySet()函數(shù)和values()函數(shù)
- import java.util.*;
-
- public class ExplicitStatic{
- public static void printKeys(java/util/Map.java.html" target="_blank">Map m){
- java/lang/System.java.html" target="_blank">System.out.print("Size = " + m.size());
- java/lang/System.java.html" target="_blank">System.out.println(" , Keys: " + m.keySet());
- }
- public static void printValues(java/util/Map.java.html" target="_blank">Map m){
- java/lang/System.java.html" target="_blank">System.out.println("Values: " + m.values());
- }
- public static void test(java/util/Map.java.html" target="_blank">Map m){
- for( int i=1; i<10; i++)
- m.put("km" + i, "m" + i);
- printKeys(m);
- printValues(m);
- java/lang/System.java.html" target="_blank">System.out.println("km1 - " + m.get("km1"));
- java/util/Set.java.html" target="_blank">Set keys = m.keySet(); //（1）
- java/util/Collection.java.html" target="_blank">Collection values = m.values(); //（2）
- keys.remove("km2"); //（3）
- values.remove("m1"); //（4）
- java/lang/System.java.html" target="_blank">System.out.println("km1 - " + m.get("km1"));
- printKeys(m);
- printValues(m);
- }
- public static void main(java/lang/String.java.html" target="_blank">String[] args){
- java/lang/System.java.html" target="_blank">System.out.println("Testing HashMap");
- test(new java/util/HashMap.java.html" target="_blank">HashMap());
- }
- }
結果為：
Testing HashMap
Size = 9 , Keys: [km5, km4, km3, km2, km1, km9, km8, km7, km6]
Values: [m5, m4, m3, m2, m1, m9, m8, m7, m6]
km1 - m1 //執(zhí)行（3）（4）之前
km1 - null
Size = 7 , Keys: [km5, km4, km3, km9, km8, km7, km6] //（5）
Values: [m5, m4, m3, m9, m8, m7, m6] //（6）
在（1）（2）處代碼分別得到了Map中的keys和values。從執(zhí)行（3）（4）前后的代碼可知，對通過keySet()和values()函數(shù)取得的值進行修改會反映到Map本身。
（3）中刪除的是值為“km2”的key，（4）刪除的是值為“m1”的value，且它們是同一個key-value pair，但結果（5）（6）表明，Map中刪除的是兩個key-pair。從而可知，只要刪除了Map中的key或value中的一個，那么整個key-value pair就會被刪除。
2.2. HashMap：可在常量時間內安插元素，或找出一組key-value pair。通過其構造函數(shù)，使用者可以調整效能表現(xiàn)，因為它允許你設定capacity（容量）和loadfactor（負載因子）。
2.3. TreeMap：當你檢視其中的key或key-value pairs時，會以排序形式出現(xiàn)，讓你得到以排序形式得到結果。TreeMap是惟一具有subMap()的一個Map，這個函數(shù)讓你得以返回tree中的部分組成。
三. HashMap的工作原理
1． 如何實現(xiàn)一個Map
1.1 與Map相關的知識
1.1.1 Map.Entry接口
一個實現(xiàn)了Map.Entry接口的類代表的是一個Map中的條目（一個key-value pair）。所以一個Map中必須要有一個實現(xiàn)了Map.Entry接口的類，并用這個類來存放Map中的key-value pair。
1.1.2 public abstract Set entrySet()函數(shù)
1) entrySet()函數(shù)返回一個Set，并且Set中的每一個元素都是一個Map.Entry類型的對象。在entrySet()函數(shù)中要把Map中所有的key-value pair以Map.Entry封裝后存入Set中的。
2) 當對Map進行修改操作后，entrySet()函數(shù)都會被調用。所以對Map的修改也會產生對這個Set的修改。
3) 當用這個Set的iterator進行操作時，不能進行add和addAll的操作。
1.2 實現(xiàn)一個簡單的Map的實例
- import java.util.*;
- /**
- * MPair類實現(xiàn)了Map.Entry
- */
- class MPair
- implements java/util/Map.java.html" target="_blank">Map.Entry, java/lang/Comparable.java.html" target="_blank">Comparable{
- java/lang/Object.java.html" target="_blank">Object key, value; //key和value分別用來存放Map中的key和value
- MPair(java/lang/Object.java.html" target="_blank">Object k, java/lang/Object.java.html" target="_blank">Object v){
- key = k;
- value = v;
- }
- //下面方法實現(xiàn)了Map.Entry接口中的方法
- public java/lang/Object.java.html" target="_blank">Object getKey() { return key; }
- public java/lang/Object.java.html" target="_blank">Object getValue() { return value; }
- public java/lang/Object.java.html" target="_blank">Object setValue(java/lang/Object.java.html" target="_blank">Object v){
- java/lang/Object.java.html" target="_blank">Object result = value;
- value = v;
- return result;
- }
- //下面方法實現(xiàn)了Comparable接口中的方法
- public boolean equals(java/lang/Object.java.html" target="_blank">Object o){
- return key.equals(((MPair)o).key);
- }
- public int compareTo(java/lang/Object.java.html" target="_blank">Object rv){
- return ((java/lang/Comparable.java.html" target="_blank">Comparable)key).compareTo(((MPair)rv).key);
- }
- }
- class SlowMap extends java/util/AbstractMap.java.html" target="_blank">AbstractMap{
- private java/util/ArrayList.java.html" target="_blank">ArrayList
- keys = new java/util/ArrayList.java.html" target="_blank">ArrayList(),
- values = new java/util/ArrayList.java.html" target="_blank">ArrayList();
- public java/lang/Object.java.html" target="_blank">Object put(java/lang/Object.java.html" target="_blank">Object key, java/lang/Object.java.html" target="_blank">Object value){
- java/lang/Object.java.html" target="_blank">Object result = get(key);
- if(!keys.contains(key)){ //（1）
- keys.add(key);
- values.add(value);
- }
- else
- values.set(keys.indexOf(key), value);
- return result;
- }
- public java/lang/Object.java.html" target="_blank">Object get(java/lang/Object.java.html" target="_blank">Object key){
- if(!keys.contains(key)){
- return null;
- }
- else
- return values.get(keys.indexOf(key));
- }
- //用Mpair封裝Map中的key-value pair并存入Set中
- public java/util/Set.java.html" target="_blank">Set entrySet(){
- java/util/Set.java.html" target="_blank">Set entries = new java/util/HashSet.java.html" target="_blank">HashSet();
- java/util/Iterator.java.html" target="_blank">Iterator
- ki = keys.iterator(),
- vi = values.iterator();
- while(ki.hasNext())
- entries.add(new MPair(ki.next(), vi.next()));
- return entries;
- }
- }
- public class ExplicitStatic{
- public static void main(java/lang/String.java.html" target="_blank">String[] args){
- SlowMap m = new SlowMap();
- for( int i=1; i<10; i++)
- m.put("km" + i, "m" + i);
- java/lang/System.java.html" target="_blank">System.out.println(m);
- }
- }
在上面代碼的（1）處，我們要從ArrayList中查找出是否具有key值，而這個查找過程線性查找，且key不具任何順序，所以速度會很慢。
2． 與HashMap相關的幾個函數(shù)
1) hashCode()函數(shù)
Object.hashCode()函數(shù)會為對象產生hash code。如果一個類沒有實現(xiàn)hashCode()函數(shù)，那么在缺省情況下將返回它的對象的內存地址。
2) equals()函數(shù)
Object.equals()在比較兩個對象時，比較的是兩個對象的內存地址。
3． HashMap的工作原理
3.1 用array來表現(xiàn)key的信息。每個key的hashCode()函數(shù)會為key產生一個hash code，而key的hash code作為array的索引。如假設有一個名為bucket的arrsy，姥一個hash code為2的key就被索引到bucket[2]，key所對應的值也在bucket[2]中。
3.1 由于array中存放的是value值，而HashMap的元素個數(shù)可以是無限的，所以array中的元素指向的不是某個key的value，而是指向具有相同的hash code的key的value值（也就是說指向的是一串values值）。如假設array被定義為LinkedList []bucket = new LinkedList[10]，那么bucket[2]中存放的是所有hash code值為2的key的value。
|
|
|
|
|
