【宇阳源码】【浙江广电小程序源码查询】【抖音直播源码云蹦迪】put源码讲解

来源:stl源码分析视频侯捷

1.JDK成长记7:3张搞懂HashMap底层原理!码讲
2.为什么HashMap是码讲线程不安全的
3.BoltDB源码解析(七)Put和Delete操作
4.FREE SOLO - 自己动手实现Raft - 16 - leveldb源码分析与调试-2
5.HashMap实现原理一步一步分析(1-put方法源码整体过程)

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方法,获取到默认容量为,这个在源码里是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分钟成长记,不要多,我想超过你也会睡着了的.....

       最后,大家可以在阅读完源码后,如何查询奶粉防伪溯源码在茶余饭后的时候问问同事或同学,你也可以分享下,讲给他听听。

为什么HashMap是线程不安全的

       这是《Java程序员进阶之路》专栏的第篇,我们来聊聊为什么HashMap是线程不安全的。

、多线程下扩容会死循环

       众所周知,HashMap是通过拉链法来解决哈希冲突的,也就是当哈希冲突时,会将相同哈希值的键值对通过链表的形式存放起来。

       JDK7时,采用的是头部插入的方式来存放链表的,也就是下一个冲突的键值对会放在上一个键值对的前面(同一位置上的新元素被放在链表的头部)。扩容的时候就有可能导致出现环形链表,造成死循环。

       resize方法的源码:

//newCapacity为新的容量voidresize(intnewCapacity){ //小数组,临时过度下Entry[]oldTable=table;//扩容前的容量intoldCapacity=oldTable.length;//MAXIMUM_CAPACITY为最大容量,2的次方=1<<if(oldCapacity==MAXIMUM_CAPACITY){ //容量调整为Integer的最大值0x7fffffff(十六进制)=2的次方-1threshold=Integer.MAX_VALUE;return;}//初始化一个新的数组(大容量)Entry[]newTable=newEntry[newCapacity];//把小数组的元素转移到大数组中transfer(newTable,initHashSeedAsNeeded(newCapacity));//引用新的大数组table=newTable;//重新计算阈值threshold=(int)Math.min(newCapacity*loadFactor,MAXIMUM_CAPACITY+1);}

       transfer方法用来转移,将小数组的元素拷贝到新的数组中。

voidtransfer(Entry[]newTable,booleanrehash){ //新的容量intnewCapacity=newTable.length;//遍历小数组for(Entry<K,V>e:table){ while(null!=e){ //拉链法,相同key上的不同值Entry<K,V>next=e.next;//是否需要重新计算hashif(rehash){ e.hash=null==e.key?0:hash(e.key);}//根据大数组的容量,和键的hash计算元素在数组中的下标inti=indexFor(e.hash,newCapacity);//同一位置上的新元素被放在链表的头部e.next=newTable[i];//放在新的数组上newTable[i]=e;//链表上的下一个元素e=next;}}}

       注意e.next=newTable[i]和newTable[i]=e这两行代码,就会将同一位置上的新元素被放在链表的头部。

       扩容前的样子假如是下面这样子。

       那么正常扩容后就是下面这样子。

       假设现在有两个线程同时进行扩容,线程A在执行到newTable[i]=e;被挂起,此时线程A中:e=3、next=7、e.next=null

       线程B开始执行,并且完成了数据转移。

       此时,7的next为3,3的next为null。

       随后线程A获得CPU时间片继续执行newTable[i]=e,将3放入新数组对应的位置,执行完此轮循环后线程A的情况如下:

       执行下一轮循环,此时e=7,原本线程A中7的next为5,但由于table是线程A和线程B共享的,而线程B顺利执行完后,7的next变成了3,那么此时线程A中,7的next也为3了。

       采用头部插入的方式,变成了下面这样子:

       好像也没什么问题,此时next=3,e=3。

       进行下一轮循环,但此时,由于线程B将3的next变为了null,所以此轮循环应该是最后一轮了。

       接下来当执行完e.next=newTable[i]即3.next=7后,3和7之间就相互链接了,执行完newTable[i]=e后,安卓触摸测试源码下载3被头插法重新插入到链表中,执行结果如下图所示:

       套娃开始,元素5也就成了弃婴,惨~~~

       不过,JDK8时已经修复了这个问题,扩容时会保持链表原来的顺序,参照HashMap扩容机制的这一篇。

、多线程下put会导致元素丢失

       正常情况下,当发生哈希冲突时,HashMap是这样的:

       但多线程同时执行put操作时,如果计算出来的索引位置是相同的,那会造成前一个key被后一个key覆盖,从而导致元素的丢失。

       put的源码:

finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){ Node<K,V>[]tab;Node<K,V>p;intn,i;//步骤①:tab为空则创建if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;//步骤②:计算index,并对null做处理if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);else{ Node<K,V>e;Kk;//步骤③:节点key存在,直接覆盖valueif(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;//步骤④:判断该链为红黑树elseif(pinstanceofTreeNode)e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);//步骤⑤:该链为链表else{ for(intbinCount=0;;++binCount){ if((e=p.next)==null){ p.next=newNode(hash,key,value,null);//链表长度大于8转换为红黑树进行处理if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}//key已经存在直接覆盖valueif(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}//步骤⑥、直接覆盖if(e!=null){ //existingmappingforkeyVoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;//步骤⑦:超过最大容量就扩容if(++size>threshold)resize();afterNodeInsertion(evict);returnnull;}

       问题发生在步骤②这里:

if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);

       两个线程都执行了if语句,假设线程A先执行了tab[i]=newNode(hash,key,value,null),那table是这样的:

       接着,线程B执行了tab[i]=newNode(hash,key,value,null),那table是这样的:

       3被干掉了。

、put和get并发时会导致get到null

       线程A执行put时,因为元素个数超出阈值而出现扩容,线程B此时执行get,有可能导致这个问题。

       注意来看resize源码:

finalNode<K,V>[]resize(){ Node<K,V>[]oldTab=table;intoldCap=(oldTab==null)?0:oldTab.length;intoldThr=threshold;intnewCap,newThr=0;if(oldCap>0){ //超过最大值就不再扩充了,就只好随你碰撞去吧if(oldCap>=MAXIMUM_CAPACITY){ threshold=Integer.MAX_VALUE;returnoldTab;}//没超过最大值,就扩充为原来的2倍elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;//doublethreshold}elseif(oldThr>0)//initialcapacitywasplacedinthresholdnewCap=oldThr;else{ //zeroinitialthresholdsignifiesusingdefaultsnewCap=DEFAULT_INITIAL_CAPACITY;newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}//计算新的resize上限if(newThr==0){ floatft=(float)newCap*loadFactor;newThr=(newCap<MAXIMUM_CAPACITY&&ft<(float)MAXIMUM_CAPACITY?(int)ft:Integer.MAX_VALUE);}threshold=newThr;@SuppressWarnings({ "rawtypes","unchecked"})Node<K,V>[]newTab=(Node<K,V>[])newNode[newCap];table=newTab;}

       线程A执行完table=newTab之后,线程B中的table此时也发生了变化,此时去get的时候当然会get到null了,因为元素还没有转移。

       为了便于大家更系统化地学习Java,二哥已经将《Java程序员进阶之路》专栏开源到GitHub上了,大家只需轻轻地star一下,就可以和所有的小伙伴一起打怪升级了。

       GitHub地址:/itwanger/toBeBetterJavaer

BoltDB源码解析(七)Put和Delete操作

       Put和Delete的实现

       上一篇文章我们了解了BoltDB的Get API的实现。现在,我们来探讨Put和Delete API的实现:

       Put API的主要功能是将一对键值对插入到Bucket中,如果键已经存在,则更新对应的值。首先,进行一些限制条件的检查,例如Put操作是否由写事务发起的,因为Put只能由写事务调用。此外,还需要检查键和值的大小是否符合限制条件。需要注意的是,Put操作和Get操作一样,这里也使用了Cursor来定位键应该放置的位置。

       在实际的Put操作中,会调用Cursor的一个不显眼的方法:

       这个方法实际上非常有用,它从当前Bucket的B-tree的根节点开始,一直到Cursor定位到的leaf page,为每个page创建一个对应的node结构。当然,如果一个page已经有对应的node,就直接使用它。

       为什么要这么做呢?这是因为事务篇中提到的修改操作具有“传染性”,修改B-tree的leaf节点会导致从root到leaf的所有page都需要修改,而BoltDB的修改操作都是在page对应的node里进行的,不是直接在page上修改,因此需要为这些page建立node结构。具体建立node结构的是Bucket的node方法:

       Bucket的node方法有两处需要注意,一个是新建的node会被追加到parent node的children中,记录下这些修改的node之间的关系,这个children在node持久化时会有用(node.spill方法)。另一个是node的数据是如何从page中读取的,这是由node的read方法完成的。

       node建立好之后,就在要修改的leaf对应的node上调用put方法:

       node的put方法相对简单,它是在inodes数组上查找对应的位置,如果exact为true,表示找到了相同的key,直接更新value;如果exact为false,相当于找到了应该插入的位置,然后在对应的inode上记录数据。我们来看一下inodes数组的定义:

       inodes数组是node实际存储数据的地方,由多个inode组成,每个不同的key对应一个不同的inode,inode之间是按key排序的。对于leaf节点来说,inode里使用key和value;对于branch节点来说,inode里使用key和pgid,pgid代表一个child page的id。value和pgid不会同时使用。

       put方法结束后,当前的Put操作也就结束了。也就是说,Put操作所做的仅仅是把新增或修改的数据放入到它所在的page对应的node内存中。

       顺便提一下Delete操作,它和Put操作非常类似,在建立起node结构之后,在对应的node的inodes数组中删除找到的key相等的inode就完成了,这里不再展开。

       那么,什么时候会把这些node里的数据持久化到DB文件里呢?是在整个写事务commit的时候。

       事务的Commit实现

       下面是事务commit的代码简化,保留了重要部分:

       Commit的整体流程比较长,下面一点一点进行说明。

       tx.root.rebalance(),这个root是root Bucket,rebalance是对root Bucket下所有子Bucket的所有node进行rebalance。这是什么意思?注意node的初始数据虽然来自一个page,但在经历了一些Delete操作后,有些node里面的数据可能过少,这时会先把这个node和它的左兄弟或右兄弟node合并(node的rebalance方法),合并后node数会减少,但不存在node里数据过少的情况。这个操作对应于B-tree的merge操作,只不过这些node都是Go的内存结构,合并起来非常简单。当然,合并后把这些node spill到page的操作,需要的page总数也会减少。

       tx.root.spill(),这个方法是把root Bucket下所有子Bucket的所有node的内容都写入这个事务分配的dirty page里。注意这些dirty page是这个事务临时分配在内存里的,结构和DB文件的page完全一样,但还不是mmap映射的DB的page。

       刚开始看到spill这个方法时,感觉它代价有些高,感觉像是把整个B-tree都走了一遍。后来仔细看才发现不是这么回事。这个spill只对有node结构的节点进行处理,那些没修改过的page没有对应的node,根本不会处理。

       注意在经过多次Put操作后,node里存放的数据可能出现一个page写不下的情况,比如insert了几千个key value。spill会先把这样的node split成多个大小合适的node(node的split方法),然后把这些node分别写入不同的page中。这个操作对应于B-tree的split操作。和rebalance方法类似的道理,因为这些node都是Go的内存结构,split起来非常容易。

       if tx.meta.pgid > opgid,这个判断是看当前事务需要的page数是否大于事务执行前DB文件有的page数,如果大于,说明DB文件放不下了,就调用db.grow增大文件,以容纳新增的page。

       紧接着是freelist的持久化操作,因为写事务可能使用了freelist里的一些page,同时也可能释放了一些page到freelist里,所以freelist很可能发生了变化,需要持久化。

       tx.write(),这个方法就是把所有的临时分配的dirty page都写入DB文件对应的page里。

       tx.writeMeta(),这个方法是把这个tx里的meta写到meta0或者meta1里面(写事务会交替写这两个meta page,这也是个常用技术,叫ping-pong buffer)。它的代码值得看一下:

       首先把meta写到临时分配的buf里,然后用文件IO写到DB文件里,最后调用fdatasync,把OS文件的buffer cache持久化到磁盘上。至此,写事务的所有数据都已经落盘完毕。后面新开启的事务会因为这个meta的txid是最大的,而选择使用这个最新的meta page。而这个meta page包括最新的root bucket,最新的freelist,最新的pgid,这些总体构成了一个DB的最新版本,保证新开启的事务读到最新版本的数据。

       看tx.write()和tx.writeMeta()的实现可以发现,写入数据用的是db.ops.writeAt,而这个方法默认值就是File.WriteAt方法,所以实际写入文件用的是文件IO,而不是直接写mmap内存。而BoltDB使用mmap一开始就把mmap映射的内存标记为只读的,压根不允许直接写mmap内存。为什么要这么做呢?

       猜测可能是为了安全。前面讲到Get操作为了性能是zero copy的,发现Get返回来的value是mmap上数据的指针,如果mmap设置为可读写的,应用程序代码五花八门,可能会通过指针一不小心修改了mmap上的数据,这样的修改因为走的不是API是无法保证事务的。把mmap设置为只读的消除了这种可能性。反过来说,如果mmap设置为可读写的,Get就不能返回mmap上的指针了,为了安全一定要copy一份数据出来才行,降低了Get的性能。

       这里还有个很自然而且很重要的问题是,如果事务commit失败了呢,BoltDB如何保证事务的原子性(ACID的A),确保这个写事务的所有操作,不论是落盘的,还是没落盘的,都不会生效?

       原子性要求,不管是commit走到哪一步,哪怕是已经把修改的数据,甚至包括修改的freelist已经落盘,只要最终事务commit失败,都不能对正确性产生任何影响。这里的正确性是指,数据库的状态(有实际的key value数据,freelist, pgid等共同构成)必须是在这个写事务运行之前的状态,数据不能被破坏,这个写事务也不能留下可被后续事务读到的任何更新。

       要做到原子性貌似挺难的,因为事务的commit里包括很多步骤,这些步骤都不是原子性的。不过重要的一点是,不论commit运行到哪一步,因为tx.writeMeta是最后一步,只有这一步运行成功commit才算成功,如果说commit失败了,那么tx.writeMeta一定是没运行,或者运行了半截,这个meta page没写完整,机器断电了。总之,这些情况下我们不会得到一个合法的新的meta page(这种情况下meta的validate方法会失败,因为meta的checksum不对)。这时候ping-pong buffer的meta page就起重要的作用了,因为交替写meta page的原因,即使这个写事务新的meta page没写成功,这个写事务运行前版本的meta page还在,而这个meta page包括这个写事务运行前的DB版本所有的状态(kv数据,freelist,pgid等)。这个meta page会被后续事务使用,就像那个失败的写事务从来没有运行过一样。而那个写事务留下的kv数据的page,freelist的page,即使是持久化了,也因为没有写成新的meta,没有机会被用到。

       还有个自然的疑问,即使这个失败的写事务写的page因为没有合法的meta无法被引用,不会影响正确性,但无法被引用是不是也意味着这些page无法被回收,浪费了磁盘空间?

       答案是也不会。在原来版本的meta里的free list和pgid的共同作用下,这些page会被视为free的,还可以使用,不会出现无法回收这些page的情况。

       还有个疑问,既然BoltDB交替写meta0和meta1,是不是连续两个事务commit正好在写meta时失败,数据库就废了?

       仔细研究发现,还是没事!因为写事务的txid也是meta的一部分,一个写事务失败,导致txid不会增长,下一次写事务的txid还是一样,meta的交替写是因为txid的变化引起的,既然没变化,就不交替了。所以下一个写事务即使写meta还失败了,也还是写的上一个写事务写的那个meta,不会把两个meta都写坏。

       总结一下,ping-pong buffer的meta page真是设计得精巧,是BoltDB达到原子性的关键!

FREE SOLO - 自己动手实现Raft - - leveldb源码分析与调试-2

       继续探讨leveldb的内部操作,首先解析写入过程。write-batch和leveldb key是核心数据结构,它们在数据写入中的角色至关重要。

       1. 数据写入流程:当通过DBImpl::Put或DB::Put添加键值对时,数据会被封装成write-batch。这个batch随后交给DBImpl::Write,最终由log::Writer::AddRecord负责将数据写入log。这样,数据便有了持久化的记录。

       2. 写入memtable:写入log后,数据还会被添加到memtable,便于快速查询。同样,DBImpl::Write通过MemTableInserter::Put调用MemTable::Add,将数据写入memtable,形成内存中的临时存储。

       3. 数据读取:对于查询,DBImpl::Get是起点,通过MemTable::Get调用SkipList::FindGreaterOrEqual在SortedTable的SkipList中搜索,提供即时的数据访问。

       总结:通过上述调用栈,我们可以对leveldb的写入和读取有更深入的理解。在后续的内容中,我们将关注大量数据写入对内存和磁盘影响的详细分析。

       期待在下次与您分享更多内容,再见!

       联系信息:email: castermode@gmail.com | 网站:vectordb.io | 项目未指定

HashMap实现原理一步一步分析(1-put方法源码整体过程)

       本文分享了HashMap内部的实现原理,重点解析了哈希(hash)、散列表(hash table)、哈希码(hashcode)以及hashCode()方法等基本概念。

       哈希(hash)是将任意长度的输入通过散列算法转换为固定长度输出的过程,建立一一对应关系。常见算法包括MD5加密和ASCII码表。

       散列表(hash table)是一种数据结构,通过关键码值映射到表中特定位置进行快速访问。

       哈希码(hashcode)是散列表中对象的存储位置标识,用于查找效率。

       Object类中的hashCode()方法用于获取对象的哈希码值,以在散列存储结构中确定对象存储地址。

       在存储字母时,使用哈希码值对数组大小取模以适应存储范围,防止哈希碰撞。

       HashMap在JDK1.7中使用数组+链表结构,而JDK1.8引入了红黑树以优化性能。

       HashMap内部数据结构包含数组和Entry对象,数组用于存储Entry对象,Entry对象用于存储键值对。

       在put方法中,首先判断数组是否为空并初始化,然后计算键的哈希码值对数组长度取模,用于定位存储位置。如果发生哈希碰撞,使用链表解决。

       本文详细介绍了HashMap的存储机制,包括数组+链表的实现方式,以及如何处理哈希碰撞。后续文章将继续深入探讨HashMap的其他特性,如数组长度的优化、多线程环境下的性能优化和红黑树的引入。

文章所属分类:百科频道,点击进入>>