HashMap详解

转自：http://blog.csdn.net/meteor_730/article/details/4701875
1、先一个hashmap排序的例子

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();
    ..........
}

2、说一下HashMap的实现
    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 获得在Objecttable的索引值。
   //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记录其位置。

3、Hashtable和HashMap的区别：
    a.Hashtable是Dictionary的子类，HashMap是Map接口的一个实现类；
    b.Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。即是说，在多线程应用程序中，不用专门的操作就安全地可以使用Hashtable 了；而对于HashMap，则需要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得到解决：
Map Collections.synchronizedMap(Map m)
这个方法返回一个同步的Map，这个Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。
    c. 在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。

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 8. 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);
        }
    }
}

输出内容：
[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 8. 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);
        }
    }
}

输出内容：
[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达到高性能同时满足排序的双重目的）。