皮皮网

【认证系统网站源码】【websc源码是什么】【c 播放视频 源码】hashmap源码put

来源:集分享 源码 时间:2024-12-24 10:35:59

1.idea debug进入HashMap源码时传参不正确?
2.JDK成长记7:3张图搞懂HashMap底层原理!
3.concurrenthashmap1.8源码如何详细解析?

hashmap源码put

idea debug进入HashMap源码时传参不正确?

       我测试了下面的代码:

       分别在这四个位置打了断点以监控程序的运行情况,debug后,进入第一次断点的位置为:

       与题主说的情况一致,而没有进入我的第一个断点进行输出,而后F9:

       发现还是认证系统网站源码在put文件,经多次F9之后,可以看出来,其实java的jvm在启动的时候,在底层也自行调用的put方法,将jvm所需要的一些动态库、jar包put到某个map之中,具体是哪个map看不出来。要等到jvm底层将所有东西准备好后,才进行main函数。

       jvm准备需要put多少次我就不数了,现在我先把put的断点取消,让程序debug到我的第一个断点处:

       这个时候将put方法打上断点,F9发现:

       奇怪的key值增加了,它将我的classes编译目录丢进去了,继续F9,和上一步差不多,再再次F9,终于来了:

       继续F9,终于到达了我的websc源码是什么第二个断点:

       继续F9,这次没有put奇怪的东西了:

       继续:

       最后:

       然后程序退出:

       综上,jvm在启动的时候会在程序背后隐式地将一些配置啊什么的通过put方法放到某些地方,不用关心,你遇到的情况是正常的也是正确的

JDK成长记7:3张图搞懂HashMap底层原理!

       一句话讲, HashMap底层数据结构,JDK1.7数组+单向链表、JDK1.8数组+单向链表+红黑树。

       在看过了ArrayList、LinkedList的底层源码后,相信你对阅读JDK源码已经轻车熟路了。除了List很多时候你使用最多的还有Map和Set。接下来我将用三张图和你一起来探索下HashMap的底层核心原理到底有哪些?

       首先你应该知道HashMap的核心方法之一就是put。我们带着如下几个问题来看下图:

       如上图所示,put方法调用了putVal方法,之后主要脉络是:

       如何计算hash值?

       计算hash值的算法就在第一步,对key值进行hashCode()后,对hashCode的值进行无符号右移位和hashCode值进行了异或操作。为什么这么做呢?其实涉及了很多数学知识,简单的说就是尽可能让高和低位参与运算,可以减少hash值的冲突。

       默认容量和扩容阈值是多少?

       如上图所示,很明显第二步回调用resize方法,获取到默认容量为,c 播放视频 源码这个在源码里是1<<4得到的,1左移4位得到的。之后由于默认扩容因子是0.,所以两者相乘就是扩容大小阈值*0.=。之后就分配了一个大小为的Node[]数组,作为Key-Value对存放的数据结构。

       最后一问题是,如何进行hash寻址的?

       hash寻址其实就在数组中找一个位置的意思。用的算法其实也很简单,就是用数组大小和hash值进行n-1&hash运算,这个操作和对hash取模很类似,只不过这样效率更高而已。hash寻址后,就得到了一个位置,可以把key-value的Node元素放入到之前创建好的Node[]数组中了。

       当你了解了上面的三个原理后,你还需要掌握如下几个问题:

       还是老规矩,看如下图:

       当hash值计算一致,比如当hash值都是时,Key-Value对的Node节点还有一个next指针,会以单链表的形式,将冲突的节点挂在数组同样位置。这就是数据结构中所提到解决hash 的冲突方法之一:单链法。当然还有探测法+rehash法有兴趣的移动端源码使用人可以回顾《数据结构和算法》相关书籍。

       但是当hash冲突严重的时候,单链法会造成原理链接过长,导致HashMap性能下降,因为链表需要逐个遍历性能很差。所以JDK1.8对hash冲突的算法进行了优化。当链表节点数达到8个的时候,会自动转换为红黑树,自平衡的一种二叉树,有很多特点,比如区分红和黑节点等,具体大家可以看小灰算法图解。红黑树的遍历效率是O(logn)肯定比单链表的O(n)要好很多。

       总结一句话就是,hash冲突使用单链表法+红黑树来解决的。

       上面的图,核心脉络是四步,源码具体的就不粘出来了。当put一个之后,map的size达到扩容阈值,就会触发rehash。你可以看到如下具体思路:

       情况1:如果数组位置只有一个值:使用新的容量进行rehash,即e.hash & (newCap - 1)

       情况2:如果数组位置有链表,根据 e.hash & oldCap == 0进行判断,结果为0的根据源码生成帮助使用原位置,否则使用index + oldCap位置,放入元素形成新链表,这里不会和情况1新的容量进行rehash与运算了,index + oldCap这样更省性能。

       情况3:如果数组位置有红黑树,根据split方法,同样根据 e.hash & oldCap == 0进行树节点个数统计,如果个数小于6,将树的结果恢复为普通Node,否则使用index + oldCap,调整红黑树位置,这里不会和新的容量进行rehash与运算了,index + oldCap这样更省性能。

       你有兴趣的话,可以分别画一下这三种情况的图。这里给大家一个图,假设都出发了以上三种情况结果如下所示:

       上面源码核心脉络,3个if主要是校验了一堆,没做什么事情,之后赋值了扩容因子,不传递使用默认值0.,扩容阈值threshold通过tableSizeFor(initialCapacity);进行计算。注意这里只是计算了扩容阈值,没有初始化数组。代码如下:

       竟然不是大小*扩容因子?

       n |= n >>> 1这句话,是在干什么?n |= n >>> 1等价于n = n | n >>>1; 而|表示位运算中的或,n>>>1表示无符号右移1位。遇到这种情况,之前你应该学到了,如果碰见复杂逻辑和算法方法就是画图或者举例子。这里你就可以举个例子:假设现在指定的容量大小是,n=cap-1=,那么计算过程应该如下:

       n是int类型,java中一般是4个字节,位。所以的二进制: 。

       最后n+1=,方法返回,赋值给threshold=。再次注意这里只是计算了扩容阈值,没有初始化数组。

       为什么这么做呢?一句话,为了提高hash寻址和扩容计算的的效率。

       因为无论扩容计算还是寻址计算,都是二进制的位运算,效率很快。另外之前你还记得取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。即 hash%size = hash & (size-1)。这个前提条件是除数是2的幂次方。

       你可以再回顾下resize代码,看看指定了map容量,第一次put会发生什么。会将扩容阈值threshold,这样在第一次put的时候就会调用newCap = oldThr;使得创建一个容量为threshold的数组,之后从而会计算新的扩容阈值newThr为newCap*0.=*0.=。也就是说map到了个元素就会进行扩容。

       除了今天知识,技能的成长,给大家带来一个金句甜点,结束我今天的分享:坚持的三个秘诀之一目标化。

       坚持的秘诀除了上一节提到的视觉化,第二个秘诀就是目标化。顾名思义,就是需要给自己定立一个目标。这里要提到的是你的目标不要定的太高了。就比如你想要增加肌肉,给自己定了一个目标,每天5组,每次个俯卧撑,你看到自己胖的身形或者海报,很有刺激,结果开始前两天非常厉害,干劲十足,特别奥利给。但是第三天,你想到要个俯卧撑,你就不想起床,就算起来,可能也会把自己撅死过去......其实你的目标不要一下子定的太大,要从微习惯开始,比如我媳妇从来没有做过俯卧撑,就让她每天从1个开始,不能多,我就怕她收不住,做多了。一开始其实从习惯开始,先变成习惯,再开始慢慢加量。量太大养不成习惯,量小才能养成习惯。很容易做到才能养成,你想想是不是这个道理?

       所以,坚持的第二个秘诀就是定一个目标,可以通过小量目标,养成微习惯。比如每天你可以读五分钟书或者5分钟成长记,不要多,我想超过你也会睡着了的.....

       最后,大家可以在阅读完源码后,在茶余饭后的时候问问同事或同学,你也可以分享下,讲给他听听。

concurrenthashmap1.8源码如何详细解析?

       ConcurrentHashMap在JDK1.8的线程安全机制基于CAS+synchronized实现,而非早期版本的分段锁。

       在JDK1.7版本中,ConcurrentHashMap采用分段锁机制,包含一个Segment数组,每个Segment继承自ReentrantLock,并包含HashEntry数组,每个HashEntry相当于链表节点,用于存储key、value。默认支持个线程并发,每个Segment独立,互不影响。

       对于put流程,与普通HashMap相似,首先定位至特定的Segment,然后使用ReentrantLock进行操作,后续过程与HashMap基本相同。

       get流程简单,通过hash值定位至segment,再遍历链表找到对应元素。需要注意的是,value是volatile的,因此get操作无需加锁。

       在JDK1.8版本中,线程安全的关键在于优化了put流程。首先计算hash值,遍历node数组。若位置为空,则通过CAS+自旋方式初始化。

       若数组位置为空,尝试使用CAS自旋写入数据;若hash值为MOVED,表示需执行扩容操作;若满足上述条件均不成立,则使用synchronized块写入数据,同时判断链表或转换为红黑树进行插入。链表操作与HashMap相同,链表长度超过8时转换为红黑树。

       get查询流程与HashMap基本一致,通过key计算位置,若table对应位置的key相同则返回结果;如为红黑树结构,则按照红黑树规则获取;否则遍历链表获取数据。