map学习

作者：Ming Chou
原文：http://access1.sun.com/techarticles/CollectionsMap.html
翻译时间：2003-8-29


1. 导言
随着Java[tm] 2标准版中的集合框架的引入，一组通用数据结构接口被整合到了Java[tm] 2 SDK，以简化程序员的工作，使程序员可以专注于业务需求，而不是构造数据对象。这个新的框架为用户提供了一些有用的工具和功能，用户不需要对框架的细节知道很多，就可以很好地使用它。

在Java[tm]集合框架中，有两个主要的接口，（1）Collection接口，包含list和set子接口，（2）Map接口。Collection和Map接口之间的主要区别在于：Collection中存储了一组对象，而Map存储关键字/值对。在Map对象中，每一个关键字最多有一个关联的值。一个很好的日常的例子就是把人们的profile信息和他的社会安全号（相当于中国的身份证号）进行关联。社会安全号是关键字，而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是唯一数据元素的集合）。values()方法返回映射中值的Collection（Collection是允许存储重复元素的对象的集合）。entrySet()方法返回Map.Entrhy的一个Set。

Map.Entry接口是用来存储单个关键字/值对的。在Map.Entry中有存储和获取单个关键字/值元素的方法。entrySet()方法返回一组实现了Map.Entry接口的对象的Set。Set中的每一个元素都代表了Map中的一个独立的关键字/值对。


3. Map 的实现

下面的部分将Map的三个通用实现作一个简单介绍：

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提供了提取数据的快速方法。当一个元素插入到Hashtable中时，关键字对象被散列（原文：the name of the Object is hashed，似有不妥），返回的整数值作为值对象在表中存储的索引值。 然后，值对象存储为散列索引所指向的（表格）单元的值（译注：这儿的说法可以理解，但欠准确。在Hashtable的实现中在每个单元中存储的是一个包含了散列码、关键字、值和指向下一个Entry的引用的Map.Entry的实现对象）。如果，另外具有相同散列码的对象也要插入Hashtable，则该对象将被存储在一个原条目开始的链表中。
Hashtable的初始容量指示了Hashtable中需要分配的空间。由于Hashtable是一个动态的实体，需要不断地大小缩放来为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之间有两个主要区别。第一，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即提供了优于Hashtable的性能。虽然HashMap是非同步的，但可以对它进行同步化。如果在一个多线程的环境下，HashMap被修改了会怎么样？HashMap有一个快速失效（fast-fail）的迭代器。快速失效意味着，当底层集合改变后，迭代器将得到通知，通过抛出ConcurrentModificationException从而导致对下一个元素的提取失败。

3.3 java.util.TreeMap

TreeMap实现了Map接口，并把元素存储在树中。TreeMap在操作上需要比HashMap更多一些的开销，但是由于树的结构使然，它返回排序的关键字。如果没有按照关键字顺序提取Map的元素的需求，那么HashMap是更实用的结构。TreeMap中实现的不包括在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接口的唯一实现。

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的输出 (不同的编译器会有不同顺序的输出):

/tmp> java ExampleHashMapmap= {01/01/01=New Years, 03/05/01=Birthday, 02/04/01=Anniversary, 10/31/01=Halloween}object                  key             value01/01/01=New Years      01/01/01        New Years03/05/01=Birthday       03/05/01        Birthday02/04/01=Anniversary    02/04/01        Anniversary10/31/01=Halloween      10/31/01        Halloween

注意在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的输出:

/tmp> java ExampleTreeMapmap= {01/01/01=New Years, 02/04/01=Anniversary, 03/05/01=Birthday, 10/31/01=Halloween}object                  key             value01/01/01=New Years      01/01/01        New Years02/04/01=Anniversary    02/04/01        Anniversary03/05/01=Birthday       03/05/01        Birthday10/31/01=Halloween      10/31/01        Halloween


TreeMap的输出比HashMap更加具有可预言性。注意在TreeMap中映射以关键字的字母顺序存储。不同于HashMap的输出，在一个实际的世界日历程序中，TreeMap的输出将更加有用。正如前面提及的，使用TreeMap数据结构的一个缺点是，当你在TreeMap结构中“put”或“remove”元素时，因为需要排序从而需要一些开销，这会影响到程序的性能。（译注：可以先使用HashMap，在需要顺序输出时，通过把HashMap对象作为参数传入，构造一个TreeMap达到高性能同时满足排序的双重目的）。

5. 总结

作为集合包的一部分，Map接口和其不同实现提供了存储关键字/值对的方便的途径。在考虑应该选用哪个实现时的一般准则是：当元素的顺序很重要时选用TreeMap，当元素不必以特定的顺序进行存储时，使用HashMap。Hashtable的使用不被推荐，因为HashMap提供了所有类似的功能，并且允许得更快。当你需要在多线程环境下使用时，HashMap也可以转换为同步的