HashMap和Hashtable的比较

这两个类是java中进行key-value存储、查询的常用类，如果我们学习过哈希算法就会知道key-value查询的效率依赖于如何存储，换句话说，如果存的好，拿出来就容易，存的不好，拿出来就不方便。两个类有很多相似之处，他们之间的关系和区别到底如何，先看看它们两个当中最核心方法put的实现。

1.Hashtable的put方法的实现，以下代码做了注释：

/**
 * Hashtable的put方法，是同步的，可以在多线程环境下确保原子性执行，index值的计算过程非常简单，
 * 但是运气不好的话有可能得到大量重复的index，大量的key-value存储在相同的Entry链表中，从而降
 * 低了get操作的执行效率
 */
public synchronized V put(K key, V value) {
	// Make sure the value is not null
	if (value == null) {
	    throw new NullPointerException();
	}

	// Makes sure the key is not already in the hashtable.
	Entry tab[] = table;
	
	//得到哈希值
	int hash = key.hashCode();
	
	/* 通过哈希值获取index */
	int index = (hash & 0x7FFFFFFF) % tab.length;
	
	/* 遍历Entry链表 */
	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
		/* 注意这里不仅要比较哈希值还要比较key对象 */
	    if ((e.hash == hash) && e.key.equals(key)) {
			V old = e.value;
			e.value = value;
			return old;
		}
	}
	
	modCount++;
	
	/* 如果装不下了，就扩充容量，重新获取index */
	if (count >= threshold) {
	    // Rehash the table if the threshold is exceeded
	    rehash();
		
		tab = table;
		index = (hash & 0x7FFFFFFF) % tab.length;
	}

	/* 如果根据哈希值没找到对应的entry对象，在entry链表末尾加入新的entr对象 */
	Entry<K,V> e = tab[index];
	tab[index] = new Entry<K,V>(hash, key, value, e);
	count++;
	return null;
}

 

2.HashMap的put方法及其使用的相关方法实现代码，以下做了注释：

/**
 * 使用位移算法对哈希码给予补充，防止出现大量的0、1重复，这样得到的index重复的几率就很大，经过补充位移运算后，
 * 可以使哈希码的0、1分布更加均匀，再经过indexFor（）方法计算得到的index重复的几率就小很多，这就是HashMap散列
 * 算法相比于Hashtable的哈希算法更优化的关键所在。
 * 需要注意的是key=null时，index=0。
 */
static int hash(int h) {
	h ^= (h >>> 20) ^ (h >>> 12);
	return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
 * 通过哈希值和table的最大存储位置的位与运算，得到一个小于length的值作为index。
 */
static int indexFor(int h, int length) {
	return h & (length-1);
}
/**
 * HashMap的put方法
 */
public V put(K key, V value) {
	if (key == null)
		return putForNullKey(value);
	
	//得到哈希值，hashCode()方法为native方法，估计是C、C++或者汇编实现的
	int hash = hash(key.hashCode());
	
	//得到index
	int i = indexFor(hash, table.length);
	
	/* 得到index，遍历table[index]寻找key相同的对象，如果不存在增加一个Entry对象 */
	for (Entry<K,V> e = table[i]; e != null; e = e.next) {
		Object k;
		
		/* 注意这里不仅要比较哈希值还要比较key对象，找到后覆盖原来的值 */
		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
			V oldValue = e.value;
			e.value = value;
			e.recordAccess(this);
			return oldValue;
		}
	}
	
	/* 如果根据哈希值没找到对应的entry对象，在entry链表末尾加入新的entr对象 */
	modCount++;
	addEntry(hash, key, value, i);
	return null;
}

 3.下面比较一下两个类到底有什么异同。
相同点：
（1）这两个类存储key-value对象的数据结构基本相同，都是将
key-value封装在entry对象中，entry中有指向下一个entry对象的引用（Entry next），这样就可以形成一个链表，而在类的主体中保存了一个Entry链表的数组（Entry[] table)来存储Entry对象，具体存储结构如下图：

 

（2）取数据的方法基本相同，在哈希算法的概念里面，每一个链表应该称之为一个"桶"，每个桶都有一个编号
（也就是index），通过编号我们可以很快的从桶里面取出东西，但是如果桶里面装的东西多了，那就要一个一个的找，会比较慢，所以我们要让东西放的均匀一些，让我们每次取东西都不至于太慢。因此，取东西效率取决于我们当初如何存东西，在这一点上两个类的思想是一样的。

不同点；
通过比较两个类put方法的实现，我们会发现它们之间的区别：
（1）Hashtable的put方法有synchronized修饰，说明该put方法实现了同步，达到了一定的线程安全级别，
而HashMap的put方式没有实现同步，是非线程安全类，当然，单线程情况下，HashMap无疑拥有更好的执行效率而不用去考虑线程安全问题。
（2）通过key获取index的过程有很大差别，其实这是两个类最重要的区别，在代码的注释里面已经给出了分析，HashMap的实现方式无疑使一种更优的实现，所以我们在单线程的环境下，或者在某些安全的多线程环境下都应该优先使用HashMap。当然，并发环境下，我们还可以考虑使用NIO包里面的类，这个问题将在其他的文章里讨论。