8/24/2010

Hashtable 和 HashMap 的区别

1.        基础:Hashtable是继承了Dictionary;
      Hashmap是实现了Map接口;
2.        同步:Hashtable是线程同步的而Hashmap不是
3.        Null值问题:Hashtable不允许任何形式的null值,而Hashmap是允许的(包括key和value);
4.        遍历:它们对于Entry的遍历都是相同的;
entry的遍历:都可以通过entrySet()实现,返回Set<Map.Entry<K,V>>;
value的遍历:都可以通过values()实现,返回Collection<V>;
但Hashtable还可以通过elements()来获取Enumeration<V>形式的迭代器;
    public synchronizedEnumeration<V> elements();
key的遍历:俩都可以通过keySet()来获取Set<K>形式的key的集合;
但Hashtable可以通过keys()来获得Enumeration<K>形式的迭代器来直接遍历key.

总体来说,HashMap无论对于Entry,key还是value都不能直接获得相关的迭代器;
而Hashtable也只能通过Set来获取Entry的集合,但对于key和value,则既可以获取其collocation形式的集合,由可以直接获取其迭代器.
造成Hashtable和HashMap有关遍历方法的共性与差异的原因在于: 共性是由于它们都实现了Map接口; 差异在于Hashtable继承自Dictionary类而HashMap没有.
对于这些方法的记忆也很简单:
首先记Map接口的方法,因为Map的特性决定了key值和Entry值不能重复,而value值可以重复。所以Map接口对于key和Entry都返回set型,即keySet()和entrySet(),而value则为Collection型,即values();
Dictionary没有考虑这么多,key值直接通过Enumeration形式的keys()获得,value值通过Enumeration形式的elements()获得。
5.        默认大小:Hashtable是11;   Hashmap是16;
大小的增长方式:
Hashtable是old*2+1;
Hashmap是old*2
    而且它的大小一定是2的指数:
    利用哈希值去找索引的实现是:returnh & (length-1);
    这里length即表示大小,所以从这个角度去看必然要求大小是2的倍数;因为如果是2^n+1,length-1刚好是10000000,会造成大量的hash冲突。
    具体的实现代码也证实了这一点,因为在自动增长的过程中肯定是×2的,所以只有可能在初始化指定大小的时候造成不为2^n的情况:
       while (capacity < initialCapacity)
            capacity <<= 1;
    只要capacity小于初始大小,就向右移1位,即×2;所以HashMap的容量肯定是2的n次方。
6.        哈希值的实现不同
HashMap:
        int hash = hash(key.hashCode());
        int i = indexFor(hash,table.length);

static int hash(int h) {
        h ^= (h >>> 20) ^ (h>>> 12);
        return h ^ (h >>> 7) ^(h >>> 4);
    }
    static int indexFor(int h, int length){
        return h & (length-1);
    }

Hashtable:
         int hash = key.hashCode();
         int index = (hash &0x7FFFFFFF) % tab.length;