欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HashMap和Hashtable的比较 博客分类: Java基础 HashMapHashtable散列哈希java 

程序员文章站 2024-03-18 09:28:28
...

这两个类是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对象,具体存储结构如下图:

HashMap和Hashtable的比较
            
    
    博客分类: Java基础 HashMapHashtable散列哈希java 
 
(2)取数据的方法基本相同,在哈希算法的概念里面,每一个链表应该称之为一个"桶",每个桶都有一个编号
(也就是index),通过编号我们可以很快的从桶里面取出东西,但是如果桶里面装的东西多了,那就要一个一个的找,会比较慢,所以我们要让东西放的均匀一些,让我们每次取东西都不至于太慢。因此,取东西效率取决于我们当初如何存东西,在这一点上两个类的思想是一样的。
不同点;
通过比较两个类put方法的实现,我们会发现它们之间的区别:
(1)Hashtable的put方法有synchronized修饰,说明该put方法实现了同步,达到了一定的线程安全级别,
而HashMap的put方式没有实现同步,是非线程安全类,当然,单线程情况下,HashMap无疑拥有更好的执行效率而不用去考虑线程安全问题。
(2)通过key获取index的过程有很大差别,其实这是两个类最重要的区别,在代码的注释里面已经给出了分析,HashMap的实现方式无疑使一种更优的实现,所以我们在单线程的环境下,或者在某些安全的多线程环境下都应该优先使用HashMap。当然,并发环境下,我们还可以考虑使用NIO包里面的类,这个问题将在其他的文章里讨论。
  • HashMap和Hashtable的比较
            
    
    博客分类: Java基础 HashMapHashtable散列哈希java 
  • 大小: 11 KB