HashMap HashTable ConcurrentHashMap实现原理分析

一、HashMap数据结构

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

1、HashMap几乎等同于HashTable,除了HashMap是非synchronized(线性安全)的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而HashTable则不行)。

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

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

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

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

二、注意

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

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

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

三、HashMap HashTable ConcurrentHashMap的数据结构和扩容机制对比

1、Hashtable

底层:数组+链表实现,无论key还是value都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个Hashtable,效率低,ConcurrentHashMap做了相关优化。

扩容:初始计算size为11,扩容newsize=oldsize*2+1。

计算index的方法:index=(hash & 0x7FFFFFFF)%tab.length

哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:

HashMap HashTable ConcurrentHashMap实现原理分析

HashMap HashTable ConcurrentHashMap实现原理分析

从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

/**

* The table, resized as necessary. Length MUST Always be a power of two.

*/

transient Entry[] table;

参考原文

2、HashMap

HashMap在Map.Entry静态内部类实现中存储key-value对。HashMap使用哈希算法,在put和get方法中,它使用hashCode()和equals()方法。当我们通过传递key-value对调用put方法的时候,HashMap使用Key hashCode()和哈希算法来找出存储key-value对的索引。Entry存储在LinkedList中,所以如果存在entry,它使用equals()方法来检查传递的key是否已经存在,如果存在,它会覆盖value,如果不存在,它会创建一个新的entry然后保存。当我们通过传递key调用get方法时,它再次使用hashCode()来找到数组中的索引,然后使用equals()方法找出正确的Entry,然后返回它的值。

底层:数组+链表实现,可以存储null键和null键,线程不安全

初始size为16,扩容:newsize=oldsize*2,size一定为2的n次幂

扩容:针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入

插入元素后才判断该不该扩容,可能扩容无效(插入后如果扩容,如果没有再次插入,就会产生无效扩容)

当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀

计算index方法:index=hash & (tab.length-1)

HashMap的初始值还要考虑加载因子

哈希冲突:若干key的哈希值按数组大小取模后,如果落在同一个数组下标上,将组成一条Entry链,对key的查找需要遍历Entry链上的每一个元素执行equals()比较

加载因子:为了降低哈希冲突的概率,默认当HashMap中的键值对达到数组的75%时,即触发扩容。因此,如果预估容量是100,即需要100/0.75=134的数组大小。

空间换时间:如果希望加快key查找的时间,还可以进一步降低加载因子,加大初始大小,以降低哈希冲突的概率。

HashMap和HashTable都是用hash算法来决定其他元素的存储,因此HashMap和Hashtable的hash表包含如下属性:

容量(capacity):hash表中桶的数量

初始化容量(initial capacity):创建hash表时桶的数量,HashMap允许在构造器中的初始化容量

尺寸(size):当前hash表中记录的数量

负载因子(load fatctor):负载因子等于“size/capacity".负载因子为0,表示空的hash表,0.5表示半满的散列表,依此类推,轻负载的散列表具有冲突少、适宜插入与查询的特点(但是使用Iterator迭代元素比较慢)

3、ConcurrentHashMap

底层:采用分段的数组+链条实现,线程安全

通过把整个Map分为N个segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry 的value变量时volatile的,也能保证读取到最新的值。)

Hashtable的synchronized时针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashmap允许多个修改操作并发进行,其关键在于使用了锁分离技术

有些方法许需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而不是某个段,这需要按顺序锁定所有端,操作完毕后,又按顺序释放所有段的锁

扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容。

HashMap HashTable ConcurrentHashMap实现原理分析

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

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

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

ConcurrentHashmap默认将hash表分为16个桶,诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样,原来只能一个线程进入,现在却能够同时拥有16个写线程执行,并发性能的提升时显而易见的。

原文 

https://segmentfault.com/a/1190000022553860

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » HashMap HashTable ConcurrentHashMap实现原理分析

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址