集合框架中的map接口的使用

duduwolf 2005-07-14

展開全文

作者：Ming Chou
原文：http://access1./techarticles/CollectionsMap.html
翻譯時間：2003-8-29

1. 導言

隨著Java[tm] 2標準版中的集合框架的引入，一組通用數(shù)據(jù)結構接口被整合到了Java[tm] 2 SDK，以簡化程序員的工作，使程序員可以專注于業(yè)務需求，而不是構造數(shù)據(jù)對象。這個新的框架為用戶提供了一些有用的工具和功能，用戶不需要對框架的細節(jié)知道很多，就可以很好地使用它。

在Java[tm]集合框架中，有兩個主要的接口，（1）Collection接口，包含list和set子接口，（2）Map接口。Collection和Map接口之間的主要區(qū)別在于：Collection中存儲了一組對象，而Map存儲關鍵字/值對。在Map對象中，每一個關鍵字最多有一個關聯(lián)的值。一個很好的日常的例子就是把人們的profile信息和他的社會安全號（相當于中國的身份證號）進行關聯(lián)。社會安全號是關鍵字，而profile就是對應的人映射到的值。

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 查詢
3.    Map 視圖

Map的改變方法允許用戶改變當前Map的內容，包括關鍵字/值對的刪除、更新和插入。

Map的查詢方法允許用戶從Map中獲取關鍵字/值對。不但有查詢Map元素的內容的方法，也有可以用來查詢整個Map對象的方法。

Map中一共有三種不同的視圖可以用來分析關鍵字/值對。既然映射中的關鍵字必須唯一，那么，keySet()方法獲取的是Map中的關鍵字的一個Set（Set是唯一數(shù)據(jù)元素的集合）。values()方法返回映射中值的Collection（Collection是允許存儲重復元素的對象的集合）。entrySet()方法返回Map.Entrhy的一個Set。

Map.Entry接口是用來存儲單個關鍵字/值對的。在Map.Entry中有存儲和獲取單個關鍵字/值元素的方法。entrySet()方法返回一組實現(xiàn)了Map.Entry接口的對象的Set。Set中的每一個元素都代表了Map中的一個獨立的關鍵字/值對。

3. Map 的實現(xiàn)

下面的部分將Map的三個通用實現(xiàn)作一個簡單介紹：

1. java.util.Hashtable
2. java.util.HashMap
3. java.util.TreeMap

3.1 java.util.Hashtable

Hashtable對象把關鍵字對象映射到值對象。提供了允許基于關鍵字搜索的快速查找的方法。Hashtable是在Java 1.0平臺中引入的，而下面將要討論的HashMap是在Java 1.2平臺引入的。Hashtable提供的附加方法（Map接口中沒有的）有：

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類似于常見的關鍵字映射到值的表格，但是Hashtable提供了提取數(shù)據(jù)的快速方法。當一個元素插入到Hashtable中時，關鍵字對象被散列（原文：the name of the Object is hashed，似有不妥），返回的整數(shù)值作為值對象在表中存儲的索引值。然后，值對象存儲為散列索引所指向的（表格）單元的值（譯注：這兒的說法可以理解，但欠準確。在Hashtable的實現(xiàn)中在每個單元中存儲的是一個包含了散列碼、關鍵字、值和指向下一個Entry的引用的Map.Entry的實現(xiàn)對象）。如果，另外具有相同散列碼的對象也要插入Hashtable，則該對象將被存儲在一個原條目開始的鏈表中。
Hashtable的初始容量指示了Hashtable中需要分配的空間。由于Hashtable是一個動態(tài)的實體，需要不斷地大小縮放來為Hashtable高效地分配空間。裝載因子指示了在Hashtable的容量需要自動增長之前，容許的空間的百分比占用。
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.
需要注意的兩點是（1）Hashtable是同步的，（2）Hashtable中不允許關鍵字或值為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非常類似于Hashtable，它是從Java 1.2平臺以后才引入的。HashMap和Hashtable之間有兩個主要區(qū)別。第一，HashMap是非同步的（為了快速訪問），第二，HashMap允許使用null關鍵字和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平臺引入后，HashMap即提供了優(yōu)于Hashtable的性能。雖然HashMap是非同步的，但可以對它進行同步化。如果在一個多線程的環(huán)境下，HashMap被修改了會怎么樣？HashMap有一個快速失效（fast-fail）的迭代器。快速失效意味著，當?shù)讓蛹细淖兒螅鲗⒌玫酵ㄖ?，通過拋出ConcurrentModificationException從而導致對下一個元素的提取失敗。

3.3 java.util.TreeMap

TreeMap實現(xiàn)了Map接口，并把元素存儲在樹中。TreeMap在操作上需要比HashMap更多一些的開銷，但是由于樹的結構使然，它返回排序的關鍵字。如果沒有按照關鍵字順序提取Map的元素的需求，那么HashMap是更實用的結構。TreeMap中實現(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
}

當你需要以一定順序存儲對象時，TreeMap是非常有用的。例如，電話薄或者字典是使用TreeMap的理想候選。SortedMap是Map的子接口。TreeMap是使用SortedMap接口的唯一實現(xiàn)。

4. 實例

在下面的部分，我們將展示兩個實例，第一個展示了HashMap的使用，第二個則使用了TreeMap。注意代碼中的唯一差別僅在一行而已，位于calendar Map實例化時，然而，由于TreeMap和HashMap的存儲行為的不同，最終的輸出就大不相同了。

4.1 HashMap 實例

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的輸出 (不同的編譯器會有不同順序的輸出):
[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對象存儲既不是按照年代順序，也不是按照字母順序。輸出的順序其實是依賴于你選用了哪種編譯器，以及機器的設置。實際上Halloween是第一個“put”到HashMap的，但是卻存儲在HashMap的最后。

4.2 TreeMap 實例

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更加具有可預言性。注意在TreeMap中映射以關鍵字的字母順序存儲。不同于HashMap的輸出，在一個實際的世界日歷程序中，TreeMap的輸出將更加有用。正如前面提及的，使用TreeMap數(shù)據(jù)結構的一個缺點是，當你在TreeMap結構中“put”或“remove”元素時，因為需要排序從而需要一些開銷，這會影響到程序的性能。（譯注：可以先使用HashMap，在需要順序輸出時，通過把HashMap對象作為參數(shù)傳入，構造一個TreeMap達到高性能同時滿足排序的雙重目的）。

5. 總結

作為集合包的一部分，Map接口和其不同實現(xiàn)提供了存儲關鍵字/值對的方便的途徑。在考慮應該選用哪個實現(xiàn)時的一般準則是：當元素的順序很重要時選用TreeMap，當元素不必以特定的順序進行存儲時，使用HashMap。Hashtable的使用不被推薦，因為HashMap提供了所有類似的功能，并且允許得更快。當你需要在多線程環(huán)境下使用時，HashMap也可以轉換為同步的。