JCF之HashMap剖析(二)

So not being able to contain my curiosity I wrote to Doug Lea and Doug kindly replied and his reply is...

"...The best answer is to read Donald Knuth's Art of Computer
Programming sections on hash tables where it explains
why, how, and when using power-of-two sizes works best.
In general, you need to use pre-conditioning functions
(as seen HashMap.hash) to make them work well, but given
these, they are faster than prime-number techniques..."

大意是：Knuth的《The Art of Computer Programming》中关于hash tables的章节对将容器大小设为2的幂次效率更高作出了解释，
而为了获得这样的效率，需要做一些前期工作(像hash函数中那样)。
帖子链接：点击打开链接
这个问题先放一放，有时间再来看。

总结一下Hashtable与HashMap的主要不同点：
1.Hashtable出现在Java1.0中，HashMap是随着Java1.2出现的，Hashtable版本要老
1.Hashtable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap，这个区别就像Vector和ArrayList一样 www.2cto.com

2.Hashtable不允许null值(key和value都不可以)，HashMap允许null值(key和value都可以)

3.HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，增加的方式是 old*2

4.哈希值的使用不同，HashTable直接使用对象的hashCode，而HashMap通过hash方法得到hashCode
HashMap应该是设计得更为合理，效率更高(从hash函数中可以看出)的哈希表，除了线程安全之外，Hashtable与HashMao相比，似乎没有优势。
而线程安全可以通过Collections.synchronizedMap 来实现。
HashSet
由于HashSet与HashMap关系非常，这里一并学习了。
HashSet的内部数据结构声明：
private transient HashMap map;
其数据结构居然是一个HashMap。到底是个啥子情况，来一看究竟。
[java]
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
//获得HashSet的迭代器对象
public Iterator iterator() {
//返回KeySet的迭代器
return map.keySet().iterator();
}
//调用map的put方法，键值对的键作为set值，而value值为PRESENT,可知PRESENT为一个静态Object对象
public boolean add(E o) {
return map.put(o, PRESENT)==null;
}
private static final Object PRESENT = new Object();
从这段实现代码中可以看出，HashSet使用HashMap作为其底层数据结构，其值存储于的Key中，而value则都是
一个静态Object对象。HashSet通过HashMap的keySet来遍历元素。接下来一揭keySet的真面目。
一下是HashMap中keySet的实现代码：
[java]
private class KeySet extends AbstractSet {
public Iterator iterator() {
return newKeyIterator();//看来需要看看newKeyIterator();

}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
Iterator newKeyIterator() {
return new KeyIterator();//继续，需要找到KeyIterator()
}
private class KeyIterator extends HashIterator {//继续，找到HashIterator
public K next() {
return nextEntry().getKey();
}
}
//Bingo,抽象类HashIterator，实现了Iterator接口
[java]
private abstract class HashIterator implements Iterator {
Entry next; // next entry to return
int expectedModCount; // For fast-fail
int index;