`
java-mans
  • 浏览: 11340558 次
文章分类
社区版块
存档分类
最新评论

HashMap HashTable和Vector ArrayList有什么区别

 
阅读更多

面试时经常问到一个问题:HashMap与HashTable有什么区别?一般回答是:HashTable实现了同步,HashMap没有。那么何为实现了同步?这需要先从Java同步机制讲起。

我们知道,Java synchronized修饰符有几种用法:
一、对类的静态方法加synchronized,表示对这个类进行加锁,该类的任何静态synchronized方法都必须等待该方法执行结束。
二、对对象的方法加synchronized,表示对这个对象加锁,该对象的任何synchronized方法都必须等待该方法执行结束。
三、对语句块加锁,后跟对象,则对该对象进行的synchronized方法/synchronized语句块都必须等待该语句块执行结束。
HashMap不是线程安全的,假设有多个线程使用同一个HashMap,并且没有显式的对这个对象加锁(如:用方法二),那么对HashMap的访问顺 序将变得不可预知。而HashTable对所有public方法都加上了synchronized修饰,所以在多线程访问HashTable时,他们仍会 互斥访问。
但是Vector和HashTable现在已经过时了。现在的方式是:使用java.util.Collections类的 synchronizedMap/synchronizedList/synchronizedSet方法。这个方法将Map装饰成一个新的 Collection类,这个类的所有方法都是同步的。它的实现方法如下:
public boolean containsKey(Object key) {
synchronized(mutex) {return m.containsKey(key);}
}
这是一个典型的装饰器模式。
面试的时候提到了一个有趣的问题:如果一个对象object引用了集合对象list中的某个元素,那么即使对list加锁,我仍可以通过改变object 的值改变整个list的构成。经过测试,这个现象是存在的,并且无法通过synchronized修饰来避免。因为:Java同步的方法,是对整个对象的 访问加锁,但是不会对对象的字段所引用的对象传递加锁。举例说明,HashMap中通过Entry[] table数组存放Entry,如果我用e1=table[0],那么显然我对HashMap加锁之后,我仍可修改e1的值。这其实是一个并发的隐患。
其实从实现上来说,HashMap比HashTable性能更好。如:HashMap的capacity只会取2^n,用x&capacity-1代替取模。
====================================================================

可能很多人都不知道ArrayList,但是肯定知道Vector,因为Vector比ArrayList早,所以用的
比较多。但是在java1.2之后的Collection框架中,Vector已经被淘汰了,因为要保持兼容型,
这个类会一直存在,但是确被建议不要使用,这就是软件的兼容性,现在想到很多人做的东西
只能在IE6.0上运行,真是气愤。

对于不熟悉Vector的人那最好了,直接用ArrayList就好了,不过习惯使用Vector的最好也转到
ArrayList(虽然Vector可能永远存在JDK中),但是我们没有理由放弃ArrayList使用Vector。

public class Vector extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
可以看出和ArrayList的声明是一样的,这里不考虑它的实现,来看看主要区别:
1.Vector有而ArrayList没有的方法:addElement,copyInto,elementAt,elements,firstElement,firstElement等等,这里就不一一列举,基本上都是多余的方法,而且还使用了Enumeration(一起被淘汰的)。

2.Vector的实现相对ArrayList稍微复杂,Vector功能并不比ArrayList强大,代码量确是两倍。

3.Vector中的大部分方法都是同步方法,不要认为这是它的优点!同步是要付出代价的,要不然在单例模式中很多人都希望用Double-Check Lock呢(虽然不可行)。因为方法都经过同步,效率自然下降不少。

===================================================================

HashTable的应用非常广泛,HashMap是新框架中用来代替HashTable的类,也就是说建议使用HashMap,不要使用HashTable。可能你觉得HashTable很好用,为什么不用呢?这里简单分析他们的区别。

1.HashTable的方法是同步的,HashMap未经同步,所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。

2.HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。

3.HashTable有一个contains(Object value),功能和containsValue(Object value)功能一样。

4.HashTable使用Enumeration,HashMap使用Iterator。

以上只是表面的不同,它们的实现也有很大的不同。

5.HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。

6.哈希值的使用不同,HashTable直接使用对象的hashCode,代码是这样的:
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
而HashMap重新计算hash值,而且用与代替求模:
int hash = hash(k);
int i = indexFor(hash, table.length);

static int hash(Object x) {
  int h = x.hashCode();

  h += ~(h << 9);
  h ^= (h >>> 14);
  h += (h << 4);
  h ^= (h >>> 10);
  return h;
}
static int indexFor(int h, int length) {
  return h & (length-1);
}
以上只是一些比较突出的区别,当然他们的实现上还是有很多不同的,比如
HashMap对null的操作。



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics