• t.me/wxcydzcc

    工作时间

    周一至周五:9:00-21:00

    周末及节日:9:00-18:00

  • 手机版二维码

    随时手机查素材

  • 扫描二维码

    官方微信公众号

Java码农之路 潜水
  • 13发帖数
  • 13主题数
  • 0关注数
  • 0粉丝
开启左侧

HashMap、ConcurrentHashMap数据结构、底层原理、源码分析

[复制链接]
 楼主| Java码农之路 发表于 2022-5-12 21:26:53 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题

  • HashMap
数据结构
JDK1.7
HashMap由数组+单向链表组成,数组是HashMap的主体,链表则是主要为相识决哈希冲突而存在的。
什么是哈希冲突?由于哈希算法被计算的数据是无穷的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。
如果发生hash冲突,HashMap会将同一个桶中的数据以链表的情势存储,但是如果发生hash冲突的概率比较高,就会导致同一个桶中的链表长度过长,遍历效率降低。

                               
登录/注册后可看大图

JDK1.8
HashMap由数组+单向链表/红黑树组成,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜刮时间。

                               
登录/注册后可看大图

转为红黑树后,链表的结构仍然会存在,通过next属性维持,红黑树节点在进行操纵时都会维护链表的结构。
底层原理
怎么实现扩容?(JDK1.7)
hashMap默认的初始容量是16,加载因子是0.75;我们也可以通过构造器 HashMap(int initialCapacity) 来指定初始容量,但需要为2的n次幂,每次扩容都为原来的两倍。
当达到其容量的3/4时,会自动进行扩容,如初始为16,存储第12个元素时,这时候会扩容为32,同时,这时需要创建一张新表,将原表的数据移到新表,可以看resize()和transfer()方法。
View Code
在扩容时,JDK1.8不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的谁人bit是1还是0就好了,是0的话索引没变,是1的话索引酿成“原索引+oldCap”。
怎么实现存取?
key可以存放null,null key总是存放在Entry[]数组的第一个元素,可以看putForNullKey()方法。
HashMap存取时,都需要计算当前key应该对应Entry[]数组哪个元素,通过调用hash()方法,得到hash值,再调用indexFor()得到Entry[]数组下标。
View Code
如果有两个相同的结果,如果hash相同且key对象为同一个,则为同一个对象,直接在该位置替换原对象;否则为不同对象,这时候发生碰撞了,我们通过链表来存储,可以分析createEntry()方法。
View Code
源码分析(JDK1.7)

  • put
View Code

  • get
View Code

  • ConcurrentHashMap(JDK1.7)
数据结构
JDK1.7仍然是数组+单向链表
底层原理
ConcurrentHashMap怎么实现同步的?和HashMap不同之处,ConcurrentHashMap最外层是多个Segment,每个Segment数据结构和HashMap类似,数组+链表组成。每个Segment 都有一个ReentrantLock锁,之间互不影响。
1、HashEntry内部类里的value ,以及链表next都是volatile 修饰的,能保证获取时的可见性。
View Code
2、采用了分段锁技能,具体可以看Segment内部类 ,继承于 ReentrantLock。每当一个线程占用锁访问一个 Segment 时,不会影响到其他的 Segment。
可以看下面的put()方法,put里面第一次尝试加锁,使用自旋获取锁,ReentrantLock提供的tryLock() 方法。
如果如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取,ReentrantLock提供的lock()方法,这种方式获取不到则一直休眠等待,直到能获取乐成。
View Code
  JDK1.8改为了数组+单向链表+红黑树的数据结构,链表长度增加到8时,可能触发变为红黑树,加快查找速度;
  在JDK1.7中Segment在初始化时默认为16,可以设置初始化但后续不能扩容修改,在JDK1.8中取消了Segment,直接用HashEntry,在一些特定情况会扩容。
最后(求关注,别白嫖我)

如果这篇文章对您有所帮助,或者有所启发的话,欢迎关注我的公众号:程序员黑哥

                               
登录/注册后可看大图

精彩评论4

热闹清风S 发表于 2022-5-13 05:20:30 | 显示全部楼层
不白嫖,点赞,评论
晨熹伴读 发表于 2022-5-13 09:10:23 | 显示全部楼层
jdk1.8转红黑树的条件是链表结构大于8,但是如果数组长度小于64优先进行数组扩容,这不专业啊
Marianas 发表于 2022-5-13 10:46:30 | 显示全部楼层
转发了
懂技术的厨师 发表于 2022-5-13 10:55:42 | 显示全部楼层
转发了
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

猜你喜欢
在线客服QQ
2241998733

24x7小时免费咨询

  • 官方在线客服

    在线客服:官方

    点击交谈

    在线客服:良子

    点击交谈

    在线客服:闵月

    点击交谈
  • https://t.me/wxcydzcc

  • 手机扫码查看手机版

    手机查找资源更方便

  • 扫一扫关注官方博客

    cydz.eu.org

Powered by 创意电子 ©2018-现在 专注资源实战分享源码下载站联盟商城繁体中文