HashMap HashTable和ConcurrentHashMap的区别-JAVA成长之路

HashMap和Hashtable的区别

HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。

HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。

HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。

另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。

由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。

HashMap不能保证随着时间的推移Map中的元素次序是不变的。

要注意的一些重要术语:

1) sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁,其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。

2) Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator,然后其它的线程试图“结构上”更改集合对象,将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的,因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改,再调用set()方法,将会抛出IllegalArgumentException异常。

3) 结构上的更改指的是删除或者插入一个元素,这样会影响到map的结构。

我们能否让HashMap同步?

HashMap可以通过下面的语句进行同步:

Map m = Collections.synchronizeMap(hashMap);

结论

Hashtable和HashMap有几个主要的不同:线程安全以及速度。仅在你需要完全的线程安全的时候使用Hashtable,而如果你使用Java 5或以上的话,请使用ConcurrentHashMap吧。

HashMap和ConcurrentHashMap分享

大家一看到这两个类就能想到HashMap不是线程安全的,ConcurrentHashMap是线程安全的。除了这些,还知道什么呢?

先看一下简单的类图:

从类图中可以看出来在存储结构中ConcurrentHashMap比HashMap多出了一个类Segment,而Segment是一个可重入锁。

ConcurrentHashMap是使用了锁分段技术技术来保证线程安全的。

锁分段技术:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

属性说明:

我们会发现HashMap和Segment里的属性值基本是一样的,因为Segment的本质上就是一个加锁的HashMap,下面是每个属性的意义:

table:数据存储区

size,count: 已存数据的大小

threshold:table需要扩容的临界值,等于table的大小*loadFactor

loadFactor: 装载因子

modCount: table结构别修改的次数

hash算法和table数组长度:

仔细阅读HashMap的构造方法的话,会发现他做了一个操作保证table数组的大小是2的n次方。

如果使用new HashMap(10)新建一个HashMap,你会发现这个HashMap中table数组实际的大小是16,并不是10.

为什么要这么做呢?这就要从HashMap里的hash和indexFor方法开始说了。

staticint hash(int h) {

// 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);

}

/**

* Returns index for hash code h.

*/

staticint indexFor(int h,int length) {

return h & (length-1);

}

int hash = hash(key.hashCode());

int i = indexFor(hash, table.length);

HashMap里的put和get方法都使用了这两个方法将key散列到table数组上去。

indexFor方法是通过hash值和table数组的长度-1进行于操作,来确定具体的位置。

为什么要减1呢?因为数组的长度是2的n次方,减1以后就变成低位的二进制码都是1,和hash值做与运算的话,就能得到一个小于数组长度的数了。

那为什么对hashCode还要做一次hash操作呢?因为如果不做hash操作的话,只有低位的值参与了hash的运算,而高位的值没有参加运算。hash方法是让高位的数字也参加hash运算。

假如:数组的长度是16 我们会发现hashcode为5和53的散列到同一个位置.

hashcode:53 00000000 00000000 00000000 00110101

hashcode:5 00000000 00000000 00000000 00000101

length-1:15 00000000 00000000 00000000 00001111

只要hashcode值的最后4位是一样的,那么他们就会散列到同一个位置。

hash方法是通过一些位运算符,让高位的数值也尽可能的参加到运算中,让它尽可能的散列到table数组上,减少hash冲突。

ConcurrentHashMap的初始化:

仔细阅读ConcurrentHashMap的构造方法的话,会发现是由initialCapacity,loadFactor, concurrencyLevel几个参数来初始化segments数组的。

segmentShift和segmentMask是在定位segment时的哈希算法里需要使用的,让其能够尽可能的散列开。

initialCapacity:ConcurrentHashMap的初始大小

loadFactor:装载因子

concurrencyLevel:预想的并发级别,为了能够更好的hash,也保证了concurrencyLevel的值是2的n次方

segements数组的大小为concurrencyLevel,每个Segement内table的大小为initialCapacity/ concurrencyLevel

ConcurrentHashMap的put和get

int hash = hash(key.hashCode());

return segmentFor(hash).get(key, hash);

可以发现ConcurrentHashMap通过一次hash,两次定位来找到具体的值的。

先通过segmentFor方法定位到具体的Segment,再在Segment内部定位到具体的HashEntry,而第二次在Segment内部定位的时候是加锁的。

ConcurrentHashMap的hash算法比HashMap的hash算法更复杂,应该是想让他能够更好的散列到数组上,减少hash冲突。

HashMap和Segment里modCount的区别:

modCount都是记录table结构被修改的次数,但是对这个次数的处理上,HashMap和Segment是不一样的。

HashMap在遍历数据的时候,会判断modCount是否被修改了,如果被修改的话会抛出ConcurrentModificationException异常。

Segment的modCount在ConcurrentHashMap的containsValue、isEmpty、size方法中用到,ConcurrentHashMap先在不加锁的情况下去做这些计算,如果发现有Segment的modCount被修改了,会再重新获取锁计算。

HashMap和ConcurrentHashMap的区别:

如果仔细阅读他们的源码,就会发现HashMap是允许插入key和value是null的数据的,而ConcurrentHashMap是不允许key和value是null的。这个是为什么呢?ConcurrentHashMap的作者是这么说的:

The main reason that nulls aren't allowed in ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps) is that ambiguities that may be just barely tolerable in non-concurrent maps can't be accommodated. The main one is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs the key isn't mapped. In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.

为什么重写了equals方法就必须重写hashCode方法呢?

绝大多数人都知道如果要把一个对象当作key使用的话,就需要重写equals方法。重写了equals方法的话,就必须重写hashCode方法,否则会出现不正确的结果。那么为什么不重写hashCode方法就会出现不正确结果了呢?这个问题只要仔细阅读一下HashMap的put方法,看看它是如何确定一个key是否已存在的就明白了。关键代码:

int hash = hash(key.hashCode());

int i = indexFor(hash, table.length);

for (Entry e = table[i]; e !=null; e = e.next) {

Object k;

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

首先通过key的hashCode来确定具体散列到table的位置,如果这个位置已经有值的话,再通过equals方法判断key是否相等。

如果只重写equals方法而不重写hashCode方法的话,即使这两个对象通过equals方法判断是相等的,但是因为没有重写hashCode方法,他们的hashCode是不一样的,这样就会被散列到不同的位置去,变成错误的结果了。所以hashCode和equals方法必须一起重写。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200521A05RT500?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券