二、java集合类、深入理解Hashtable以及和HashMap的对比
上一节认识了HashMap，作为经常和HashMap对比的Hashtable，这里我们也来探讨一下。
首先打开了Hashtable的源码，类图如下：
和HashMap不同的是，Hashtable继承了Dictionary类，而HashMap继承了AbstractMap类。
分别打开AbstactMap类和Dictionary类查看，发现，AbstactMap类虽然是个虚类，但是也提供了很多已实现的方法，而Dictionary类等同于一个接口，并没有做任何实现。
回到Hashtable的类，还是先写一个最简单的使用吧
简单看了一下Hashtable的类变量
Hashtable也是维护了一个Entry的数组，但是这里没有设置为一个空的数组。
从构造函数来看，和HashMap大同小异。但是Hashtable并没有采用2的幂次方的数值作为table递增的方案，而是默认用11，扩容方案也是newSize = oldSize*2 + 1的方案。
再来看看put方法：
Hashtable在put的方法上加了synchronized关键字，所以这里多线程在访问时都是同步操作，当然不会有并发问题了。
Hashtable中几乎所有的方法都有synchronized关键字，这在保证线程安全的同时，也造成了Hashtable的效率不如HashMap。
Hashtable和HashMap还有哪些不同呢？
此处网上有很多详细的对比，相信看完上面一些文字，大家可能也会带着一些疑问，我在另一个网页上看到了关于HashMap和Hashtable很详细的对比。这里就直接引他山之玉了。
地址：http://www.importnew.com/24822.html
详细的对比可以直接去上面的网站看了，这里仅截出我认为比较重要部分的截图：
1. HashMap支持Null key和Null value，Hashtable不支持
4.2 算法
上一小节已经说了用来表示哈希表的内部数据结构。HashMap/HashTable还需要有算法来将给定的键key，映射到确定的hash桶（数组位置）。需要有算法在哈希桶内的键值对多到一定程度时，扩充哈希表的大小（数组的大小）。本小节比较这两个类在算法层面有哪些不同。
初始容量大小和每次扩充容量大小的不同。先看代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
以下代码及注释来自java.util.HashTable// 哈希表默认初始大小为11public Hashtable() {
this(11, 0.75f);
}protected void rehash() {
int oldCapacity = table.length;
Entry<K,V>[] oldMap = table;
// 每次扩容为原来的2n+1
int newCapacity = (oldCapacity << 1) + 1;
// ...
}以下代码及注释来自java.util.HashMap// 哈希表默认初始大小为2^4=16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
void addEntry(int hash, K key, V value, int bucketIndex) {
// 每次扩充为原来的2n
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
} |
可以看到HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。HashMap默认的初始化大小为16，之后每次扩充为原来的2倍。还有我没列出代码的一点，就是如果在创建时给定了初始化大小，那么HashTable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。
也就是说HashTable会尽量使用素数、奇数。而HashMap则总是使用2的幂作为哈希表的大小。我们知道当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀（具体证明，见这篇文章），所以单从这一点上看，HashTable的哈希表大小选择，似乎更高明些。但另一方面我们又知道，在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。所以从hash计算的效率上，又是HashMap更胜一筹。
所以，事实就是HashMap为了加快hash的速度，将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题，所以HashMap为解决这问题，又对hash算法做了一些改动。具体我们来看看，在获取了key对象的hashCode之后，HashTable和HashMap分别是怎样将他们hash到确定的哈希桶（Entry数组位置）中的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
以下代码及注释来自java.util.HashTable// hash 不能超过Integer.MAX_VALUE 所以要取其最小的31个bitint hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
// 直接计算key.hashCode()private int hash(Object k) {
// hashSeed will be zero if alternative hashing is disabled.
return hashSeed ^ k.hashCode();
}以下代码及注释来自java.util.HashMapint hash = hash(key);
int i = indexFor(hash, table.length);
// 在计算了key.hashCode()之后，做了一些位运算来减少哈希冲突final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}// 取模不再需要做除法static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
} |
正如我们所言，HashMap由于使用了2的幂次方，所以在取模运算时不需要做除法，只需要位的与运算就可以了。但是由于引入的hash冲突加剧问题，HashMap在调用了对象的hashCode方法之后，又做了一些位运算在打散数据。关于这些位计算为什么可以打散数据的问题，本文不再展开了。感兴趣的可以看这里。
如果你有细心读代码，还可以发现一点，就是HashMap和HashTable在计算hash时都用到了一个叫hashSeed的变量。这是因为映射到同一个hash桶内的Entry对象，是以链表的形式存在的，而链表的查询效率比较低，所以HashMap/HashTable的效率对哈希冲突非常敏感，所以可以额外开启一个可选hash（hashSeed），从而减少哈希冲突。因为这是两个类相同的一点，所以本文不再展开了，感兴趣的看这里。事实上，这个优化在JDK 1.8中已经去掉了，因为JDK 1.8中，映射到同一个哈希桶（数组位置）的Entry对象，使用了红黑树来存储，从而大大加速了其查找效率。
线程安全的部分上面也简单的说明过了，下面是网页上的说法：