Java中Set&List的迭代器实现步骤解析

2023-08-10 16:27:03 67

List

Java的list又分为ArrayList和LinkedList

ArrayList

privateclassItrimplementsIterator{
intcursor;//indexofnextelementtoreturn
intlastRet=-1;//indexoflastelementreturned;-1ifnosuch
intexpectedModCount=modCount;

//preventcreatingasyntheticconstructor
Itr(){}

publicbooleanhasNext(){
returncursor!=size;
}

@SuppressWarnings("unchecked")
publicEnext(){
checkForComodification();
inti=cursor;
if(i>=size)
thrownewNoSuchElementException();
Object[]elementData=ArrayList.this.elementData;
if(i>=elementData.length)
thrownewConcurrentModificationException();
cursor=i+1;
return(E)elementData[lastRet=i];
}

publicvoidremove(){
if(lastRet<0)
thrownewIllegalStateException();
checkForComodification();

try{
ArrayList.this.remove(lastRet);
cursor=lastRet;
lastRet=-1;
expectedModCount=modCount;
}catch(IndexOutOfBoundsExceptionex){
thrownewConcurrentModificationException();
}
}
}

从代码中我们不难看出迭代器维护上一次return的元素下边和下一个将要return的元素下标，并且迭代器在进行修改操作时会检查在本次操作与上次操作之间是否有迭代器以外的操作，并且适时抛出ConcurrentModificationException(并发修改异常)来阻止更多错误的发生

LinkedList

privateclassListItrimplementsListIterator{
privateNodelastReturned;
privateNodenext;
privateintnextIndex;
privateintexpectedModCount=modCount;

ListItr(intindex){
//assertisPositionIndex(index);
next=(index==size)?null:node(index);
nextIndex=index;
}

publicbooleanhasNext(){
returnnextIndex0;
}

publicEprevious(){
checkForComodification();
if(!hasPrevious())
thrownewNoSuchElementException();

lastReturned=next=(next==null)?last:next.prev;
nextIndex--;
returnlastReturned.item;
}

publicintnextIndex(){
returnnextIndex;
}

publicintpreviousIndex(){
returnnextIndex-1;
}

publicvoidremove(){
checkForComodification();
if(lastReturned==null)
thrownewIllegalStateException();

NodelastNext=lastReturned.next;
unlink(lastReturned);
if(next==lastReturned)
next=lastNext;
else
nextIndex--;
lastReturned=null;
expectedModCount++;
}

publicvoidset(Ee){
if(lastReturned==null)
thrownewIllegalStateException();
checkForComodification();
lastReturned.item=e;
}

publicvoidadd(Ee){
checkForComodification();
lastReturned=null;
if(next==null)
linkLast(e);
else
linkBefore(e,next);
nextIndex++;
expectedModCount++;
}

publicvoidforEachRemaining(Consumeraction){
Objects.requireNonNull(action);
while(modCount==expectedModCount&&nextIndex
LinkedList的迭代器类的实现逻辑与ArrayList大致相近但是其访问元素的方式由原来的下标变为"指针"(Java强引用)
Set


通过看Java源码可以知道Set全家桶基本上都包含了Map,相当于是一种组合的方式
HashSet


构造方法


HashSet有多个构造方法但都是初始化一个HashMap或其子类
/**
*Constructsanew,emptyset;thebacking{@codeHashMap}instancehas
*defaultinitialcapacity(16)andloadfactor(0.75).
*/
publicHashSet(){
map=newHashMap<>();
}

/**
*Constructsanewsetcontainingtheelementsinthespecified
*collection.The{@codeHashMap}iscreatedwithdefaultloadfactor
*(0.75)andaninitialcapacitysufficienttocontaintheelementsin
*thespecifiedcollection.
*
*@paramcthecollectionwhoseelementsaretobeplacedintothisset
*@throwsNullPointerExceptionifthespecifiedcollectionisnull
*/
publicHashSet(Collectionc){
map=newHashMap<>(Math.max((int)(c.size()/.75f)+1,16));
addAll(c);
}

/**
*Constructsanew,emptyset;thebacking{@codeHashMap}instancehas
*thespecifiedinitialcapacityandthespecifiedloadfactor.
*
*@paraminitialCapacitytheinitialcapacityofthehashmap
*@paramloadFactortheloadfactorofthehashmap
*@throwsIllegalArgumentExceptioniftheinitialcapacityisless
*thanzero,oriftheloadfactorisnonpositive
*/
publicHashSet(intinitialCapacity,floatloadFactor){
map=newHashMap<>(initialCapacity,loadFactor);
}

/**
*Constructsanew,emptyset;thebacking{@codeHashMap}instancehas
*thespecifiedinitialcapacityanddefaultloadfactor(0.75).
*
*@paraminitialCapacitytheinitialcapacityofthehashtable
*@throwsIllegalArgumentExceptioniftheinitialcapacityisless
*thanzero
*/
publicHashSet(intinitialCapacity){
map=newHashMap<>(initialCapacity);
}

/**
*Constructsanew,emptylinkedhashset.(Thispackageprivate
*constructorisonlyusedbyLinkedHashSet.)Thebacking
*HashMapinstanceisaLinkedHashMapwiththespecifiedinitial
*capacityandthespecifiedloadfactor.
*
*@paraminitialCapacitytheinitialcapacityofthehashmap
*@paramloadFactortheloadfactorofthehashmap
*@paramdummyignored(distinguishesthis
*constructorfromotherint,floatconstructor.)
*@throwsIllegalArgumentExceptioniftheinitialcapacityisless
*thanzero,oriftheloadfactorisnonpositive
*/
HashSet(intinitialCapacity,floatloadFactor,booleandummy){
map=newLinkedHashMap<>(initialCapacity,loadFactor);
}
iterator方法
该接口在HashSet中的实现相当的简单,可以看到iterator返回了keySet().iterator()
publicIteratoriterator(){
returnmap.keySet().iterator();
}
HashMap的KeySet


从这一处代码可以看到iterator()返回了对象KeyIterator
finalclassKeySetextendsAbstractSet{
publicfinalintsize(){returnsize;}
publicfinalvoidclear(){HashMap.this.clear();}
publicfinalIteratoriterator(){returnnewKeyIterator();}
publicfinalbooleancontains(Objecto){returncontainsKey(o);}
publicfinalbooleanremove(Objectkey){
returnremoveNode(hash(key),key,null,false,true)!=null;
}
publicfinalSpliteratorspliterator(){
returnnewKeySpliterator<>(HashMap.this,0,-1,0,0);
}
publicfinalvoidforEach(Consumeraction){
Node[]tab;
if(action==null)
thrownewNullPointerException();
if(size>0&&(tab=table)!=null){
intmc=modCount;
for(Nodee:tab){
for(;e!=null;e=e.next)
action.accept(e.key);
}
if(modCount!=mc)
thrownewConcurrentModificationException();
}
}
}
HashMap的KeyIterator


KeyIterator是HashIterator一个子类在此一并展示了,这个类从字段结构上跟LinkedList的ListItr还是很像的
获取next的机制Node内部本身包含一个next引用当HashIterator或其子类对象调用方法nextNode时,若该引用非空者优先返回该引用指向的对象,否则掩盖引用的index在HashMap内部的Node数组table中向后找,直到找到一个不为空的引用，或者到table结束也没有找到,那么此时返回空引用
abstractclassHashIterator{
Nodenext;//nextentrytoreturn
Nodecurrent;//currententry
intexpectedModCount;//forfast-fail
intindex;//currentslot

HashIterator(){
expectedModCount=modCount;
Node[]t=table;
current=next=null;
index=0;
if(t!=null&&size>0){//advancetofirstentry
do{}while(indexnextNode(){
Node[]t;
Nodee=next;
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
if(e==null)
thrownewNoSuchElementException();
if((next=(current=e).next)==null&&(t=table)!=null){
do{}while(indexp=current;
if(p==null)
thrownewIllegalStateException();
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
current=null;
removeNode(p.hash,p.key,null,false,false);
expectedModCount=modCount;
}
}

finalclassKeyIteratorextendsHashIterator
implementsIterator{
publicfinalKnext(){returnnextNode().key;}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

Java中Set&List的迭代器实现步骤解析

热门推荐

随机推荐