JavaJdk1.8HashMap源码阅读笔记二
三、源码阅读
3、元素包含containsKey(Objectkey)
/
Returnstrueifthismapcontainsamappingforthe
specifiedkey.
@paramkeyThekeywhosepresenceinthismapistobetested
@returntrueifthismapcontainsamappingforthespecified
key.
/
publicbooleancontainsKey(Objectkey){
returngetNode(hash(key),key)!=null;
}
/
ImplementsMap.getandrelatedmethods
@paramhashhashforkey
@paramkeythekey
@returnthenode,ornullifnone
/
finalNodegetNode(inthash,Objectkey){
Node[]tab;Nodefirst,e;intn;Kk;
if((tab=table)!=null&&(n=tab.length)>0&&
//判断tab[hash]位置是否有值
(first=tab[(n-1)&hash])!=null){
if(first.hash==hash&&//alwayscheckfirstnode
((k=first.key)==key||(key!=null&&key.equals(k))))
returnfirst;
if((e=first.next)!=null){
if(firstinstanceofTreeNode)
return((TreeNode)first).getTreeNode(hash,key);
//遍历寻找
do{
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
returne;
}while((e=e.next)!=null);
}
}
returnnull;
}
/
Callsfindforrootnode.
/
finalTreeNodegetTreeNode(inth,Objectk){
return((parent!=null)?root():this).find(h,k,null);
}
/
Returnsrootoftreecontainingthisnode.
获取红黑树的根
/
finalTreeNoderoot(){
for(TreeNoder=this,p;;){
if((p=r.parent)==null)
returnr;
r=p;
}
}
/
Findsthenodestartingatrootpwiththegivenhashandkey.
ThekcargumentcachescomparableClassFor(key)uponfirstuse
comparingkeys.
/
finalTreeNodefind(inth,Objectk,Classkc){//k即key，kc为null
TreeNodep=this;
do{
intph,dir;Kpk;
TreeNodepl=p.left,pr=p.right,q;
if((ph=p.hash)>h)//ph存当前节点hash
p=pl;
elseif(ph
p=pr;//查右子树
elseif((pk=p.key)==k||(k!=null&&k.equals(pk)))
returnp;//hash、key均相同，【找到了！】返回当前节点
elseif(pl==null)//hash等，key不等，且当前节点的左节点null
p=pr;//查右子树
elseif(pr==null)
p=pl;
//get->getTreeNode传递的kc为null。||逻辑或,短路运算,有真即可
//false||(false&&？？)
elseif((kc!=null||
(kc=comparableClassFor(k))!=null)&&
(dir=compareComparables(kc,k,pk))!=0)
p=(dir<0)?pl:pr;
elseif((q=pr.find(h,k,kc))!=null)
returnq;
else
p=pl;
}while(p!=null);
returnnull;
}
4、get(Objectkey)
/
返回value或null
/
publicVget(Objectkey){
Nodee;
return(e=getNode(hash(key),key))==null?null:e.value;
}
函数getNode在阅读笔记一中已经记录。
5、移除remove(Objectkey)
/
Removesthemappingforthespecifiedkeyfromthismapifpresent.
@paramkeykeywhosemappingistoberemovedfromthemap
@returnthepreviousvalueassociatedwithkey,or
nulliftherewasnomappingforkey.
(Anullreturncanalsoindicatethatthemap
previouslyassociatednullwithkey.)
/
publicVremove(Objectkey){
Nodee;
return(e=removeNode(hash(key),key,null,false,true))==null?
null:e.value;
}
/
ImplementsMap.removeandrelatedmethods
@paramhashhashforkey
@paramkeythekey
@paramvaluethevaluetomatchifmatchValue,elseignored
@parammatchValueiftrueonlyremoveifvalueisequal
@parammovableiffalsedonotmoveothernodeswhileremoving
@returnthenode,ornullifnone
/
finalNoderemoveNode(inthash,Objectkey,Objectvalue,
booleanmatchValue,booleanmovable){
Node[]tab;Nodep;intn,index;
if((tab=table)!=null&&(n=tab.length)>0&&
(p=tab[index=(n-1)&hash])!=null){
Nodenode=null,e;Kk;Vv;
if(p.hash==hash&&
//先比较内存地址，如果地址不一致，再调用equals进行比较
((k=p.key)==key||(key!=null&&key.equals(k))))
node=p;
elseif((e=p.next)!=null){
//如果是以红黑树处理冲突，则通过getTreeNode查找
if(pinstanceofTreeNode)
node=((TreeNode)p).getTreeNode(hash,key);
else{
//如果是以链式的方式处理冲突，则通过遍历链表来寻找节点
do{
if(e.hash==hash&&
((k=e.key)==key||
(key!=null&&key.equals(k)))){
node=e;
break;
}
p=e;
}while((e=e.next)!=null);
}
}
//比对找到的key的value跟要删除的是否匹配
if(node!=null&&(!matchValue||(v=node.value)==value||
(value!=null&&value.equals(v)))){
if(nodeinstanceofTrewww.shanxiwang.neteNode)
((TreeNode)node).removeTreeNode(this,tab,movable);
elseif(node==p)
tab[index]=node.next;
else
p.next=node.next;
//已从结构上修改此列表的次数
++modCount;
--size;
//回调
afterNodeRemoval(node);
returnnode;
}
}
returnnull;
}
/
Removesthegivennode,thatmustbepresentbeforethiscall.
Thisismessierthantypicalred-blackdeletioncodebecausewe
cannotswapthecontentsofaninteriornodewithaleaf
successorthatispinnedby"next"pointersthatareaccessible
independentlyduringtraversal.Soinsteadweswapthetree
linkages.Ifthecurrenttreeappearstohavetoofewnodes,
thebinisconvertedbacktoaplainbin.(Thetesttriggers
somewherebetween2and6nodes,dependingontreestructure).
/
finalvoidremoveTreeNode(HashMapmap,Node[]tab,
booleanmovable){
intn;
if(tab==null||(n=tab.length)==0)
return;
intindex=(n-1)&hash;
TreeNodefirst=(TreeNode)tab[index],root=first,rl;
TreeNodesucc=(TreeNode)next,pred=prev;
if(pred==null)
tab[index]=first=succ;
else
pred.next=succ;
if(succ!=null)
succ.prev=pred;
if(first==null)
return;
if(root.parent!=null)
root=root.root();
if(root==null||root.right==null||
(rl=root.left)==null||rl.left==null){
tab[index]=first.untreeify(map);//toosmall
return;
}
TreeNodep=this,pl=left,pr=right,replacement;
if(pl!=null&&pr!=null){
TreeNodes=pr,sl;
while((sl=s.left)!=null)//findsuccessor
s=sl;
booleanc=s.red;s.red=p.red;p.red=c;//swapcolors
TreeNodesr=s.right;
TreeNodepp=p.parent;
if(s==pr){//pwass''sdirectparent
p.parent=s;
s.right=p;
}
else{
TreeNodesp=s.parent;
if((p.parent=sp)!=null){
if(s==sp.left)
sp.left=p;
else
sp.right=p;
}
if((s.right=pr)!=null)
pr.parent=s;
}
p.left=null;
if((p.right=sr)!=null)
sr.parent=p;
if((s.left=pl)!=null)
pl.parent=s;
if((s.parent=pp)==null)
root=s;
elseif(p==pp.left)
pp.left=s;
else
pp.right=s;
if(sr!=null)
replacement=sr;
else
replacement=p;
}
elseif(pl!=null)
replacement=pl;
elseif(pr!=null)
replacement=pr;
else
replacement=p;
if(replacement!=p){
TreeNodepp=replacement.parent=p.parent;
if(pp==null)
root=replacement;
elseif(p==pp.left)
pp.left=replacement;
else
pp.right=replacement;
p.left=p.right=p.parent=null;
}
TreeNoder=p.red?root:balanceDeletion(root,replacement);
if(replacement==p){//detach
TreeNodepp=p.parent;
p.parent=null;
if(pp!=null){
if(p==pp.left)
pp.left=null;
elseif(p==pp.right)
pp.right=null;
}
}
if(movable)
moveRootToFront(tab,r);
}
方法finalvoidremoveTreeNode暂时没有吃透，待后续补充。
四、小结
HashMap高性能需要以下几点：
1、高效的hash算法
2、保证hash值到内存地址（数组索引）的映射速度
3、根据内存地址（数组索引）可以直接得到相应的值
|
|
