Java中LinkedHashMap源码解析
概述:
LinkedHashMap实现Map继承HashMap,基于Map的哈希表和链该列表实现,具有可预知的迭代顺序。
LinedHashMap维护着一个运行于所有条目的双重链表结构,该链表定义了迭代顺序,可以是插入或者访问顺序。
LintHashMap的节点对象继承HashMap的节点对象,并增加了前后指针beforeafter:
/** *LinkedHashMap节点对象 */ staticclassEntryextendsHashMap.Node { Entry before,after; Entry(inthash,Kkey,Vvalue,Node next){ super(hash,key,value,next); } }
lintHashMap初始化:
accessOrder,简单说就是这个用来控制元素的顺序,
accessOrder为true:表示按照访问的顺序来,也就是谁最先访问,就排在第一位
accessOrder为false表示按照存放顺序来,就是你put元素的时候的顺序。
publicLinkedHashMap(intinitialCapacity,floatloadFactor){ super(initialCapacity,loadFactor); accessOrder=false; } /** *生成一个空的LinkedHashMap,并指定其容量大小,负载因子使用默认的0.75, *accessOrder为false表示按照存放顺序来,就是你put元素的时候的顺序 *accessOrder为true:表示按照访问的顺序来,也就是谁最先访问,就排在第一位 */ publicLinkedHashMap(intinitialCapacity){ super(initialCapacity); accessOrder=false; } /** *生成一个空的HashMap,容量大小使用默认值16,负载因子使用默认值0.75 *默认将accessOrder设为false,按插入顺序排序. */ publicLinkedHashMap(){ super(); accessOrder=false; } /** *根据指定的map生成一个新的HashMap,负载因子使用默认值,初始容量大小为Math.max((int)(m.size()/DEFAULT_LOAD_FACTOR)+1,DEFAULT_INITIAL_CAPACITY) *默认将accessOrder设为false,按插入顺序排序. */ publicLinkedHashMap(Mapm){ super(); accessOrder=false; putMapEntries(m,false); } /** *生成一个空的LinkedHashMap,并指定其容量大小和负载因子, *默认将accessOrder设为true,按访问顺序排序 */ publicLinkedHashMap(intinitialCapacity, floatloadFactor, booleanaccessOrder){ super(initialCapacity,loadFactor); this.accessOrder=accessOrder; }
putMapEntries(m,false)调用父类HashMap的方法,继而根据HashMap的put来实现数据的插入:
/** *ImplementsMap.putAllandMapconstructor * *@parammthemap *@paramevictfalsewheninitiallyconstructingthismap,else *true(relayedtomethodafterNodeInsertion). */ finalvoidputMapEntries(Mapm,booleanevict){ ints=m.size(); if(s>0){ if(table==null){//pre-size floatft=((float)s/loadFactor)+1.0F; intt=((ft<(float)MAXIMUM_CAPACITY)? (int)ft:MAXIMUM_CAPACITY); if(t>threshold) threshold=tableSizeFor(t); } elseif(s>threshold) resize(); for(Map.Entrye:m.entrySet()){ Kkey=e.getKey(); Vvalue=e.getValue(); putVal(hash(key),key,value,false,evict); } } }
存储:
put调用的HashMap的put方法,调用两个空方法,由LinkedHashMap实现
publicVput(Kkey,Vvalue){ returnputVal(hash(key),key,value,false,true); }
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent, booleanevict){ Node[]tab;Node p;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{ Node e;Kk; if(p.hash==hash&& ((k=p.key)==key||(key!=null&&key.equals(k)))) e=p; elseif(pinstanceofTreeNode) e=((TreeNode )p).putTreeVal(this,tab,hash,key,value); else{ for(intbinCount=0;;++binCount){ if((e=p.next)==null){ p.next=newNode(hash,key,value,null); if(binCount>=TREEIFY_THRESHOLD-1)//-1for1st treeifyBin(tab,hash); break; } if(e.hash==hash&& ((k=e.key)==key||(key!=null&&key.equals(k)))) break; p=e; } } if(e!=null){//existingmappingforkey VoldValue=e.value; if(!onlyIfAbsent||oldValue==null) e.value=value; afterNodeAccess(e); returnoldValue; } } ++modCount; if(++size>threshold) resize(); afterNodeInsertion(evict); returnnull; }
在hashmap中红色部分为空实现:
voidafterNodeAccess(Nodep){} voidafterNodeInsertion(booleanevict){}
然后看下LinkedHashMap怎么实现这两方法:
将当前节点e移动到双向链表的尾部。每次LinkedHashMap中有元素被访问时,就会按照访问先后来排序,先访问的在双向链表中靠前,越后访问的越接近尾部。当然只有当accessOrder为true时,才会执行这个操作。
voidafterNodeAccess(Nodee){ LinkedHashMap.Entry last; //若访问顺序为true,且访问的对象不是尾结点 if(accessOrder&&(last=tail)!=e){ //向下转型,记录p的前后结点 LinkedHashMap.Entry p= (LinkedHashMap.Entry )e,b=p.before,a=p.after; //p的后结点为空 p.after=null; //如果p的前结点为空 if(b==null) //a为头结点 head=a; else//p的前结点不为空 //b的后结点为a b.after=a; //p的后结点不为空 if(a!=null) //a的前结点为b a.before=b; else//p的后结点为空 //后结点为最后一个结点 last=b; //若最后一个结点为空 if(last==null) //头结点为p head=p; else{//p链入最后一个结点后面 p.before=last; last.after=p; } //尾结点为p tail=p; //增加结构性修改数量 ++modCount; } }
afterNodeInsertion方法evict为true时删除双向链表的头节点
voidafterNodeInsertion(booleanevict){//possiblyremoveeldest LinkedHashMap.Entryfirst; //头结点不为空,删除头结点 if(evict&&(first=head)!=null&&removeEldestEntry(first)){ Kkey=first.key; removeNode(hash(key),key,null,false,true); } }
删除操作调用HashMap的remove方法实现元素删除,remove调用removeNode,而removeNode有一个方法需要LinkedHashMap来实现:
将e节点从双向链表中删除,更改e前后节点引用关系,使之重新连成完整的双向链表。
voidafterNodeRemoval(Nodee){//unlink LinkedHashMap.Entry p= (LinkedHashMap.Entry )e,b=p.before,a=p.after; p.before=p.after=null; if(b==null) head=a; else b.after=a; if(a==null) tail=b; else a.before=b; }
读取:
e不为空,则获取e的value值并返回。
publicVget(Objectkey){ Nodee; if((e=getNode(hash(key),key))==null) returnnull; if(accessOrder) afterNodeAccess(e); returne.value; }
accessOrder为true,也就是说按照访问顺序获取内容。
voidafterNodeAccess(Nodee){ LinkedHashMap.Entry last; //若访问顺序为true,且访问的对象不是尾结点 if(accessOrder&&(last=tail)!=e){ //向下转型,记录p的前后结点 LinkedHashMap.Entry p= (LinkedHashMap.Entry )e,b=p.before,a=p.after; //p的后结点为空 p.after=null; //如果p的前结点为空 if(b==null) //a为头结点 head=a; else//p的前结点不为空 //b的后结点为a b.after=a; //p的后结点不为空 if(a!=null) //a的前结点为b a.before=b; else//p的后结点为空 //后结点为最后一个结点 last=b; //若最后一个结点为空 if(last==null) //头结点为p head=p; else{//p链入最后一个结点后面 p.before=last; last.after=p; } //尾结点为p tail=p; //增加结构性修改数量 ++modCount; } }
LinkedHashMap的几个迭代器:
抽象类LinkedHashIterator实现具体删除,判断是否存在下个结点,迭代的逻辑。
LinkedKeyIterator继承自LinkedHashIterator,实现了Iterator接口,对LinkedHashMap中的key进行迭代。
LinkedValueIterator继承自LinkedHashIterator,实现了Iterator接口,对LinkedHashMap中的Value进行迭代
LinkedEntryIterator继承自LinkedHashIterator,实现了Iterator接口,对LinkedHashMap中的结点进行迭代
abstractclassLinkedHashIterator{ //下一个节点 LinkedHashMap.Entrynext; //当前节点 LinkedHashMap.Entry current; //期望的修改次数 intexpectedModCount; LinkedHashIterator(){ //next赋值为头结点 next=head; //赋值修改次数 expectedModCount=modCount; //当前节点赋值为空 current=null; } //是否存在下一个结点 publicfinalbooleanhasNext(){ returnnext!=null; } finalLinkedHashMap.Entry nextNode(){ LinkedHashMap.Entry e=next; //检查是否存在结构性改变 if(modCount!=expectedModCount) thrownewConcurrentModificationException(); //结点为nullNoSuchElementException if(e==null) thrownewNoSuchElementException(); //不为null,赋值当前节点 current=e; //赋值下一个结点 next=e.after; returne; } //删除操作 publicfinalvoidremove(){ Node p=current; if(p==null) thrownewIllegalStateException(); if(modCount!=expectedModCount) thrownewConcurrentModificationException(); current=null; Kkey=p.key; //移除结点操作 removeNode(hash(key),key,null,false,false); expectedModCount=modCount; } } finalclassLinkedKeyIteratorextendsLinkedHashIterator implementsIterator { publicfinalKnext(){returnnextNode().getKey();} } finalclassLinkedValueIteratorextendsLinkedHashIterator implementsIterator { publicfinalVnext(){returnnextNode().value;} } finalclassLinkedEntryIteratorextendsLinkedHashIterator implementsIterator >{ publicfinalMap.Entry next(){returnnextNode();} }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。