作者：Ming Chou
原文：
http://access1.sun.com/techarticles/CollectionsMap.html翻譯時(shí)間：2003-8-29
1. 導(dǎo)言
隨著Java[tm] 2標(biāo)準(zhǔn)版中的集合框架的引入，一組通用數(shù)據(jù)結(jié)構(gòu)接口被整合到了Java[tm] 2 SDK，以簡(jiǎn)化程序員的工作，使程序員可以專(zhuān)注于業(yè)務(wù)需求，而不是構(gòu)造數(shù)據(jù)對(duì)象。這個(gè)新的框架為用戶(hù)提供了一些有用的工具和功能，用戶(hù)不需要對(duì)框架的細(xì)節(jié)知道很多，就可以很好地使用它。
在Java[tm]集合框架中，有兩個(gè)主要的接口，（1）Collection接口，包含list和set子接口，（2）Map接口。Collection和Map接口之間的主要區(qū)別在于：Collection中存儲(chǔ)了一組對(duì)象，而Map存儲(chǔ)關(guān)鍵字/值對(duì)。在Map對(duì)象中，每一個(gè)關(guān)鍵字最多有一個(gè)關(guān)聯(lián)的值。一個(gè)很好的日常的例子就是把人們的profile信息和他的社會(huì)安全號(hào)（相當(dāng)于中國(guó)的身份證號(hào)）進(jìn)行關(guān)聯(lián)。社會(huì)安全號(hào)是關(guān)鍵字，而profile就是對(duì)應(yīng)的人映射到的值。
2. Map接口
下面的代碼片斷顯示了Map接口的樣子：
- public interface java.util.Map {
- //Altering Methods
- public Object put(Object key, Object value); //gets Object with key/value mapping
- public Object remove(Object key); //removes Object with key
- public void putAll(java.util.Map); //put all Map elements into current Map
- public void clear(); //removes all mappings from current Map
- //Querying Methods
- public Object get(Object key); //gets Object with key
- public int size(); //returns number of Map elements
- public boolean isEmpty(); //check if Map is empty
- public boolean containsKey(Object); //Checks if map contains object as key
- public boolean containsValue(Object); //Checks if map contains object as value
- public boolean equals(Object); //compares specified Object with current Map
- //Viewing Methods
- public java.util.Set keySet(); //Gets keys
- public java.util.Collection values(); //Gets values
- public java.util.Set entrySet(); //Gets mappings
- public static interface java.util.Map.Entry { //a map-entry (single key/value pair)
- public Object getKey(); //returns current entry key
- public Object getValue(); //returns current entry value
- public Object setValue(Object value); //replaces current value with specified value
- public boolean equals(Object); //compares current object with specified object
- public int hashCode(); //returns hashcode with current map-entry
- }
- }
Map接口為我們提供了完成下面三種主要的功能的方法：
1. Map 改變
2. Map 查詢(xún)
3. Map 視圖
Map的改變方法允許用戶(hù)改變當(dāng)前Map的內(nèi)容，包括關(guān)鍵字/值對(duì)的刪除、更新和插入。
Map的查詢(xún)方法允許用戶(hù)從Map中獲取關(guān)鍵字/值對(duì)。不但有查詢(xún)Map元素的內(nèi)容的方法，也有可以用來(lái)查詢(xún)整個(gè)Map對(duì)象的方法。
Map中一共有三種不同的視圖可以用來(lái)分析關(guān)鍵字/值對(duì)。既然映射中的關(guān)鍵字必須唯一，那么，keySet()方法獲取的是Map中的關(guān)鍵字的一個(gè)Set（Set是唯一數(shù)據(jù)元素的集合）。values()方法返回映射中值的Collection（Collection是允許存儲(chǔ)重復(fù)元素的對(duì)象的集合）。entrySet()方法返回Map.Entrhy的一個(gè)Set。
Map.Entry接口是用來(lái)存儲(chǔ)單個(gè)關(guān)鍵字/值對(duì)的。在Map.Entry中有存儲(chǔ)和獲取單個(gè)關(guān)鍵字/值元素的方法。entrySet()方法返回一組實(shí)現(xiàn)了Map.Entry接口的對(duì)象的Set。Set中的每一個(gè)元素都代表了Map中的一個(gè)獨(dú)立的關(guān)鍵字/值對(duì)。
3. Map 的實(shí)現(xiàn)
下面的部分將Map的三個(gè)通用實(shí)現(xiàn)作一個(gè)簡(jiǎn)單介紹：
1. java.util.Hashtable
2. java.util.HashMap
3. java.util.TreeMap
3.1 java.util.Hashtable
Hashtable對(duì)象把關(guān)鍵字對(duì)象映射到值對(duì)象。提供了允許基于關(guān)鍵字搜索的快速查找的方法。Hashtable是在Java 1.0平臺(tái)中引入的，而下面將要討論的HashMap是在Java 1.2平臺(tái)引入的。Hashtable提供的附加方法（Map接口中沒(méi)有的）有：
- public class java.util.Hashtable extends Dictionary implements Cloneable, Map, Serializable {
- //Hashtable constructors
- //construct a default Hashtable with default capacity and load of 0.75
- public Hashtable();
- //construct a Hashtable with passed capacity and default load of 0.75
- public Hashtable (int initialCapacity);
- //construct Hashtable with passed capacity and load
- public Hashtable(int initialCapacity, float load);
- public Hashtable(Map); //construct Hashtable with passed mapping
-
- //Hashtable specific methods
- public boolean contains(Object); //checks if Object is in Hashtable
- public Enumeration elements(); //returns Enumeration of elements in Hashtable
- public Enumeration keys(); //returns Enumeration of keys in hashtable
- //creates shallow copy of Hashtable(structure copied, but not key/values)
- public Object clone();
- public String toString(); //prints out key/value pairs of Hashtable elements
- //reorganizes all elements in Hashtable, and increases Hashtable capacity
- protected void rehash();
-
- public Object get(Object); //get Value from passed in key
- public Object put(Object key, Object value); //insert key/value pair
- }
Hashtable類(lèi)似于常見(jiàn)的關(guān)鍵字映射到值的表格，但是Hashtable提供了提取數(shù)據(jù)的快速方法。當(dāng)一個(gè)元素插入到Hashtable中時(shí)，關(guān)鍵字對(duì)象被散列（原文：the name of the Object is hashed，似有不妥），返回的整數(shù)值作為值對(duì)象在表中存儲(chǔ)的索引值。 然后，值對(duì)象存儲(chǔ)為散列索引所指向的（表格）單元的值（譯注：這兒的說(shuō)法可以理解，但欠準(zhǔn)確。在Hashtable的實(shí)現(xiàn)中在每個(gè)單元中存儲(chǔ)的是一個(gè)包含了散列碼、關(guān)鍵字、值和指向下一個(gè)Entry的引用的Map.Entry的實(shí)現(xiàn)對(duì)象）。如果，另外具有相同散列碼的對(duì)象也要插入Hashtable，則該對(duì)象將被存儲(chǔ)在一個(gè)原條目開(kāi)始的鏈表中。
Hashtable的初始容量指示了Hashtable中需要分配的空間。由于Hashtable是一個(gè)動(dòng)態(tài)的實(shí)體，需要不斷地大小縮放來(lái)為Hashtable高效地分配空間。裝載因子指示了在Hashtable的容量需要自動(dòng)增長(zhǎng)之前，容許的空間的百分比占用。
The initial capacity of the Hashtable dictates how many spaces are allocated for Objects in the Hashtable. As a Hashtable is a dynamic entity, constant resizing is required to efficiently allocate space for the Hashtable. The load factor indicates how full percentage wise the Hashtable is allowed to become before the Hashtable‘s capacity is automatically increased.
需要注意的兩點(diǎn)是（1）Hashtable是同步的，（2）Hashtable中不允許關(guān)鍵字或值為null。
Two things to note are that (1) Hashtable data is synchronized and (2) the null value is not allowed as a key or value in the Hashtable.
3.2 java.util.HashMap
HashMap非常類(lèi)似于Hashtable，它是從Java 1.2平臺(tái)以后才引入的。HashMap和Hashtable之間有兩個(gè)主要區(qū)別。第一，HashMap是非同步的（為了快速訪問(wèn)），第二，HashMap允許使用null關(guān)鍵字和null值，而Hashtable是不允許的。HashMap的特殊方法（不在Map接口中的）有：
public class java.util.HashMap implements Map, Cloneable, java.io.Serializable {
public HashMap(int initialCapacity, float load); //construct a default HashMap with default capacity and load of 0.75
public HashMap(int initialCapacity); //construct a HashMap with passed capacity and default load of 0.75
public HashMap(); //construct HashMap with passed capacity and load
public Hashmap(Map); //construct HashMap with passed mapping
public Object clone(); //constructs shallow copy of HashMap (keys/values not copied)
public Object get(Object); //get Value from passed in key
public Object put(Object key, Object value); //insert key/value pair
}
自Java 1.2平臺(tái)引入后，HashMap即提供了優(yōu)于Hashtable的性能。雖然HashMap是非同步的，但可以對(duì)它進(jìn)行同步化。如果在一個(gè)多線程的環(huán)境下，HashMap被修改了會(huì)怎么樣？HashMap有一個(gè)快速失效（fast-fail）的迭代器。快速失效意味著，當(dāng)?shù)讓蛹细淖兒?，迭代器將得到通知，通過(guò)拋出ConcurrentModificationException從而導(dǎo)致對(duì)下一個(gè)元素的提取失敗。
3.3 java.util.TreeMap
TreeMap實(shí)現(xiàn)了Map接口，并把元素存儲(chǔ)在樹(shù)中。TreeMap在操作上需要比HashMap更多一些的開(kāi)銷(xiāo)，但是由于樹(shù)的結(jié)構(gòu)使然，它返回排序的關(guān)鍵字。如果沒(méi)有按照關(guān)鍵字順序提取Map的元素的需求，那么HashMap是更實(shí)用的結(jié)構(gòu)。TreeMap中實(shí)現(xiàn)的不包括在Map接口中的public成員有：
- public class java.TreeMap implements SortedMap, Cloneable, java.io.Serializable {
- public TreeMap(); //new TreeMap
- public TreeMap(Comparator); //new TreeMap using Comparator
- public TreeMap(Map); //new TreeMap using Map
- public TreeMap(SortedMap); //new TreeMap using sortedMap
- public Comparator comparator();
- public Object firstKey(); //returns first Key
- public Object lastKey(); //returns last Key
- public Object clone(); //returns shallow copy of TreeMap
- public SortedMap headMap(Object); //returns SortedMap of all elements upto Object
- public SortedMap tailMap(Object); //returns SortedMap of all elements after Object
- public SortedMap subMap(Object, Object); //returns SortedMap of all elements between keys
- public Object get(Object); //get Value from passed in key
- public Object put(Object key, Object value); //insert key/value pair
- }
當(dāng)你需要以一定順序存儲(chǔ)對(duì)象時(shí)，TreeMap是非常有用的。例如，電話薄或者字典是使用TreeMap的理想候選。SortedMap是Map的子接口。TreeMap是使用SortedMap接口的唯一實(shí)現(xiàn)。
4. 實(shí)例
在下面的部分，我們將展示兩個(gè)實(shí)例，第一個(gè)展示了HashMap的使用，第二個(gè)則使用了TreeMap。注意代碼中的唯一差別僅在一行而已，位于calendar Map實(shí)例化時(shí)，然而，由于TreeMap和HashMap的存儲(chǔ)行為的不同，最終的輸出就大不相同了。
4.1 HashMap 實(shí)例
- import java.util.*;
- public class ExampleHashMap {
- //calendar Map
- Map calendar = new HashMap();
- //constructor to add all elements into Map
- public ExampleHashMap(String d[], String i[]){
- for (int x=0; x<d.length; x++)
- calendar.put(d[x], i[x]);
- }
- //main method
- public static void main(String args[]) {
- //Data to be inserted into calendar
- String [] dates = {"10/31/01", "01/01/01", "03/05/01", "02/04/01"};
- String [] items = {"Halloween", "New Years", "Birthday", "Anniversary"};
- //create instance of class
- ExampleHashMap example = new ExampleHashMap(dates, items);
- //print out all key/value pairs in map
- System.out.println("map= " + example.calendar);
- //retrieve mappings into Set
- Set mappings = example.calendar.entrySet();
- System.out.println("object \t\t\tkey\t\tvalue");
- //iterate through mappings and print content
- for (Iterator i = mappings.iterator(); i.hasNext();) {
- Map.Entry me = (Map.Entry)i.next();
- Object ok = me.getKey();
- Object ov = me.getValue();
- System.out.print(me + "\t");
- System.out.print(ok + "\t");
- System.out.println(ov);
- }
- }
- }
- HashMap的輸出 (不同的編譯器會(huì)有不同順序的輸出):
[pre]/tmp> java ExampleHashMap
map= {01/01/01=New Years, 03/05/01=Birthday, 02/04/01=Anniversary, 10/31/01=Halloween}
object key value
01/01/01=New Years 01/01/01 New Years
03/05/01=Birthday 03/05/01 Birthday
02/04/01=Anniversary 02/04/01 Anniversary
10/31/01=Halloween 10/31/01 Halloween[/pre]
注意在HashMap對(duì)象存儲(chǔ)既不是按照年代順序，也不是按照字母順序。輸出的順序其實(shí)是依賴(lài)于你選用了哪種編譯器，以及機(jī)器的設(shè)置。實(shí)際上Halloween是第一個(gè)“put”到HashMap的，但是卻存儲(chǔ)在HashMap的最后。
4.2 TreeMap 實(shí)例
- import java.util.*;
- public class ExampleTreeMap {
- //calendar Map
- Map calendar = new TreeMap();
- //constructor to add all elements into Map
- public ExampleTreeMap(String d[], String i[]){
- for (int x=0; x<d.length; x++)
- calendar.put(d[x], i[x]);
- }
- //main method
- public static void main(String args[]) {
- //Data to be inserted into calendar
- String [] dates = {"10/31/01", "01/01/01", "03/05/01", "02/04/01"};
- String [] items = {"Halloween", "New Years", "Birthday", "Anniversary"};
- //create instance of class
- ExampleTreeMap example = new ExampleTreeMap(dates, items);
- //print out all key/value pairs in map
- System.out.println("map= " + example.calendar);
- //retrieve mappings into Set
- Set mappings = example.calendar.entrySet();
- System.out.println("object \t\t\tkey\t\tvalue");
- //iterate through mappings and print content
- for (Iterator i = mappings.iterator(); i.hasNext();) {
- Map.Entry me = (Map.Entry)i.next();
- Object ok = me.getKey();
- Object ov = me.getValue();
- System.out.print(me + "\t");
- System.out.print(ok + "\t");
- System.out.println(ov);
- }
- }
- }
- TreeMap的輸出:
[pre]/tmp> java ExampleTreeMap
map= {01/01/01=New Years, 02/04/01=Anniversary, 03/05/01=Birthday, 10/31/01=Halloween}
object key value
01/01/01=New Years 01/01/01 New Years
02/04/01=Anniversary 02/04/01 Anniversary
03/05/01=Birthday 03/05/01 Birthday
10/31/01=Halloween 10/31/01 Halloween[/pre]
TreeMap的輸出比HashMap更加具有可預(yù)言性。注意在TreeMap中映射以關(guān)鍵字的字母順序存儲(chǔ)。不同于HashMap的輸出，在一個(gè)實(shí)際的世界日歷程序中，TreeMap的輸出將更加有用。正如前面提及的，使用TreeMap數(shù)據(jù)結(jié)構(gòu)的一個(gè)缺點(diǎn)是，當(dāng)你在TreeMap結(jié)構(gòu)中“put”或“remove”元素時(shí)，因?yàn)樾枰判驈亩枰恍╅_(kāi)銷(xiāo)，這會(huì)影響到程序的性能。（譯注：可以先使用HashMap，在需要順序輸出時(shí)，通過(guò)把HashMap對(duì)象作為參數(shù)傳入，構(gòu)造一個(gè)TreeMap達(dá)到高性能同時(shí)滿足排序的雙重目的）。
5. 總結(jié)
作為集合包的一部分，Map接口和其不同實(shí)現(xiàn)提供了存儲(chǔ)關(guān)鍵字/值對(duì)的方便的途徑。在考慮應(yīng)該選用哪個(gè)實(shí)現(xiàn)時(shí)的一般準(zhǔn)則是：當(dāng)元素的順序很重要時(shí)選用TreeMap，當(dāng)元素不必以特定的順序進(jìn)行存儲(chǔ)時(shí)，使用HashMap。Hashtable的使用不被推薦，因?yàn)镠ashMap提供了所有類(lèi)似的功能，并且允許得更快。當(dāng)你需要在多線程環(huán)境下使用時(shí)，HashMap也可以轉(zhuǎn)換為同步的。
