menu ChaYedan
HashMap和ConcurrentHashMap
2979 浏览 | 2020-06-03 | 阅读时间: 约 4 分钟 | 分类: Java | 标签: Java
请注意,本文编写于 907 天前,最后修改于 902 天前,其中某些信息可能已经过时。

总述

HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象

最重要的就是利用散列桶的空间,最好每一个位置都刚好有一个节点。且几乎不产生链表。那么这样就必须有一个好的计算位置的方法,也就是常说的散列函数(哈希函数)。那么回到刚才的问题,要让每个节点都刚好有节点,那么首先想到的就是对Key计算出的hashcode取桶大小的模,但是取模的消耗是比较大的,所以没有采用这种方法。(主要是因为扩容时,会重新计算Key对应的位置,如果用取模,效率会低到不忍直视)

第二个重要的点就是解决哈希冲突的问题,因为比如像"abc"和"cba"这样的字符串,计算出的hashcode是一样的,那么就会存在在存值时产生哈希冲突。产生哈希冲突影响的就是查找的效率。在JDK1.7之前,有冲突就直接在对应冲突的位置建立链表,但一旦同样的位置冲突多了,那么链表就会很长,那么查找的效率就会非常低,所以在JDK1.8就采用了链表长度大于等于8时,就开始采用红黑树的结构。

散列函数

为了完成刚才我们所说的充分利用桶空间,最好每个位置都存在节点,取模确实是一个好想法,差就差在效率最低。位运算的效率远远高出取模的效率,所以用位运算来代替模运算。

在length = 2的指数次幂的时候,hash%length = h & (length-1)。

加载因子0.75

主要是平衡空间和时间。如果太大,会导致哈希碰撞增大。例如设置为1,那么要填满才会扩容,会大幅增大碰撞概率,比如说剩15的位置为空,这时第十六个元素填充进来,经过取模填上15这个位置的概率是十六分之一,那被碰撞的概率就是十六分之十五,如果前面就是非常完美的分布(即一空一个),这时候就会大概率增加一个链表节点。如果前面不是完美的分布,如果发生碰撞,情况就会更加糟糕。

到8转换为红黑树

这是一个概率学的问题,这个问题具体是属于泊松分布,根据官方的计算,在装填因子为0.75时(别忘了扩容时会重新计算位置更改分布),碰撞产生的链表长度大于8的概率为0.00000006,几乎为一个不可能事件。

1.7形成环的原因

出错原因:多线程情况下,线程一将链表反转后,使得原来的节点2的next不为空了。

然后因为线程二执行同样的代码

第二轮的末尾,也就是e=next那一步,因为原来节点2的next是null,所以完成反转后就停止循环了,但是现在因为线程1将节点反转了,导致节点二的next有值了,所以线程2会死循环下去。

1.8解决方案

4个指针将链表分为分为高位和低位,与原来的HashMap长度做与运算,分成两部分,得到的结果为0的元素就原地不动,得到结果为1的元素就直接原地址+原长度到新的位置(比如原来是 1,原来的长度为16,现在就将高位的部分移动到17的位置)

ConcurrentHashMap

是由 Segment 数组、HashEntry 组成,和 HashMap 一样,仍然是数组加链表。

  1. Segment是ConcurrentHashMap中的内部类,它就是ConcurrentHashMap中的锁分段对应的存储结构。ConcurrentHashMap与Segment是组合关系,一个ConcurrentHashMap对象包含若干个Segment对象。在代码中表现为ConcurrentHashMap类中存在Segment数组成员。
  2. Segment类继承于ReentrantLock类,所以Segment本质上是一个可重入的互斥锁。

ConcurrentHashMap采用的是分段锁策略,其主干就是Segment 数组,Segment继承自ReentrantLock类,是一种可重入的互斥锁,一个Segment就是一个子哈希表,Segement里默认维护了一个hashentry数组(hashentry数组中的hashentry的具体数量,是由ConcurrentHashMap中的构造函数中传参initialCapacity和concurrencyLevel相除得到,默认两个都是16,所以默认维护一个hashentry),所以在并发的环境下,只有当访问相同的hashentry数组时,才会上锁,其余的时候就不会有上锁的情况出现。

1.8的改进

上面是1.7的大概思路。1.7 已经解决了并发问题,并且能支持 N 个 Segment 这么多次数的并发,但依然存在 HashMap 在 1.7 版本中的问题。那就是查询遍历链表效率太低。1.8抛弃了原有的 Segment 分段锁,而采用了 CAS + synchronized 来保证并发安全性。

并且也采用了数组加链表加红黑树的实现,并且在链表长度大于等于8时,就开始采用红黑树的结构。

CAS详解:https://www.cnblogs.com/barrywxx/p/10700311.html

CAS的ABA问题:加版本号控制

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (共 2 条评论)

    114514
    2020-06-07 16:37
    1.8中Concurrenthashmap改用了数组+链表+红黑树
      2020-06-07 18:53
      @114514是写掉了,感谢提醒