通俗解释ConcurrentHashMap

  • 2018-04-14
  • 浏览 (199)

先说说HashMap,HashMap是基于hashing(哈希算法)原理,调用者通过put()和get()方法存取对象。当调用者通过put()将键值对传过去,它调用键值对的hashCode方法来计算hashcode值,然后根据hashCode值找到bucket(桶)的位置来存储对象;当调用者通过get()方法获取对象时,通过键对象的equals()方法来找到对应的键值对,然后返回值对象。

HashMap使用链表来解决解决hash“碰撞”问题,当发生“碰撞”时,将对象存储在链表的下一个节点。HashMap在每个链表节点里存储的是键值对象。当两个不同的键对象的hashcode值相同,它们会存储在同一个bucket位置的链表中,获取值对象是会通过键的equals方法来知道键值对:

当两个值对象的hashCode值相等时会发什么?
首先明确一点hashCode值相等并不能判断两个对象相等,如果两个不同的对象hashCode值相等,所以在存储的时候发生了“碰撞”,因为hashCode值相等,所以存储在相同位置的bucket的链表中,最坏的情况所有的对应都存储在同一个位置的bucket中的链表中,这样HashMap就退化成了一个链表,查找数据时查找时间从O(1)到O(n),大大降低了HashMap的性能,在这种情况下你就应该考虑是否继续使用HashMap?

优化上述的办法就是减少“碰撞”,如何减少“碰撞”?
1.String, Interger这样的wrapper类作为HashMap的键;而且String最为常用,因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变
2.使用自定义的对象作为键时遵守重写equals()和hashCode()方法的规则,保证不同的对象不要出现相同的hashCode;

相信每个JAVA程序员都了解HashMap,最大的问题是线程不安全,因为方法中不涉及到同步,也正因为如此,HashMap的效率非常高,在不涉及线程安全的程序中广泛被应用。然而当涉及到多线程作业时,就会出现一些问题。为了解决这些问题JAVA提供了Hashtable,这是一种整体加锁的数据结构,然而效率不敢恭维。这时候就有了ConcurrentHashMap。

一个例子说明三者关系:
前提:某个卫生间共有16个隔间。

HashMap:每个隔间都没锁门,有人想上厕所,管理员指给他一个隔间,里面没人的话正常用,里面有人的话把这个人赶出来然后用。
优点,每个人进来不耽误都能用;缺点,每一个上厕所的人都有被中途赶出来的危险。

Hashtable:在卫生间外面安装一个大门,有人想上厕所,问管理员要一个钥匙进门,把门反锁用,用完后出来,把钥匙交换给管理员。在这个人上厕所期间,其他所有人都必须在外面排号。
优点,每个人都能安心上完厕所;缺点,卫生间外面可能已经出了人命。 =_=

ConcurrentHashMap:在卫生间每个隔间安装门锁,有人想上厕所,管理员指给他一个隔间,进来后这个隔间如果没人在用则直接用,如果有人正在用,则排号。在这期间其他人会按规则分到不同的隔间,重复上述行为。
优点:每个人都能安心上厕所,外面排队的也被均匀分摊。缺点:。。。

ConcurrentHashMap实现的原理
ConcurrentHashMap把Map分成了N个Segment(默认16),其中Segment是线程同步的,相当于分成了N个Hashtable。当实现Put方法时,在key值经过正常的hash后,还要再经过一次segmentForHash算法,用来分配具体防盗哪个Segment。后来的线程如果经过计算也是放在这个Segment下,则需要先获取锁,如果计算得出应该放在其他的Segment,则正常执行,不会影响效率,以此实现线程安全。ConcurrentHashMap使用锁分离技术,只要多个修改操作不发生在同一个Segment上,它们就可以并发进行。
有些方法需要跨段,比如size()和containsValue(),需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁。这里“按顺序”是很重要的,否则极有可能出现死锁,在ConcurrentHashMap内部,段数组是final的,并且其成员变量实际上也是final的,但是,仅仅是将数组声明为final的并不保证数组成员也是final的,这需要实现上的保证。这可以确保不会出现死锁,因为获得锁的顺序是固定的
正文到此结束