从源码角度解读：HashTable、HashMap与ConCurrentHashMap 内部维护一个数组

HashMap的数据结构hashMap初始的数据结构如下图所示，内部维护一个数组，然后数组上维护一个单链表，有个形象的比喻就是像挂钩一样，数组脚标一样的，一个一个的节点往下挂。
//此处略过其他代码，只截取出了hashMap的数组结构相关的数组与链表publicclassHashMapextendsAbstractMapimplementsMap,Cloneable,Serializable{privatestaticfinallongserialVersionUID=362498820763181265L;/*----------------Fields--------------*//***Thetable,initializedonfirstuse,andresizedas*necessary.Whenallocated,lengthisalwaysapoweroftwo.*(Wealsotoleratelengthzeroinsomeoperationstoallow*bootstrappingmechanicsthatarecurrentlynotneeded.)*///这个是hashMap内部维护的数组transientNode[]table;/***Basichashbinnode,usedformostentries.(Seebelowfor*TreeNodesubclass,andinLinkedHashMapforitsEntrysubclass.)*///这个是数组元素的节点类， next的属性表示下一个节点，即数组的节点元素维护的下一个节点的元素，那不是就是链表吗staticclassNodeimplementsMap.Entry{finalinthash;//数组的脚标值，下面会详细描述这个内容finalKkey;//map的keyVvalue;//map的valueNodenext;//下一个节点Node(inthash,Kkey,Vvalue,Nodenext){this.hash=hash;this.key=key;this.value=https://pcff.toutiao.jxnews.com.cn/p/20200808/value;this.next=next;}publicfinalKgetKey(){returnkey;}publicfinalVgetValue(){returnvalue;}publicfinalStringtoString(){returnkey+"="+value;}publicfinalinthashCode(){returnObjects.hashCode(key)^Objects.hashCode(value);}publicfinalVsetValue(VnewValue){VoldValue=https://pcff.toutiao.jxnews.com.cn/p/20200808/value;value=newValue;returnoldValue;}publicfinalbooleanequals(Objecto){if(o==this)returntrue;if(oinstanceofMap.Entry){Map.Entry,?>e=(Map.Entry,?>)o;if(Objects.equals(key,e.getKey())&&Objects.equals(value,e.getValue()))returntrue;}returnfalse;}}通过源码可知， HashMap的数据结构正如上文所述，是一个数组加链表的形式存储数组，那么数组的角标是怎么计算的呢？如果是你来设计，你会怎么去设计这个角标的计算方式呢？
在没看源码之前，我做了一个猜想，就是数组的角标我猜想是按照下面的计算方式计算的：
既然是HashMap ，那肯定有个hashCode然后通过key值的hashCode与数组的长度取模取模之后，数值一样的，就往数组的节点上面往下挂上面是我的猜想，但是HashMap的数组角标的实现真的是这样吗？我们进入下一节去探究
hash值的计算既然要看脚标值的计算，那我们肯定要看HashMap的put方法，因为在put方法里面肯定要计算出脚标的值，然后才能把数据存放到数组里面去嘛，所以我们直接看put的源码：
/***Associatesthespecifiedvaluewiththespecifiedkeyinthismap.*Ifthemappreviouslycontainedamappingforthekey,theold*valueisreplaced.**@paramkeykeywithwhichthespecifiedvalueistobeassociated*@paramvaluevaluetobeassociatedwiththespecifiedkey*@returnthepreviousvalueassociatedwithkey,or*nulliftherewasnomappingforkey.*(Anullreturncanalsoindicatethatthemap*previouslyassociatednullwithkey.)*///此处是HashMap的put方法的源码，这个put方法又调了另一个putVal的方法，我们看一下putVal的方法publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}/***ImplementsMap.putandrelatedmethods**@paramhashhashforkey*@paramkeythekey*@paramvaluethevaluetoput*@paramonlyIfAbsentiftrue,don'tchangeexistingvalue*@paramevictiffalse,thetableisincreationmode.*@returnpreviousvalue,ornullifnone*/finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;Nodep;intn,i;if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);else{这里我们关注tab[i]=newNode(hash,key,value,null);这句代码，前面我们看到了tab就是数组，那说明这句代码就是给节点赋值，那么i就是数组的角标那这个i是怎么计算的呢？
看他上面的一句判断(p=tab[i=(n-1)&hash]即这个i是通过(n-1)&hash计算出来的， n=tab.length这个n是数组的长度，就是说数组的角标是通过数组的长度-1与上这个hash ，这个跟我们之前猜想的然后通过hashCode与数组的长度取模就不一致了，那这里我们先保留着这个问题，先看一下hash的计算，从上面代码中，可以知道， hash值是通过调用hash(key)方法调用得到。
这里我将计算hash的方法，单独抽离出来外面写，如下：
staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}key就是map调用put方法， put进来的key值，看上面这个方法，前面判空之后返回0的大家一眼就看明白了，主要关注后面的内容， (h=key.hashCode())^(h>>>16)这句代码前半部分很明白，就是取key的hashCode值赋给h ，（^这个符号表示异或， >>>表示无符号右移），然后与h右移16位后的值进行异或操作。
为什么要这样计算去计算hash呢？这样计算hash又最终与数组的脚标有什么联系呢？
下面我来画张图，来理顺这一块的计算，看下图：
就是hashMap的数组初始大小是16 ，那length-1的值就为15 ， 15的二进制值是….00001111 ，此时上面hash值363766277的二进制位00010101101011101010001000000101 ，这两个数进行与运算时，由于15的前面高位都为0 ，所以进行与运算的值最终都不可能大于15 ，像这个例子，最终的值为0101为9 ，这样就保证了每一个脚标i值都能在数组的长度内
那么这里就有一个疑问了，为什么不直接采用与数组长度取模的方式，直接取得脚标值，而是先去异或，再与运算去计算脚标值？
主要有两个原因：
1.用位运算，效率更高
2.hashCode的高低位异或运算，让高低位更加均匀的混合到一起，可以使得在put元素时，可以减少哈希碰撞
减少哈希碰撞才是最主要的原因。那什么是哈希碰撞呢？
我们知道HashMap的数组结构不是数组加链表吗？那数组跟链表有什么特点？我们都知道数组是查询快、增删慢，链表是查询慢、增删快。
这也很容易理解，链表嘛，只记录着下一个节点的值，又没有脚标，如果你这个链表很长（虽然在这里最长不会超过8 ，后面会讲到），你查找的一个元素刚好在最后一个，那不是在定位到数组脚标以后找到链表的第一个节点，然后往下一直遍历查找到最后一个才找到我们要的元素，这样效率不就很慢了吗，所以如果我们直接对hashCode跟数组的长度进行取模，计算出的hash值可能会碰撞高，就会使得数组单个节点的链表很长很长，而这样子HashMap的查询效率就很差，而hashCode的高低位异或运算，可以让高低位更加均匀的混合到一起，减少哈希碰撞，从而提高HashMap的查询效率。
一句话总结，失败的hashCode算法会导致HashMap的性能由数组下降为链表，所以想要避免发生碰撞，就要提高hashCode结果的均匀性。
数组的扩容数组的初始化长度在上一节的时候，我们讲到了HashMap的长度总是2^n这句话，我们怎么知道呢，我们可以从源码中找到这一设定，那么我们首先先看一下， HashMap数组初始的默认大小是多少呢，源码中有这一句代码
/***Thedefaultinitialcapacity-MUSTbeapoweroftwo.*/staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka但是，我们不能光看这个常量值就说HashMap内数组的默认常量值就是16啊，我们要继续找到初始化的方法代码，看他是不是初始值为16
/***Initializesordoublestablesize.Ifnull,allocatesin*accordwithinitialcapacitytargetheldinfieldthreshold.*Otherwise,becauseweareusingpower-of-twoexpansion,the*elementsfromeachbinmusteitherstayatsameindex,ormove*withapoweroftwooffsetinthenewtable.**@returnthetable*///上面的英文中说到，初始化或者翻倍数组的大小finalNode[]resize(){Node[]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;}elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;//doublethreshold}elseif(oldThr>0)//initialcapacitywasplacedinthresholdnewCap=oldThr;else{//zeroinitialthresholdsignifiesusingdefaultsnewCap=DEFAULT_INITIAL_CAPACITY;//当oldTab即为table数组的长度，当oldTab长度为0时，将DEFAULT_INITIAL_CAPACITY赋值给newCap ， newCap即为数组的新长度newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}我们可以查询下resize()方法的调用者，发现putVal()方法里调用了这个方法
所以HashMap中数组的初始化长度就是DEFAULT_INITIAL_CAPACITY ，等于1<<4 ，等于16
数组扩容的阈值上一节我们知道数组的初始长度是16 ，然而16的长度显然不能满足我们普通应用的开发，所以这里就涉及到了数组的扩容。那要什么时候扩容，怎么扩呢？
我们知道，链表的查询效率肯定比数组的查询效率低，所以要提高HashMap的查询效率，我们肯定要数据尽可能多的往数组上存数据，而不是延长链表的长度。那是不是存满之后再做扩容呢？比方说数组初始化16 ，等到存满16的时候或者第17个进来的时候，开始扩容呢？
我们可以先分析一下，然后再来看源码。当数组的元素都放满了，然后这时候来扩容，扩容之后，数组元素的脚标值就得重新计算，即rehash ，比如原来是计算hash用的数组长度16 ，扩容之后数组长度变成了32 ，这时候(n-1)&hash计算脚标的值就不正确了，那你数组都存满了，那不是数组的每个元素都得重新计算脚标i值，所以这种做法是不是不合理？
那么这个阈值具体是多少呢？下面我们来探究源码，既然要找到扩容的阈值，那我们不外乎要从两个方法入手去找，一个就是put()操作的时候，一个就是扩容resize()的时候。因为我已经找过了，我就直接去put()方法里面找了， resize()方法后面会细讲，这里就讲put()方法。
//这里put方法只调用了putVal方法，那我们就直接看putVal方法publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}//我解释下这个方法里面，大概的操作finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;Nodep;intn,i;if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;//这一步之前分析过了，就是判断数组为null或长度为0时，对数组进行扩容if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);//这一步其实也很清楚了，就是根据hash值计算出数组的脚标，然后判断数组的该脚标的元素是否为空，为空的话就把put进来的数据封装成节点赋值进数组else{//根据上面的两个判断，那么走到这里的代码就是说，数组不为空，而且put进来的key计算所得的脚标节点也不为空，走这一块逻辑（实际上这块逻辑也跟扩容的阈值无关，只是单纯的判断然后加节点的操作，但是我还是解释下这里的代码）Nodee;Kk;if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;//这里的意思是说，如果hash值相同， key值也相同，那么就说明此时put操作的元素在数组从存在，这覆盖该节点elseif(pinstanceofTreeNode)e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);//这里是判断节点类型是否是树类型，为什么会是树类型呢？不是说是HashMap是数组加链表吗？后面的章节会详细讲到，这里暂且跳过else{//代码走到这里，就说明此时put进来的元素，对应的数组脚标是个链表for(intbinCount=0;;++binCount){//此处的代码后面讲链表时会细讲，这里暂且跳过if((e=p.next)==null){p.next=newNode(hash,key,value,null);if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}//这里判断hash值与key值是否都相同，如果是即说明map中存在该key-value ，此时跳出循环if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}//此逻辑是判断hash值与key值是否都相同跳出循环后，将新值覆盖旧值，然后将旧值返回出去if(e!=null){//existingmappingforkeyVoldValue=https://pcff.toutiao.jxnews.com.cn/p/20200808/e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;//hashMap内部维护的一个修改的次数，有兴趣了解的话可以看源码里面对这个属性的翻译if(++size>threshold)resize();//扩容，在此之前的代码，都是判断之后进行添加覆盖节点的操作，此处是插入新节点之后判断是否扩容，所以这里的条件就是我们找了这么久的扩容的阈值！！！afterNodeInsertion(evict);returnnull;}走读完上面的代码，我们可以得知if(++size>threshold) ，如下代码可知size实际上就是HashMap集合的键值对数，即长度，所以就是说，当size的大小超过threshold时，开始进行扩容，也即threshold就是进行扩容的阈值。那么这个阈值的大小是多少呢？
/***Thenumberofkey-valuemappingscontainedinthismap.*/transientintsize;/***Returnsthenumberofkey-valuemappingsinthismap.**@returnthenumberofkey-valuemappingsinthismap*/publicintsize(){returnsize;}继续走读源码，找到resize()方法处，
我们可以继续走读源码来验证是否数组长度超过75%就进行扩容，还是上面那张图的源码，我把其中一段给抽离出来，如下：
if(oldCap>0){if(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;returnoldTab;}//此处的意思是说，当数组的长度是大于0的时候，而且数组扩容一倍之后，小于默认配置的最大值时，并且大于初始化数组的长度，则执行if下面的代码，那就是说，扩容之后如果没超过最大值，就走这个逻辑elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)//而这个逻辑的代码意思，就是阈值threshold增大一倍（左移一位）newThr=oldThr<<1;//doublethreshold}那么，我们就知道了，当数组扩容时， threshold的值也会增大一倍，那么下一次扩容时，也是HashMap的size超过数组长度的75%的时候，就进行扩容。
扩容【从源码角度解读：HashTable、HashMap与ConCurrentHashMap】HashMap内数组的扩容是将数组的长度左移一位，在二进制运算中，左移一位实际上就是将数值扩大一倍。而且我们也知道，扩容的源码就是resize()这个方法，所以这一章节就来重点解读resize()方法的源码
/***Initializesordoublestablesize.Ifnull,allocatesin*accordwithinitialcapacitytargetheldinfieldthreshold.*Otherwise,becauseweareusingpower-of-twoexpansion,the*elementsfromeachbinmusteitherstayatsameindex,ormove*withapoweroftwooffsetinthenewtable.**@returnthetable*/finalNode[]resize(){Node[]oldTab=table;//oldTab就是扩容前数组对象intoldCap=(oldTab==null)?0:oldTab.length;//oldCap就是扩容前数组的长度intoldThr=threshold;//oldThr就是扩容前的阈值intnewCap,newThr=0;//声明newCap-扩容后的数组长度， newThr-扩容后的阈值if(oldCap>0){//这一部分逻辑其实上一节已经讲过了，在这里我就大致说一下，就是如果这是扩容前数组长度已经达到了默认配置的最大值时，那么就不扩容了，直接返回原数组，否则，数组扩容一倍，阈值也增大一倍if(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;returnoldTab;}elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;//doublethreshold}elseif(oldThr>0)//initialcapacitywasplacedinthresholdnewCap=oldThr;//这个判断不是正常创建Map集合走的逻辑，这里可以跳过这句代码else{//zeroinitialthresholdsignifiesusingdefaults//这一步的代码前面也解释过了，就是当数组长度为0 ，初始化数组长度与扩容的阈值newCap=DEFAULT_INITIAL_CAPACITY;newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}if(newThr==0){floatft=(float)newCap*loadFactor;newThr=(newCap<MAXIMUM_CAPACITY&&ft<(float)MAXIMUM_CAPACITY?(int)ft:Integer.MAX_VALUE);}//将新的扩容后的阈值赋值给thresholdthreshold=newThr;@SuppressWarnings({"rawtypes","unchecked

从源码角度解读：HashTable、HashMap与ConCurrentHashMap

推荐阅读

深海鱼油对身体有什么好处

秘制红烧鸡爪

花生怎么做好吃小吃

李嫣|李嫣摆摊义卖穿着打扮引发争议

有氧体操减肥吗？

雷诺纬度|地球在自转，直升机在空中悬停12小时后，会到地球的另一边吗？

工作人员|涉嫌强奸5岁女童致受害者住进ICU，嫌犯养母发声

梦见别人的新娘子是什么意思梦见好多新娘子是啥意思

央视新闻客户端|19名球员确诊！阿根廷足球俱乐部恢复训练前公布检测初步结果

汽车营销培训课程，教你如何做好汽车销售

人社部：公务员或不再招考为主，这几类人可直接进入！

环境|什么原因引起失眠

四喜丸子的家常做法的做法窍门窍门,四喜丸子的做法最正宗的做法视频窍门-

控股|威海广泰：控股股东广泰投资解除质押720万股

11国官员来闽培训茶艺亲睐大田茶文化

[]职场上升法则：三大原则，帮你站稳脚跟，往高处走

|河北银行家：对下季度宏观经济热度预期指数增强12.8%

[可惜]它极为珍贵，人称“亚洲人参”，农村常见却常被当成野草

ZAKER|网友：大快人心，醉酒男绕到桥梁外侧坠亡，家属索赔31万，法院判了

iQOO|iQOO 8系列展望：不止骁龙888 Plus和顶级屏幕设计也抢眼