Java中LinkedHashMap源码解析

2023-09-23 22:52:05 305

概述：

LinkedHashMap实现Map继承HashMap，基于Map的哈希表和链该列表实现，具有可预知的迭代顺序。

LinedHashMap维护着一个运行于所有条目的双重链表结构，该链表定义了迭代顺序，可以是插入或者访问顺序。

LintHashMap的节点对象继承HashMap的节点对象，并增加了前后指针beforeafter：

/**
*LinkedHashMap节点对象
*/
staticclassEntryextendsHashMap.Node{
Entrybefore,after;
Entry(inthash,Kkey,Vvalue,Nodenext){
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;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{
Nodee;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.Entrylast;
//若访问顺序为true，且访问的对象不是尾结点
if(accessOrder&&(last=tail)!=e){
//向下转型，记录p的前后结点
LinkedHashMap.Entryp=
(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.Entryp=
(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.Entrylast;
//若访问顺序为true，且访问的对象不是尾结点
if(accessOrder&&(last=tail)!=e){
//向下转型，记录p的前后结点
LinkedHashMap.Entryp=
(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.Entrycurrent;
//期望的修改次数
intexpectedModCount;

LinkedHashIterator(){
//next赋值为头结点
next=head;
//赋值修改次数
expectedModCount=modCount;
//当前节点赋值为空
current=null;
}
//是否存在下一个结点
publicfinalbooleanhasNext(){
returnnext!=null;
}

finalLinkedHashMap.EntrynextNode(){
LinkedHashMap.Entrye=next;
//检查是否存在结构性改变
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
//结点为nullNoSuchElementException
if(e==null)
thrownewNoSuchElementException();
//不为null,赋值当前节点
current=e;
//赋值下一个结点
next=e.after;
returne;
}
//删除操作
publicfinalvoidremove(){
Nodep=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.Entrynext(){returnnextNode();}
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

Java中LinkedHashMap源码解析

热门推荐

随机推荐