专栏首页EffectiveCodingJava Concurrent Map

Java Concurrent Map

前言

HashMap是我们生产过程中使用较多的一个数据结构,平时非并发场景使用的HashMap,并发场景下使用的HashTable、ConcurrentHashMap。

表面的API看上去都基本是相同的,但不同的Map实现却差异较大,比如说1.6、1.17、1.8及以上版本中的HashMap、ConcurrentHashMap、远古的HashTable。在进行下面介绍之前默认大家已经理解红黑树、Hash计算等

按照顺序介绍:

Java 1.6

HashMap

默认负载因子为0.75,默认容量为16。也就是到达16*0.75 时会出发resize操作。基于数组和链表实现,这算是HashMap的一种教科书里的实现结构了(通常大学课本中特别常见),当key为null 时会添加元素至0的位置。

缺点:new HashMap时就开辟内存空间,在正式使用之前这段时间,造成了一定的内存浪费。下面是HashMap的一种实现结构

HashTable

hashTbles的实现基本可以以HashMap结构为基础,要说差异的话就是每个方法都变成了sychronized,这种直接在每个方法上直接sychronized,怕不是当时当时临时上的策略了,Collections.synchronizedMap()也是同样的粗暴。自从ConcurrentHashMap出现后已经几乎没有使用的了。

ConcurrentHashMap

1.6中的HashMap采用的是分段加锁的方式,可以简单理解为使用使用分段锁直接锁住某些段,然后减小争用的可能性(比HashTable稍微好一些),产生争用时取锁(通过reentrantlock保证并发的安全,直接继承的),来保证安全性。下面是大致的一种结构,锁的是Segment。有一个concurrency level 默认是16,也就是segment的数量,这个不可以扩容。负载因子同样是0.75,然后容量指定时是平均分配给每个桶的。

Java 1.7

HashTable的实现去查了下源码,一直到Java 10 都基本保持原始的样子。应该是停止更新了,所以以1.7 为准。

HashMap 相对于1.6中的,解决了上文提到的资源浪费问题,实现了简单的懒加载。

ConcurrentHashMap 相对于1.6 中基本没有发生变化。

Java 8

真正的变化其实发生在1.8中

HashMap:

优化点:解决碰撞过多的问题,理想情况下6和7中的实现碰撞是较少的,在底层结构看起来也就是链表的长度较短。但现实使用中并没法保证是在理想情况下或正常情况下工作的,所以经常出现链表长度很长,导致性能逐渐下降,并且有的还没开始使用,从一定角度上来说属于资源的分配不均,存在一定的浪费。针对这个问题,1.8中设定了一个阀值(8),当链表长度大于8时使用红黑树进行替换。也就是使用红黑树的方式减小碰撞所带来的代价(O(n) 到 O(logn))

然后Hash算法更改为:XORs,扩容算法更改为:ewThr<<1,然后懒加载的特性仍然保留,第一次put的时候才真正的new。

ConcurrentHashMap:

key&value都不允许为空,从1.8开始出现前置检查,并且舍弃concurrencylevel 改用动态分片。并且,这次可不是挤牙膏式更新,舍弃了之前Segment分段锁式设计,底层采用数组+链表+红黑树结构实现,采用CAS+sychronized实现并发安全。(结构基本同上面java 8中的HashMap)。

下面是putVal中的CAS+Sychronized的使用,putval也是整个ConcurrentHashMap中比较核心的,推荐详细去看一下,因为篇幅,只说里面的一两点。

具体的hash算法:

再然后取元素时,利用了类似于volatile特性的UnSafe.getObjectVolatile(),保证取到的为最新值。

1.8中的扩容方式:

当table的数量达到阀值sizeCtl时,会构建一个nextTable(大小为之前的两倍),然后把table的数据复制到nextTable中(不断的遍历原有的完成复制)。其中sizeCtl利用CAS(UnSafe.compareAndSetInt() 完成操作)可以简单看一下。1.8之前的跟之后的ConcurrentHashMap 这个过程是有所差异的,因为结构不同的关系,1.7及之前的扩容时不需要对整个map做rehash只需要对于segment做rehash就OK了

line:2432

private final voidtransfer(Node<K,V>[]tab,Node<K,V>[]nextTab) {

说一个经典的问题:

为什么要使用ConcurrentHashMap,单纯使用HashMap存在什么问题。

看上去ConcurrentHashMap相对于HashMap 也就是在一个数据操作的环节增加了锁操作变为CAS操作。这么做的意义是什么呢?

因为HashMap在并发执行put操作时会引起死循环,多线程可能会导致HashMap的Entry链表形成环形数据结构,查找时会陷入死循环。(两个线程同时扩容相撞了,导致环形链表的产生,所以悲剧就出现了——Infinite Loop)

关于rehash:

Java 6 存在rehash

Java 7 存在rehash

Java 8 可能会发生rehash,在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看原来的hash值新增的那个bit是1还是0,是0的话索引没变,是1的话索引变成“原索引+oldCap”

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis 持久化之AOF持久化&混合持久化

    RDB(snapshotting) 是一种内存快照的方式进行持久化,AOF(append-only-file)是通过追加写入命令的方式进行持久化,混合持久化是指...

    邹志全
  • Go 内存管理 -- 垃圾回收

    go作为一个非常年轻的语言,吸取了各个语言的优点,比如说Java中优秀的垃圾回收,来释放程序员一部分精力。 本篇要说的就是垃圾回收,常见的垃圾回收算法有标记-...

    邹志全
  • JVM 《一 JVM 中的垃圾回收》

    当我们了解其中的内存之后,我们可能会有一点想法,我们的对象、相关类信息是存放在Java堆、方法区之中的。那我们的程序正在不断的new 对象、不断的loading...

    邹志全
  • 深入理解HashMap和TreeMap的区别

    HashMap和TreeMap是Map家族中非常常用的两个类,两个类在使用上和本质上有什么区别呢?本文将从这两个方面进行深入的探讨,希望能揭露其本质。

    程序那些事
  • 还看不懂JDK7 HashMap环的产生原理你来打我

    JDK7中当我们用头插法 对旧table数据重定位到新table的时候我们知道是会行程环的,环产生的核心函数transfer如下,其中重点关注部分以标出。

    sowhat1412
  • 解释一下 HashMap 的工作原理

    HashMap 是基于散列表的数据结构。所谓散列表,它通过键值对的方式存储数据,把 key 通过散列算法计算出一个存储地址,将 value 放入这个地址中。散列...

    水货程序员
  • 有趣的条漫版 HashMap,25岁大爷都能看懂

    因为写文章的过程中画了不少的图,所以,我想,能不能用长图的形式展现一次呢,结果图片熬夜做了半天,最后出来的效果不是很好,哎,审美缺失吧。之后会有详细的文字源码解...

    古时的风筝
  • 10个经典的Java面试题集合

    概述:还在做无准备的面试吗?还在为找不到Java的面试题而苦恼吗?那么你就一定不能错过以下小编为你量身打造的Java面试题集合了!让我们一起来看看 这里有10个...

    非著名程序员
  • 10 个经典的 Java 集合面试题,看你能否答得上来?

    这里有10个经典的Java面试题,也为大家列出了答案。这是Java开发人员面试经常容易遇到的问题,相信你了解和掌握之后一定会有所提高。

    Java技术栈
  • PySpark ML——分布式机器学习库

    继续PySpark学习之路,本篇开启机器学习子模块的介绍,不会更多关注机器学习算法原理,仅对ML库的基本框架和理念加以介绍。最后用一个小例子实战对比下sklea...

    luanhz

扫码关注云+社区

领取腾讯云代金券