HashMap按key排序(转)

HashMap按key排序

 HashMap   map   =   new   HashMap();  
         map.put("0201",   "0201");  
         map.put("01",   "01");  
         map.put("0304",   "0304");  
         map.put("0101",   "0101");  

         Object[]   key   =     map.keySet().toArray();  
         Arrays.sort(key);  

         for   (int   i   =   0;   i   <   key.length;   i++)   {  
                 System.out.println(map.get(key[i]));  
         }  


-----------------------------------------------------------------------

Map hashMap = new HashMap();

List arrayList = new ArrayList(hashMap.entrySet());

Collections.sort(arrayList, new Comparator() {
   public int compare(Object o1, Object o2) {
    Map.Entry obj1 = (Map.Entry) o1;
    Map.Entry obj2 = (Map.Entry) o2;
    return (obj1.getKey()).toString().compareTo(obj2.getKey());
   }
  });
//  将HASHMAP中的数据排序-------------------------------------------
  for (Iterator iter = arrayList.iterator(); iter.hasNext();) {
   Map.Entry entry = (Map.Entry) iter.next();
   String     key = (String)entry.getKey();
   ..........
  }
--------------------------------------------------------------------------------------------------------
HashMap可谓JDK的一大实用工具，把各个Object映射起来，实现了“键－－值”对应的快速存取。但实际里面做了些什么呢？

　　在这之前，先介绍一下负载因子和容量的属性。大家都知道其实一个 HashMap 的实际容量就 因子*容量，其默认值是 16×0.75＝12； 这个很重要，对效率很一定影响！当存入HashMap的对象超过这个容量时，HashMap 就会重新构造存取表。这就是一个大问题，我后面慢慢介绍，反正，如果你已经知道你大概要存放多少个对象，最好设为该实际容量的能接受的数字。

　　两个关键的方法，put和get：

　　先有这样一个概念，HashMap是声明了 Map，Cloneable, Serializable 接口，和继承了 AbstractMap 类，里面的 Iterator 其实主要都是其内部类HashIterator 和其他几个 iterator 类实现，当然还有一个很重要的继承了Map.Entry 的 Entry 内部类，由于大家都有源代码，大家有兴趣可以看看这部分，我主要想说明的是 Entry 内部类。它包含了hash，value，key 和next 这四个属性，很重要。put的源码如下

　　public Object put(Object key, Object value) {
　　Object k = maskNull(key);

　　这个就是判断键值是否为空，并不很深奥，其实如果为空，它会返回一个static Object 作为键值，这就是为什么HashMap允许空键值的原因。

　　int hash = hash(k);
　　int i = indexFor(hash, table.length);

　　这连续的两步就是 HashMap 最牛的地方！研究完我都汗颜了，其中 hash 就是通过 key 这个Object的 hashcode 进行 hash，然后通过 indexFor 获得在Object table的索引值。

　　table？？？不要惊讶，其实HashMap也神不到哪里去，它就是用 table 来放的。最牛的就是用 hash 能正确的返回索引。其中的hash算法，我跟JDK的作者 Doug 联系过，他建议我看看《The art of programing vol3》可恨的是，我之前就一直在找，我都找不到，他这样一提，我就更加急了，可惜口袋空空啊！！！

　　不知道大家有没有留意 put 其实是一个有返回的方法，它会把相同键值的 put 覆盖掉并返回旧的值！如下方法彻底说明了 HashMap 的结构，其实就是一个表加上在相应位置的Entry的链表：

　　for (Entry e = table[i]; e != null; e = e.next) {
　　if (e.hash == hash && eq(k, e.key)) {
　　Object oldvalue = e.value;
　　e.value = value; //把新的值赋予给对应键值。
　　e.recordAccess(this); //空方法，留待实现
　　return oldvalue; //返回相同键值的对应的旧的值。
　　}
　　}
　　modCount++; //结构性更改的次数
　　addEntry(hash, k, value, i); //添加新元素，关键所在！
　　return null; //没有相同的键值返回
　　}

　　我们把关键的方法拿出来分析：

　　void addEntry(int hash, Object key, Object value, int bucketIndex) {
　　table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);

　　因为 hash 的算法有可能令不同的键值有相同的hash码并有相同的table索引，如：key＝“33”和key＝Object g的hash都是－8901334，那它经过indexfor之后的索引一定都为i，这样在new的时候这个Entry的next就会指向这个原本的table[i]，再有下一个也如此，形成一个链表，和put的循环对定e.next获得旧的值。到这里，HashMap的结构，大家也十分明白了吧？
所谓的重构也不神，就是建一个两倍大的table（我在别的论坛上看到有人说是两倍加1，把我骗了），然后再一个个indexfor进去！注意！！这就是效率！！如果你能让你的HashMap不需要重构那么多次，效率会大大提高！

　　说到这里也差不多了，get比put简单得多，大家，了解put，get也差不了多少了。对于collections我是认为，它是适合广泛的，当不完全适合特有的，如果大家的程序需要特殊的用途，自己写吧，其实很简单。（作者是这样跟我说的，他还建议我用LinkedHashMap,我看了源码以后发现，LinkHashMap其实就是继承HashMap的，然后override相应的方法，有兴趣的同人，自己looklook）建个 Object table，写相应的算法，就ok啦。

　　举个例子吧，像 Vector，list 啊什么的其实都很简单，最多就多了的同步的声明，其实如果要实现像Vector那种，插入，删除不多的，可以用一个Object table来实现，按索引存取，添加等。

　　如果插入，删除比较多的，可以建两个Object table，然后每个元素用含有next结构的，一个table存，如果要插入到i，但是i已经有元素，用next连起来，然后size＋＋，并在另一个table记录其位置。
---------------------------------------------------------------------------------------------------------------------------------------------------------
Hashtable和HashMap的区别：
1.Hashtable是Dictionary的子类，HashMap是Map接口的一个实现类；
2.Hashtable中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。即是说，在多线程应用程序中，不用专门的操作就安全地可以使用Hashtable了；而对于HashMap，则需要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得到解决：
Map Collections.synchronizedMap(Map m)
这个方法返回一个同步的Map，这个Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。
3.在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。
---------------------------------------------------------------------------------------------------------------------------------------------------------

下面的部分，我们将展示两个实例，第一个展示了HashMap的使用，第二个则使用了TreeMap。注意代码中的唯一差别仅在一行而已，位于calendar Map实例化时，然而，由于TreeMap和HashMap的存储行为的不同，最终的输出就大不相同了。

4.1 HashMap 实例

1. import java.util.*;
2. public class ExampleHashMap {
3.    //calendar Map 
4.    Map calendar = new  HashMap();
5.    //constructor to add all elements into Map
6.    public ExampleHashMap(String d[], String i[]){
7.       for (int x=0; x<d.length; x++)
8.          calendar.put(d[x], i[x]);
9.    }
10.    //main method
11.    public static void main(String args[]) {
12.       //Data to be inserted into calendar
13.       String [] dates = {"10/31/01", "01/01/01", "03/05/01", "02/04/01"};
14.       String [] items = {"Halloween", "New Years", "Birthday", "Anniversary"};
15.       //create instance of class
16.       ExampleHashMap example = new ExampleHashMap(dates, items);
17.       //print out all key/value pairs in map
18.       System.out.println("map= " + example.calendar);
19.       //retrieve mappings into Set
20.       Set mappings = example.calendar.entrySet();
21.       System.out.println("object \t\t\tkey\t\tvalue");
22.       //iterate through mappings and print content
23.       for (Iterator i = mappings.iterator(); i.hasNext();) {
24.          Map.Entry me = (Map.Entry)i.next();
25.          Object ok = me.getKey();
26.          Object ov = me.getValue();
27.          System.out.print(me + "\t");
28.          System.out.print(ok + "\t");
29.          System.out.println(ov); 
30.       }
31.    }
32. }

- 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 实例

1. import java.util.*;
2. public class ExampleTreeMap {
3.    //calendar Map 
4.    Map calendar = new TreeMap();
5.    //constructor to add all elements into Map
6.    public ExampleTreeMap(String d[], String i[]){
7.       for (int x=0; x<d.length; x++)
8.          calendar.put(d[x], i[x]);
9.    }
10.    //main method
11.    public static void main(String args[]) {
12.       //Data to be inserted into calendar
13.       String [] dates = {"10/31/01", "01/01/01", "03/05/01", "02/04/01"};
14.       String [] items = {"Halloween", "New Years", "Birthday", "Anniversary"};
15.       //create instance of class
16.       ExampleTreeMap example = new ExampleTreeMap(dates, items);
17.       //print out all key/value pairs in map
18.       System.out.println("map= " + example.calendar);
19.       //retrieve mappings into Set
20.       Set mappings = example.calendar.entrySet();
21.       System.out.println("object \t\t\tkey\t\tvalue");
22.       //iterate through mappings and print content
23.       for (Iterator i = mappings.iterator(); i.hasNext();) {
24.          Map.Entry me = (Map.Entry)i.next();
25.          Object ok = me.getKey();
26.          Object ov = me.getValue();
27.          System.out.print(me + "\t");
28.          System.out.print(ok + "\t");
29.          System.out.println(ov); 
30.       }
31.    }
32. }

- 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数据结构的一个缺点是，当你在TreeMap结构中“put”或“remove”元素时，因为需要排序从而需要一些开销，这会影响到程序的性能。（译注：可以先使用HashMap，在需要顺序输出时，通过把HashMap对象作为参数传入，构造一个TreeMap达到高性能同时满足排序的双重目的）。

<script type="text/javascript"></script>