JDK1.8HashMap原理和源码分析(java面试收藏).doc

JDK1.8 的新HashMap分析一、综述 Java中HashMap是非常常用的容器，因而也是需要面试官喜欢问的问题，难得有空，就对它进行源码级分析好了。一上来就看源码会有点头疼，那么先偷个懒，看看网上有没HashMap的分析。图1 HashMap的结构图一直到java 1.7为止，HashMap的结构都是这么简单，基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。这样子的HashMap性能上就将抱有一定疑问，如果说有成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那将不可避免的花费0(N)的查找时间，这将是多么大的性能损失。这儿问题终于在1.8得到解决。当然解决的代价就是代码变得更加复杂orz.图2 jdk1.8hashmap结构图到了1.8，当同一个hash值的节点数不小于8的时候，将不再以单链表形式存储了，会被调整成一棵红黑树（图中null节点没画）。这就是JDK1.8和1.7的最大区别。好了接下来就按照HashMap的成员域、构造函数、put函数来分析下HashMap。二、域transientNode table;HashMap的散列表transientSetMap.Entry entrySet;transientintsize;记录HashMap中存储了多少个键值对transientintmodCount;mod是modify的缩写，hashMap的结构发生结构变化时会记录一次。intthreshold;当size大于这个数时，就进行一次扩容，即调用resize()函数finalfloatloadFactor;这是一个比例参数，当table中已经被占用的元素数与table总长度的比例不小于这个参数的时候，就会发生table的扩容，每次扩容都以2倍大小进行扩容，注意resize()函数还有几个参数需要解释下：staticfinalintDEFAULT_INITIAL_CAPACITY= 1 4;默认初始化table的大小staticfinalintMAXIMUM_CAPACITY= 1 30;table的最大大小staticfinalfloatDEFAULT_LOAD_FACTOR= 0.75f;默认loadFactor大小staticfinalintTREEIFY_THRESHOLD= 8;当节点冲突数达到8时，就会对hash表进行调整，如果table的长度小于64，那么会进行table扩容，如果不小于64，那么会将因冲突形成的单链表调整为红黑树。staticfinalintUNTREEIFY_THRESHOLD= 6;这个参数还不是很明白，有可能在删除冲突节点之后，可能同hash的节点数低于这个值时，将红黑树重新恢复为单链表。staticfinalintMIN_TREEIFY_CAPACITY= 64;注意到TREEIFY_THRESHOLD解释，不小于64时仅对table进行扩容，这个64就是指这个值。三、构造函数Node节点是对Key-Value的包装，是存储在HashMap中的节点，由于代码简单，就不做分析了。staticclassNodeimplementsMap.Entry finalinthash;finalKkey; Vvalue; Nodenext; Node(inthash, Kkey, Vvalue, Nodenext) this.hash=hash;this.key=key;this.value=value;this.next=next; publicfinalK getKey() returnkey; publicfinalV getValue() returnvalue; publicfinalString toString() returnkey+=+value; publicfinalinthashCode() returnObjects.hashCode(key) Objects.hashCode(value); publicfinalV setValue(VnewValue) VoldValue=value;value=newValue;returnoldValue; publicfinalbooleanequals(Objecto) if(o=this)returntrue;if(oinstanceofMap.Entry) Map.Entrye= (Map.Entry)o;if(Objects.equals(key,e.getKey() & Objects.equals(value,e.getValue() returntrue; returnfalse; 接着是HashTable的构造函数publicHashMap(intinitialCapacity,floatloadFactor) if(initialCapacityMAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;if(loadFactor= 0 | Float.isNaN(loadFactor)thrownewIllegalArgumentException(Illegal load factor: +loadFactor);this.loadFactor=loadFactor;this.threshold=tableSizeFor(initialCapacity); 对于HashMap，实际上有两个参数是可以由用户来设置的：initialCapacity：是初始化hash表的大小，但是HashMap中合法的Hash表大小是2的次幂，因此，会有tableSizeFor(int)函数进行数据调整，调整成不小于输入参数的最小的一个2的次幂数，比如输入3，那么输出就是4。LoadFactor：就是table占用比门限，这个参数解释见第二节。 HashMap还有几个构造函数，但比较简单，就不再解释publicHashMap(intinitialCapacity) this(initialCapacity,DEFAULT_LOAD_FACTOR); publicHashMap() this.loadFactor=DEFAULT_LOAD_FACTOR;/ all other fields defaulted publicHashMap(Mapm) this.loadFactor=DEFAULT_LOAD_FACTOR;putMapEntries(m,false); 四、put函数publicV put(Kkey, Vvalue) returnputVal(hash(key),key,value,false,true); Put函数是这样的，和1.7差距有点大，因为1.7的时候put的所有代码都在put函数中，1.8的时候只是对putVal函数做了包装，因为要添加一个键值对，要更多参数了。finalV putVal(inthash, Kkey, Vvalue,booleanonlyIfAbsent,booleanevict) Nodetab; Nodep;intn,i;if(tab=table) =null| (n=tab.length) = 0)/先判断，table大小，如果table为null，或者没分配空间，就resize一次n= (tab= resize().length;if(p=tabi= (n- 1) &hash) =null)/如果首节点为null，就创建一个首节点。注意到tabi = (n - 1) & hash,(n-1)&hash才是真正的hash值，也就是存储在table的位置（index）。tabi = newNode(hash,key,value,null);/创建一个新的节点else/到这儿了，说明碰撞了，那么就要开始处理碰撞了 Nodee; Kk;/首先先去查找与待插入键值对key相同的Node，存储在e中，k是那个节点的keyif(p.hash=hash& (k=p.key) =key| (key!=null&key.equals(k)/p这时候是指向tablei的那个Node，这时候先判断下tablei这个节点是不是和我们待插入节点有相同的hash、key值。如果是就e = pe=p;elseif(pinstanceofTreeNode)/到这儿，说明第一个节点的hash、key值与我们带插入Node的hash、key值不吻合，那么要从这个节点之后的链表节点或者树节点中查找。由于之前提到过，1.8的HashMap存储碰撞节点时，有可能是用红黑树存储，那么先判断首节点p的类型，如果是TreeNode类型（Node的子类），那么就说明碰撞节点已经用红黑树存储，那么使用树的插入方法，如果新插入了树节点，那么e会等于null，用于后面的判断与处理e= (TreeNode)p).putTreeVal(this,tab,hash,key,value);else/说明碰撞节点是单链表存储的for(intbinCount= 0; ; +binCount) /单链表逐个向后查找if(e=p.next) =null) /e引用下一个节点，如果是null，表示没有找到同hash、key的节点p.next= newNode(hash,key,value,null);/创建一个新的节点，放到冲突链表的最后if(binCount=TREEIFY_THRESHOLD- 1)/注意到如果这时候冲突节点个数达到8个，那么就会treeifyBin(tab, hash)函数，看是否需要改变冲突节点的存储结构，这个treeifyBin首先回去判断当前hash表的长度，如果不足64的话，实际上就只进行resize，扩容table，如果已经达到64，那么才会将冲突项存储结构改为红黑树。 treeifyBin(tab,hash);break; if(e.hash=hash& (k=e.key) =key| (key!=null&key.equals(k)/如果找到了同hash、key的节点，那么直接退出循环break;p=e;/调整下p节点 if(e!=null) /退出循环后，先看e是不是为null，为null表示添加了一个新节点，而不为null表示找到了一个与待插入同hash、同key的已存节点 VoldValue=e.value;if(!onlyIfAbsent|oldValue=null)/注意到这时候要判断是不是要修改已插入节点的value值，两个条件任意满足即修改e.value=value; afterNodeAccess(e);/这个是空函数，可以由用户根据需要覆盖returnoldValue; +modCount;/当插入了新节点，才会运行到这儿，由于插入了新节点，整个HashMap的结构调整次数+1if(+sizethreshold)/HashMap中节点数+1，如果大于threshold，那么要进行一次扩容 resize(); afterNodeInsertion(evict);/这个是空函数，可以由用户根据需要覆盖returnnull; 这才是put函数的本体，先从输入参数开始解释：Int hash：输入的hash值，是key的hash值，但是这个不是真正table的hash值，还得进行换算。K key：键值对的键V value：键值对的值booleanonlyIfAbsent：如果找到同key的键值对，是否更新value值，true就是更新，false就是不更新。booleanevict：这个参数只在afterNodeInsertion(evict)函数中使用，但是这个函数是个空的函数，如果用户不覆盖这个函数，那么这个参数没有意义。好了，接下来就是分析源码了。不得不先吐槽一下，1.8的hashmap代码真的很丑啊。赋值语句强行放在if判断语句内，刚开始看还真是不习惯。好了，直接看上面源码的注释吧。五、相关函数分析finalNode resize()finalNode resize() NodeoldTab=table;/临时变量赋值hash表intoldCap= (oldTab=null) ? 0 :oldTab.length;/读取hash表的长度intoldThr=threshold;/读取hash表的扩容门限（对于节点个数）intnewCap,newThr= 0;if(oldCap 0) /如果老table的容量进行判断if(oldCap=MAXIMUM_CAPACITY) /大于0的情况表示table已经存在，查看此容量大小，比MAXIMUM大的话调整为MAXIMUM_CAPACITYthreshold= Integer.MAX_VALUE;returnoldTab;/返回老的表 elseif(newCap=oldCap 1) =DEFAULT_INITIAL_CAPACITY)/扩容是将老容量大小*2newThr=oldThr 0)/虽然老table容量为0，但是它的容量门限被谁都那个不是0，那么新的table容量就是OldThrnewCap=oldThr;else/如果老的table容量和门限都是0，用默认值进行初始化新table的容量和门限newCap=DEFAULT_INITIAL_CAPACITY;newThr= (int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY); if(newThr= 0) /如果说新表门限是0floatft= (float)newCap*loadFactor;/先计算并临时存储一个门限值newThr= (newCapMAXIMUM_CAPACITY&ft (float)MAXIMUM_CAPACITY? (int)ft: Integer.MAX_VALUE);/重新设置新门限值 threshold=newThr;/HashMap的门限域被重现设置，前面都只是对临时变量进行操作的SuppressWarnings(rawtypes,unchecked) NodenewTab= (Node)newNodenewCap;/使用新容量创建一个新表table=newTab;/HashMap的table域赋值新创建的tableif(oldTab!=null) for(intj= 0;joldCap; +j) /从table0tableoldCap进行节点转移 Nodee;if(e=oldTabj) !=null) /取出第一个节点就行，然后把oldTabj赋值为null。oldTabj =null;if(e.next=null)newTabe.hash& (newCap- 1) =e;/e没有后续节点，那么之前并没有发生碰撞，简单完成单节点转移就好了，由于新的table的容量变化了，那么e这个节点的它真正的hash值（存入table的位置index）是要重新计算的。elseif(einstanceofTreeNode)/如果e是树节点类型，说明这次移动的是一棵树 (TreeNode)e).split(this,newTab,j,oldCap);/好了，这时候是对一棵树的调整else/到这儿e后面带着个单链表，那么就要逐个去将单链表中每个元素重新算在HashMap中的位置，并进行搬运 NodeloHead=null,loTail=null; NodehiHead=null,hiTail=null; Nodenext;donext=e.next;/记录下一个节点if(e.hash&oldCap) = 0) /原来的链表e因为新链表是2倍扩容，那么实际上会被拆分成两队，e.hash/oldCap为奇数一队，放在hi队中，而e.hash/oldCap为偶数一队，放在lo队中，这儿使用(e.hash & oldCap) = 0是用了一个技巧，运算结果一致if(loTail=null)loHead=e;elseloTail.next=e;loTail=e; elseif(hiTail=null)hiHead=e;else hiTail.next=e;hiTail=e; while(e=next) !=null);if(loTail!=null) /lo队不为空，则放在新队的原位置loTail.next=null;newTabj =loHead; if(hiTail!=null) hiTail.next=null;newTabj+oldCap =hiHead;/hi队不为空，则放在新队的j+oldCap中 returnnewTab; finalvoidtreeifyBin(Node tab, inthash)finalvo