|
|
java集合框架系列---TreeMap
1、介绍
简介
TreeMap是一个有序的key-value集合，它是通过红黑树实现的。
TreeMap继承于AbstractMap，所以它是一个Map，即一个key-value集合。
TreeMap实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap实现了Cloneable接口，意味着它能被克隆。
TreeMap实现了java.io.Serializable接口，意味着它支持序列化。
TreeMap基于红黑树（Red-Blacktree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的
Comparator进行排序，具体取决于使用的构造方法。
TreeMap的基本操作containsKey、get、put和remove的时间复杂度是log(n)。
TreeMap是非同步的。它的iterator方法返回的迭代器是fail-fastl的。
构造函数
//默认构造函数。使用该构造函数，TreeMap中的元素按照自然排序进行排列。
TreeMap()
//创建的TreeMap包含Map
TreeMap(MapcopyFrom)
//指定Tree的比较器
TreeMap(Comparatorcomparator)
//创建的TreeSet包含copyFrom
TreeMap(SortedMapcopyFrom)
API
EntryceilingEntry(Kkey)
KceilingKey(Kkey)
voidclear()
Objectclone()
Comparatorcomparator()
booleancontainsKey(Objectkey)
NavigableSetdescendingKeySet()
NavigableMapdescendingMap()
Set>entrySet()
EntryfirstEntry()
KfirstKey()
EntryfloorEntry(Kkey)
KfloorKey(Kkey)
Vget(Objectkey)
NavigableMapheadMap(Kto,booleaninclusive)
SortedMapheadMap(KtoExclusive)
EntryhigherEntry(Kkey)
KhigherKey(Kkey)
booleanisEmpty()
SetkeySet()
EntrylastEntry()
KlastKey()
EntrylowerEntry(Kkey)
KlowerKey(Kkey)
NavigableSetnavigableKeySet()
EntrypollFirstEntry()
EntrypollLastEntry()
Vput(Kkey,Vvalue)
Vremove(Objectkey)
intsize()
SortedMapsubMap(KfromInclusive,KtoExclusive)
NavigableMapsubMap(Kfrom,booleanfromInclusive,Kto,booleantoInclusive)
NavigableMaptailMap(Kfrom,booleaninclusive)
SortedMaptailMap(KfromInclusive)
2、数据结构
从图中可以看出：
(01)TreeMap实现继承于AbstractMap，并且实现了NavigableMap接口。
(02)TreeMap的本质是R-BTree(红黑树)，它包含几个重要的成员变量：root,size,comparator。
root是红黑数的根节点。它是Entry类型，Entry是红黑数的节点，它包含了红黑数的6个基本组成成分：key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序，Entry节点包含的内容为value。
红黑数排序时，根据Entry中的key进行排序；Entry中的key比较大小是根据比较器comparator来进行判断的。
size是红黑数中节点的个数。
红黑数树参见：红黑树介绍
3、源码分析
源码：
packagejava.util;
publicclassTreeMap
extendsAbstractMap
implementsNavigableMap,Cloneable,java.io.Serializable
{
//比较器。用来给TreeMap排序
privatefinalComparatorcomparator;
//TreeMap是红黑树实现的，root是红黑书的根节点
privatetransientEntryroot=null;
//红黑树的节点总数
privatetransientintsize=0;
//记录红黑树的修改次数
privatetransientintmodCount=0;
//默认构造函数
publicTreeMap(){
comparator=null;
}
//带比较器的构造函数
publicTreeMap(Comparatorcomparator){
this.comparator=comparator;
}
//带Map的构造函数，Map会成为TreeMap的子集
publicTreeMap(Mapm){
comparator=null;
putAll(m);
}
//带SortedMap的构造函数，SortedMap会成为TreeMap的子集
publicTreeMap(SortedMapm){
comparator=m.comparator();
try{
buildFromSorted(m.size(),m.entrySet().iterator(),null,null);
}catch(java.io.IOExceptioncannotHappen){
}catch(ClassNotFoundExceptioncannotHappen){
}
}
publicintsize(){
returnsize;
}
//返回TreeMap中是否保护“键(key)”
publicbooleancontainsKey(Objectkey){
returngetEntry(key)!=null;
}
//返回TreeMap中是否保护"值(value)"
publicbooleancontainsValue(Objectvalue){
//getFirstEntry()是返回红黑树的第一个节点
//successor(e)是获取节点e的后继节点
for(Entrye=getFirstEntry();e!=null;e=successor(e))
if(valEquals(value,e.value))
returntrue;
returnfalse;
}
//获取“键(key)”对应的“值(value)”
publicVget(Objectkey){
//获取“键”为key的节点(p)
Entryp=getEntry(key);
//若节点(p)为null，返回null；否则，返回节点对应的值
return(p==null?null:p.value);
}
publicComparatorcomparator(){
returncomparator;
}
//获取第一个节点对应的key
publicKfirstKey(){
returnkey(getFirstEntry());
}
//获取最后一个节点对应的key
publicKlastKey(){
returnkey(getLastEntry());
}
//将map中的全部节点添加到TreeMap中
publicvoidputAll(Mapmap){
//获取map的大小
intmapSize=map.size();
//如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value对”
if(size==0&&mapSize!=0&&mapinstanceofSortedMap){
Comparatorc=((SortedMap)map).comparator();
//如果TreeMap和map的比较器相等；
//则将map的元素全部拷贝到TreeMap中，然后返回！
if(c==comparator||(c!=null&&c.equals(comparator))){
++modCount;
try{
buildFromSorted(mapSize,map.entrySet().iterator(),
null,null);
}catch(java.io.IOExceptioncannotHappen){
}catch(ClassNotFoundExceptioncannotHappen){
}
return;
}
}
//调用AbstractMap中的putAll();
//AbstractMap中的putAll()又会调用到TreeMap的put()
super.putAll(map);
}
//获取TreeMap中“键”为key的节点
finalEntrygetEntry(Objectkey){
//若“比较器”为null，则通过getEntryUsingComparator()获取“键”为key的节点
if(comparator!=null)
returngetEntryUsingComparator(key);
if(key==null)
thrownewNullPointerException();
Comparablek=(Comparable)key;
//将p设为根节点
Entryp=root;
while(p!=null){
intcmp=k.compareTo(p.key);
//若“p的key”
if(cmp<0)
p=p.left;
//若“p的key”>key，则p=“p的左孩子”
elseif(cmp>0)
p=p.right;
//若“p的key”=key，则返回节点p
else
returnp;
}
returnnull;
}
//获取TreeMap中“键”为key的节点(对应TreeMap的比较器不是null的情况)
finalEntrygetEntryUsingComparator(Objectkey){
Kk=(K)key;
Comparatorcpr=comparator;
if(cpr!=null){
//将p设为根节点
Entryp=root;
while(p!=null){
intcmp=cpr.compare(k,p.key);
//若“p的key”
if(cmp<0)
p=p.left;
//若“p的key”>key，则p=“p的左孩子”
elseif(cmp>0)
p=p.right;
//若“p的key”=key，则返回节点p
else
returnp;
}
}
returnnull;
}
//获取TreeMap中不小于key的最小的节点；
//若不存在(即TreeMap中所有节点的键都比key大)，就返回null
finalEntrygetCeilingEntry(Kkey){
Entryp=root;
while(p!=null){
intcmp=compare(key,p.key);
//情况一：若“p的key”>key。
//若p存在左孩子，则设p=“p的左孩子”；
//否则，返回p
if(cmp<0){
if(p.left!=null)
p=p.left;
else
returnp;
//情况二：若“p的key”
}elseif(cmp>0){
//若p存在右孩子，则设p=“p的右孩子”
if(p.right!=null){
p=p.right;
}else{
//若p不存在右孩子，则找出p的后继节点，并返回
//注意：这里返回的“p的后继节点”有2种可能性：第一，null；第二，TreeMap中大于key的最小的节点。
//理解这一点的核心是，getCeilingEntry是从root开始遍历的。
//若getCeilingEntry能走到这一步，那么，它之前“已经遍历过的节点的key”都>key。
//能理解上面所说的，那么就很容易明白，为什么“p的后继节点”又2种可能性了。
Entryparent=p.parent;
Entrych=p;
while(parent!=null&&ch==parent.right){
ch=parent;
parent=parent.parent;
}
returnparent;
}
//情况三：若“p的key”=key。
}else
returnp;
}
returnnull;
}
//获取TreeMap中不大于key的最大的节点；
//若不存在(即TreeMap中所有节点的键都比key小)，就返回null
//getFloorEntry的原理和getCeilingEntry类似，这里不再多说。
finalEntrygetFloorEntry(Kkey){
Entryp=root;
while(p!=null){
intcmp=compare(key,p.key);
if(cmp>0){
if(p.right!=null)
p=p.right;
else
returnp;
}elseif(cmp<0){
if(p.left!=null){
p=p.left;
}else{
Entryparent=p.parent;
Entrych=p;
while(parent!=null&&ch==parent.left){
ch=parent;
parent=parent.parent;
}
returnparent;
}
}else
returnp;
}
returnnull;
}
//获取TreeMap中大于key的最小的节点。
//若不存在，就返回null。
//请参照getCeilingEntry来对getHigherEntry进行理解。
finalEntrygetHigherEntry(Kkey){
Entryp=root;
while(p!=null){
intcmp=compare(key,p.key);
if(cmp<0){
if(p.left!=null)
p=p.left;
else
returnp;
}else{
if(p.right!=null){
p=p.right;
}else{
Entryparent=p.parent;
Entrych=p;
while(parent!=null&&ch==parent.right){
ch=parent;
parent=parent.parent;
}
returnparent;
}
}
}
returnnull;
}
//获取TreeMap中小于key的最大的节点。
//若不存在，就返回null。
//请参照getCeilingEntry来对getLowerEntry进行理解。
finalEntrygetLowerEntry(Kkey){
Entryp=root;
while(p!=null){
intcmp=compare(key,p.key);
if(cmp>0){
if(p.right!=null)
p=p.right;
else
returnp;
}else{
if(p.left!=null){
p=p.left;
}else{
Entryparent=p.parent;
Entrych=p;
while(parent!=null&&ch==parent.left){
ch=parent;
parent=parent.parent;
}
returnparent;
}
}
}
returnnull;
}
//将“key,value”添加到TreeMap中
//理解TreeMap的前提是掌握“红黑树”。
//若理解“红黑树中添加节点”的算法，则很容易理解put。
publicVput(Kkey,Vvalue){
Entryt=root;
//若红黑树为空，则插入根节点
if(t==null){
//TBD:
//5045147:(coll)AddingnulltoanemptyTreeSetshould
//throwNullPointerException
//
//compare(key,key);//typecheck
root=newEntry(key,value,null);
size=1;
modCount++;
returnnull;
}
intcmp;
Entryparent;
//splitcomparatorandcomparablepaths
Comparatorcpr=comparator;
//在二叉树(红黑树是特殊的二叉树)中，找到(key,value)的插入位置。
//红黑树是以key来进行排序的，所以这里以key来进行查找。
if(cpr!=null){
do{
parent=t;
cmp=cpr.compare(key,t.key);
if(cmp<0)
t=t.left;
elseif(cmp>0)
t=t.right;
else
returnt.setValue(value);
}while(t!=null);
}
else{
if(key==null)
thrownewNullPointerException();
Comparablek=(Comparable)key;
do{
parent=t;
cmp=k.compareTo(t.key);
if(cmp<0)
t=t.left;
elseif(cmp>0)
t=t.right;
else
returnt.setValue(value);
}while(t!=null);
}
//新建红黑树的节点(e)
Entrye=newEntry(key,value,parent);
if(cmp<0)
parent.left=e;
else
parent.right=e;
//红黑树插入节点后，不再是一颗红黑树；
//这里通过fixAfterInsertion的处理，来恢复红黑树的特性。
fixAfterInsertion(e);
size++;
modCount++;
returnnull;
}
//删除TreeMap中的键为key的节点，并返回节点的值
publicVremove(Objectkey){
//找到键为key的节点
Entryp=getEntry(key);
if(p==null)
returnnull;
//保存节点的值
VoldValue=p.value;
//删除节点
deleteEntry(p);
returnoldValue;
}
//清空红黑树
publicvoidclear(){
modCount++;
size=0;
root=null;
}
//克隆一个TreeMap，并返回Object对象
publicObjectclone(){
TreeMapclone=null;
try{
clone=(TreeMap)super.clone();
}catch(CloneNotSupportedExceptione){
thrownewInternalError();
}
//Putcloneinto"virgin"state(exceptforcomparator)
clone.root=null;
clone.size=0;
clone.modCount=0;
clone.entrySet=null;
clone.navigableKeySet=null;
clone.descendingMap=null;
//Initializeclonewithourmappings
try{
clone.buildFromSorted(size,entrySet().iterator(),null,null);
}catch(java.io.IOExceptioncannotHappen){
}catch(ClassNotFoundExceptioncannotHappen){
}
returnclone;
}
//获取第一个节点(对外接口)。
publicMap.EntryfirstEntry(){
returnexportEntry(getFirstEntry());
}
//获取最后一个节点(对外接口)。
publicMap.EntrylastEntry(){
returnexportEntry(getLastEntry());
}
//获取第一个节点，并将改节点从TreeMap中删除。
publicMap.EntrypollFirstEntry(){
//获取第一个节点
Entryp=getFirstEntry();
Map.Entryresult=exportEntry(p);
//删除第一个节点
if(p!=null)
deleteEntry(p);
returnresult;
}
//获取最后一个节点，并将改节点从TreeMap中删除。
publicMap.EntrypollLastEntry(){
//获取最后一个节点
Entryp=getLastEntry();
Map.Entryresult=exportEntry(p);
//删除最后一个节点
if(p!=null)
deleteEntry(p);
returnresult;
}
//返回小于key的最大的键值对，没有的话返回null
publicMap.EntrylowerEntry(Kkey){
returnexportEntry(getLowerEntry(key));
}
//返回小于key的最大的键值对所对应的KEY，没有的话返回null
publicKlowerKey(Kkey){
returnkeyOrNull(getLowerEntry(key));
}
//返回不大于key的最大的键值对，没有的话返回null
publicMap.EntryfloorEntry(Kkey){
returnexportEntry(getFloorEntry(key));
}
//返回不大于key的最大的键值对所对应的KEY，没有的话返回null
publicKfloorKey(Kkey){
returnkeyOrNull(getFloorEntry(key));
}
//返回不小于key的最小的键值对，没有的话返回null
publicMap.EntryceilingEntry(Kkey){
returnexportEntry(getCeilingEntry(key));
}
//返回不小于key的最小的键值对所对应的KEY，没有的话返回null
publicKceilingKey(Kkey){
returnkeyOrNull(getCeilingEntry(key));
}
//返回大于key的最小的键值对，没有的话返回null
publicMap.EntryhigherEntry(Kkey){
returnexportEntry(getHigherEntry(key));
}
//返回大于key的最小的键值对所对应的KEY，没有的话返回null
publicKhigherKey(Kkey){
returnkeyOrNull(getHigherEntry(key));
}
//TreeMap的红黑树节点对应的集合
privatetransientEntrySetentrySet=null;
//KeySet为KeySet导航类
privatetransientKeySetnavigableKeySet=null;
//descendingMap为键值对的倒序“映射”
privatetransientNavigableMapdescendingMap=null;
//返回TreeMap的“键的集合”
publicSetkeySet(){
returnnavigableKeySet();
}
//获取“可导航”的Key的集合
//实际上是返回KeySet类的对象。
publicNavigableSetnavigableKeySet(){
KeySetnks=navigableKeySet;
return(nks!=null)?nks:(navigableKeySet=newKeySet(this));
}
//返回“TreeMap的值对应的集合”
publicCollectionvalues(){
Collectionvs=values;
return(vs!=null)?vs:(values=newValues());
}
//获取TreeMap的Entry的集合，实际上是返回EntrySet类的对象。
publicSet>entrySet(){
EntrySetes=entrySet;
return(es!=null)?es:(entrySet=newEntrySet());
}
//获取TreeMap的降序Map
//实际上是返回DescendingSubMap类的对象
publicNavigableMapdescendingMap(){
NavigableMapkm=descendingMap;
return(km!=null)?km:
(descendingMap=newDescendingSubMap(this,
true,null,true,
true,null,true));
}
//获取TreeMap的子Map
//范围是从fromKey到toKey；fromInclusive是是否包含fromKey的标记，toInclusive是是否包含toKey的标记
publicNavigableMapsubMap(KfromKey,booleanfromInclusive,
KtoKey,booleantoInclusive){
returnnewAscendingSubMap(this,
false,fromKey,fromInclusive,
false,toKey,toInclusive);
}
//获取“Map的头部”
//范围从第一个节点到toKey,inclusive是是否包含toKey的标记
publicNavigableMapheadMap(KtoKey,booleaninclusive){
returnnewAscendingSubMap(this,
true,null,true,
false,toKey,inclusive);
}
//获取“Map的尾部”。
//范围是从fromKey到最后一个节点，inclusive是是否包含fromKey的标记
publicNavigableMaptailMap(KfromKey,booleaninclusive){
returnnewAscendingSubMap(this,
false,fromKey,inclusive,
true,null,true);
}
//获取“子Map”。
//范围是从fromKey(包括)到toKey(不包括)
publicSortedMapsubMap(KfromKey,KtoKey){
returnsubMap(fromKey,true,toKey,false);
}
//获取“Map的头部”。
//范围从第一个节点到toKey(不包括)
publicSortedMapheadMap(KtoKey){
returnheadMap(toKey,false);
}
//获取“Map的尾部”。
//范围是从fromKey(包括)到最后一个节点
publicSortedMaptailMap(KfromKey){
returntailMap(fromKey,true);
}
//”TreeMap的值的集合“对应的类，它集成于AbstractCollection
classValuesextendsAbstractCollection{
//返回迭代器
publicIteratoriterator(){
returnnewValueIterator(getFirstEntry());
}
//返回个数
publicintsize(){
returnTreeMap.this.size();
}
//"TreeMap的值的集合"中是否包含"对象o"
publicbooleancontains(Objecto){
returnTreeMap.this.containsValue(o);
}
//删除"TreeMap的值的集合"中的"对象o"
publicbooleanremove(Objecto){
for(Entrye=getFirstEntry();e!=null;e=successor(e)){
if(valEquals(e.getValue(),o)){
deleteEntry(e);
returntrue;
}
}
returnfalse;
}
//清空删除"TreeMap的值的集合"
publicvoidclear(){
TreeMap.this.clear();
}
}
//EntrySet是“TreeMap的所有键值对组成的集合”，
//EntrySet集合的单位是单个“键值对”。
classEntrySetextendsAbstractSet>{
publicIterator>iterator(){
returnnewEntryIterator(getFirstEntry());
}
//EntrySet中是否包含“键值对Object”
publicbooleancontains(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entryentry=(Map.Entry)o;
Vvalue=entry.getValue();
Entryp=getEntry(entry.getKey());
returnp!=null&&valEquals(p.getValue(),value);
}
//删除EntrySet中的“键值对Object”
publicbooleanremove(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entryentry=(Map.Entry)o;
Vvalue=entry.getValue();
Entryp=getEntry(entry.getKey());
if(p!=null&&valEquals(p.getValue(),value)){
deleteEntry(p);
returntrue;
}
returnfalse;
}
//返回EntrySet中元素个数
publicintsize(){
returnTreeMap.this.size();
}
//清空EntrySet
publicvoidclear(){
TreeMap.this.clear();
}
}
//返回“TreeMap的KEY组成的迭代器(顺序)”
IteratorkeyIterator(){
returnnewKeyIterator(getFirstEntry());
}
//返回“TreeMap的KEY组成的迭代器(逆序)”
IteratordescendingKeyIterator(){
returnnewDescendingKeyIterator(getLastEntry());
}
//KeySet是“TreeMap中所有的KEY组成的集合”
//KeySet继承于AbstractSet，而且实现了NavigableSet接口。
staticfinalclassKeySetextendsAbstractSetimplementsNavigableSet{
//NavigableMap成员，KeySet是通过NavigableMap实现的
privatefinalNavigableMapm;
KeySet(NavigableMapmap){m=map;}
//升序迭代器
publicIteratoriterator(){
//若是TreeMap对象，则调用TreeMap的迭代器keyIterator()
//否则，调用TreeMap子类NavigableSubMap的迭代器keyIterator()
if(minstanceofTreeMap)
return((TreeMap)m).keyIterator();
else
return(Iterator)(((TreeMap.NavigableSubMap)m).keyIterator());
}
//降序迭代器
publicIteratordescendingIterator(){
//若是TreeMap对象，则调用TreeMap的迭代器descendingKeyIterator()
//否则，调用TreeMap子类NavigableSubMap的迭代器descendingKeyIterator()
if(minstanceofTreeMap)
return((TreeMap)m).descendingKeyIterator();
else
return(Iterator)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
}
publicintsize(){returnm.size();}
publicbooleanisEmpty(){returnm.isEmpty();}
publicbooleancontains(Objecto){returnm.containsKey(o);}
publicvoidclear(){m.clear();}
publicElower(Ee){returnm.lowerKey(e);}
publicEfloor(Ee){returnm.floorKey(e);}
publicEceiling(Ee){returnm.ceilingKey(e);}
publicEhigher(Ee){returnm.higherKey(e);}
publicEfirst(){returnm.firstKey();}
publicElast(){returnm.lastKey();}
publicComparatorcomparator(){returnm.comparator();}
publicEpollFirst(){
Map.Entrye=m.pollFirstEntry();
returne==null?null:e.getKey();
}
publicEpollLast(){
Map.Entrye=m.pollLastEntry();
returne==null?null:e.getKey();
}
publicbooleanremove(Objecto){
intoldSize=size();
m.remove(o);
returnsize()!=oldSize;
}
publicNavigableSetsubSet(EfromElement,booleanfromInclusive,
EtoElement,booleantoInclusive){
returnnewTreeSet(m.subMap(fromElement,fromInclusive,
toElement,toInclusive));
}
publicNavigableSetheadSet(EtoElement,booleaninclusive){
returnnewTreeSet(m.headMap(toElement,inclusive));
}
publicNavigableSettailSet(EfromElement,booleaninclusive){
returnnewTreeSet(m.tailMap(fromElement,inclusive));
}
publicSortedSetsubSet(EfromElement,EtoElement){
returnsubSet(fromElement,true,toElement,false);
}
publicSortedSetheadSet(EtoElement){
returnheadSet(toElement,false);
}
publicSortedSettailSet(EfromElement){
returntailSet(fromElement,true);
}
publicNavigableSetdescendingSet(){
returnnewTreeSet(m.descendingMap());
}
}
//它是TreeMap中的一个抽象迭代器，实现了一些通用的接口。
abstractclassPrivateEntryIteratorimplementsIterator{
//下一个元素
Entrynext;
//上一次返回元素
EntrylastReturned;
//期望的修改次数，用于实现fast-fail机制
intexpectedModCount;
PrivateEntryIterator(Entryfirst){
expectedModCount=modCount;
lastReturned=null;
next=first;
}
publicfinalbooleanhasNext(){
returnnext!=null;
}
//获取下一个节点
finalEntrynextEntry(){
Entrye=next;
if(e==null)
thrownewNoSuchElementException();
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
next=successor(e);
lastReturned=e;
returne;
}
//获取上一个节点
finalEntryprevEntry(){
Entrye=next;
if(e==null)
thrownewNoSuchElementException();
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
next=predecessor(e);
lastReturned=e;
returne;
}
//删除当前节点
publicvoidremove(){
if(lastReturned==null)
thrownewIllegalStateException();
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
//这里重点强调一下“为什么当lastReturned的左右孩子都不为空时，要将其赋值给next”。
//目的是为了“删除lastReturned节点之后，next节点指向的仍然是下一个节点”。
//根据“红黑树”的特性可知：
//当被删除节点有两个儿子时。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
//这意味着“当被删除节点有两个儿子时，删除当前节点之后，''新的当前节点''实际上是‘原有的后继节点(即下一个节点)’”。
//而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点；能继续遍历红黑树。
if(lastReturned.left!=null&&lastReturned.right!=null)
next=lastReturned;
deleteEntry(lastReturned);
expectedModCount=modCount;
lastReturned=null;
}
}
//TreeMap的Entry对应的迭代器
finalclassEntryIteratorextendsPrivateEntryIterator>{
EntryIterator(Entryfirst){
super(first);
}
publicMap.Entrynext(){
returnnextEntry();
}
}
//TreeMap的Value对应的迭代器
finalclassValueIteratorextendsPrivateEntryIterator{
ValueIterator(Entryfirst){
super(first);
}
publicVnext(){
returnnextEntry().value;
}
}
//reeMap的KEY组成的迭代器(顺序)
finalclassKeyIteratorextendsPrivateEntryIterator{
KeyIterator(Entryfirst){
super(first);
}
publicKnext(){
returnnextEntry().key;
}
}
//TreeMap的KEY组成的迭代器(逆序)
finalclassDescendingKeyIteratorextendsPrivateEntryIterator{
DescendingKeyIterator(Entryfirst){
super(first);
}
publicKnext(){
returnprevEntry().key;
}
}
//比较两个对象的大小
finalintcompare(Objectk1,Objectk2){
returncomparator==null?((Comparable)k1).compareTo((K)k2)
:comparator.compare((K)k1,(K)k2);
}
//判断两个对象是否相等
finalstaticbooleanvalEquals(Objecto1,Objecto2){
return(o1==null?o2==null:o1.equals(o2));
}
//返回“Key-Value键值对”的一个简单拷贝(AbstractMap.SimpleImmutableEntry对象)
//可用来读取“键值对”的值
staticMap.EntryexportEntry(TreeMap.Entrye){
returne==null?null:
newAbstractMap.SimpleImmutableEntry(e);
}
//若“键值对”不为null，则返回KEY；否则，返回null
staticKkeyOrNull(TreeMap.Entrye){
returne==null?null:e.key;
}
//若“键值对”不为null，则返回KEY；否则，抛出异常
staticKkey(Entrye){
if(e==null)
thrownewNoSuchElementException();
returne.key;
}
//TreeMap的SubMap，它一个抽象类，实现了公共操作。
//它包括了"(升序)AscendingSubMap"和"(降序)DescendingSubMap"两个子类。
staticabstractclassNavigableSubMapextendsAbstractMap
implementsNavigableMap,java.io.Serializable{
//TreeMap的拷贝
finalTreeMapm;
//lo是“子Map范围的最小值”，hi是“子Map范围的最大值”；
//loInclusive是“是否包含lo的标记”，hiInclusive是“是否包含hi的标记”
//fromStart是“表示是否从第一个节点开始计算”，
//toEnd是“表示是否计算到最后一个节点”
finalKlo,hi;
finalbooleanfromStart,toEnd;
finalbooleanloInclusive,hiInclusive;
//构造函数
NavigableSubMap(TreeMapm,
booleanfromStart,Klo,booleanloInclusive,
booleantoEnd,Khi,booleanhiInclusive){
if(!fromStart&&!toEnd){
if(m.compare(lo,hi)>0)
thrownewIllegalArgumentException("fromKey>toKey");
}else{
if(!fromStart)//typecheck
m.compare(lo,lo);
if(!toEnd)
m.compare(hi,hi);
}
this.m=m;
this.fromStart=fromStart;
this.lo=lo;
this.loInclusive=loInclusive;
this.toEnd=toEnd;
this.hi=hi;
this.hiInclusive=hiInclusive;
}
//判断key是否太小
finalbooleantooLow(Objectkey){
//若该SubMap不包括“起始节点”，
//并且，“key小于最小键(lo)”或者“key等于最小键(lo)，但最小键却没包括在该SubMap内”
//则判断key太小。其余情况都不是太小！
if(!fromStart){
intc=m.compare(key,lo);
if(c<0||(c==0&&!loInclusive))
returntrue;
}
returnfalse;
}
//判断key是否太大
finalbooleantooHigh(Objectkey){
//若该SubMap不包括“结束节点”，
//并且，“key大于最大键(hi)”或者“key等于最大键(hi)，但最大键却没包括在该SubMap内”
//则判断key太大。其余情况都不是太大！
if(!toEnd){
intc=m.compare(key,hi);
if(c>0||(c==0&&!hiInclusive))
returntrue;
}
returnfalse;
}
//判断key是否在“lo和hi”开区间范围内
finalbooleaninRange(Objectkey){
return!tooLow(key)&&!tooHigh(key);
}
//判断key是否在封闭区间内
finalbooleaninClosedRange(Objectkey){
return(fromStart||m.compare(key,lo)>=0)
&&(toEnd||m.compare(hi,key)>=0);
}
//判断key是否在区间内,inclusive是区间开关标志
finalbooleaninRange(Objectkey,booleaninclusive){
returninclusive?inRange(key):inClosedRange(key);
}
//返回最低的Entry
finalTreeMap.EntryabsLowest(){
//若“包含起始节点”，则调用getFirstEntry()返回第一个节点
//否则的话，若包括lo，则调用getCeilingEntry(lo)获取大于/等于lo的最小的Entry;
//否则，调用getHigherEntry(lo)获取大于lo的最小Entry
TreeMap.Entrye=
(fromStart?m.getFirstEntry():
(loInclusive?m.getCeilingEntry(lo):
m.getHigherEntry(lo)));
return(e==null||tooHigh(e.key))?null:e;
}
//返回最高的Entry
finalTreeMap.EntryabsHighest(){
//若“包含结束节点”，则调用getLastEntry()返回最后一个节点
//否则的话，若包括hi，则调用getFloorEntry(hi)获取小于/等于hi的最大的Entry;
//否则，调用getLowerEntry(hi)获取大于hi的最大Entry
TreeMap.Entrye=
TreeMap.Entrye=
(toEnd?m.getLastEntry():
(hiInclusive?m.getFloorEntry(hi):
m.getLowerEntry(hi)));
return(e==null||tooLow(e.key))?null:e;
}
//返回"大于/等于key的最小的Entry"
finalTreeMap.EntryabsCeiling(Kkey){
//只有在“key太小”的情况下，absLowest()返回的Entry才是“大于/等于key的最小Entry”
//其它情况下不行。例如，当包含“起始节点”时，absLowest()返回的是最小Entry了！
if(tooLow(key))
returnabsLowest();
//获取“大于/等于key的最小Entry”
TreeMap.Entrye=m.getCeilingEntry(key);
return(e==null||tooHigh(e.key))?null:e;
}
//返回"大于key的最小的Entry"
finalTreeMap.EntryabsHigher(Kkey){
//只有在“key太小”的情况下，absLowest()返回的Entry才是“大于key的最小Entry”
//其它情况下不行。例如，当包含“起始节点”时，absLowest()返回的是最小Entry了,而不一定是“大于key的最小Entry”！
if(tooLow(key))
returnabsLowest();
//获取“大于key的最小Entry”
TreeMap.Entrye=m.getHigherEntry(key);
return(e==null||tooHigh(e.key))?null:e;
}
//返回"小于/等于key的最大的Entry"
finalTreeMap.EntryabsFloor(Kkey){
//只有在“key太大”的情况下，(absHighest)返回的Entry才是“小于/等于key的最大Entry”
//其它情况下不行。例如，当包含“结束节点”时，absHighest()返回的是最大Entry了！
if(tooHigh(key))
returnabsHighest();
//获取"小于/等于key的最大的Entry"
TreeMap.Entrye=m.getFloorEntry(key);
return(e==null||tooLow(e.key))?null:e;
}
//返回"小于key的最大的Entry"
finalTreeMap.EntryabsLower(Kkey){
//只有在“key太大”的情况下，(absHighest)返回的Entry才是“小于key的最大Entry”
//其它情况下不行。例如，当包含“结束节点”时，absHighest()返回的是最大Entry了,而不一定是“小于key的最大Entry”！
if(tooHigh(key))
returnabsHighest();
//获取"小于key的最大的Entry"
TreeMap.Entrye=m.getLowerEntry(key);
return(e==null||tooLow(e.key))?null:e;
}
//返回“大于最大节点中的最小节点”，不存在的话，返回null
finalTreeMap.EntryabsHighFence(){
return(toEnd?null:(hiInclusive?
m.getHigherEntry(hi):
m.getCeilingEntry(hi)));
}
//返回“小于最小节点中的最大节点”，不存在的话，返回null
finalTreeMap.EntryabsLowFence(){
return(fromStart?null:(loInclusive?
m.getLowerEntry(lo):
m.getFloorEntry(lo)));
}
//下面几个abstract方法是需要NavigableSubMap的实现类实现的方法
abstractTreeMap.EntrysubLowest();
abstractTreeMap.EntrysubHighest();
abstractTreeMap.EntrysubCeiling(Kkey);
abstractTreeMap.EntrysubHigher(Kkey);
abstractTreeMap.EntrysubFloor(Kkey);
abstractTreeMap.EntrysubLower(Kkey);
//返回“顺序”的键迭代器
abstractIteratorkeyIterator();
//返回“逆序”的键迭代器
abstractIteratordescendingKeyIterator();
//返回SubMap是否为空。空的话，返回true，否则返回false
publicbooleanisEmpty(){
return(fromStart&&toEnd)?m.isEmpty():entrySet().isEmpty();
}
//返回SubMap的大小
publicintsize(){
return(fromStart&&toEnd)?m.size():entrySet().size();
}
//返回SubMap是否包含键key
publicfinalbooleancontainsKey(Objectkey){
returninRange(key)&&m.containsKey(key);
}
//将key-value插入SubMap中
publicfinalVput(Kkey,Vvalue){
if(!inRange(key))
thrownewIllegalArgumentException("keyoutofrange");
returnm.put(key,value);
}
//获取key对应值
publicfinalVget(Objectkey){
return!inRange(key)?null:m.get(key);
}
//删除key对应的键值对
publicfinalVremove(Objectkey){
return!inRange(key)?null:m.remove(key);
}
//获取“大于/等于key的最小键值对”
publicfinalMap.EntryceilingEntry(Kkey){
returnexportEntry(subCeiling(key));
}
//获取“大于/等于key的最小键”
publicfinalKceilingKey(Kkey){
returnkeyOrNull(subCeiling(key));
}
//获取“大于key的最小键值对”
publicfinalMap.EntryhigherEntry(Kkey){
returnexportEntry(subHigher(key));
}
//获取“大于key的最小键”
publicfinalKhigherKey(Kkey){
returnkeyOrNull(subHigher(key));
}
//获取“小于/等于key的最大键值对”
publicfinalMap.EntryfloorEntry(Kkey){
returnexportEntry(subFloor(key));
}
//获取“小于/等于key的最大键”
publicfinalKfloorKey(Kkey){
returnkeyOrNull(subFloor(key));
}
//获取“小于key的最大键值对”
publicfinalMap.EntrylowerEntry(Kkey){
returnexportEntry(subLower(key));
}
//获取“小于key的最大键”
publicfinalKlowerKey(Kkey){
returnkeyOrNull(subLower(key));
}
//获取"SubMap的第一个键"
publicfinalKfirstKey(){
returnkey(subLowest());
}
//获取"SubMap的最后一个键"
publicfinalKlastKey(){
returnkey(subHighest());
}
//获取"SubMap的第一个键值对"
publicfinalMap.EntryfirstEntry(){
returnexportEntry(subLowest());
}
//获取"SubMap的最后一个键值对"
publicfinalMap.EntrylastEntry(){
returnexportEntry(subHighest());
}
//返回"SubMap的第一个键值对"，并从SubMap中删除改键值对
publicfinalMap.EntrypollFirstEntry(){
TreeMap.Entrye=subLowest();
Map.Entryresult=exportEntry(e);
if(e!=null)
m.deleteEntry(e);
returnresult;
}
//返回"SubMap的最后一个键值对"，并从SubMap中删除改键值对
publicfinalMap.EntrypollLastEntry(){
TreeMap.Entrye=subHighest();
Map.Entryresult=exportEntry(e);
if(e!=null)
m.deleteEntry(e);
returnresult;
}
//Views
transientNavigableMapdescendingMapView=null;
transientEntrySetViewentrySetView=null;
transientKeySetnavigableKeySetView=null;
//返回NavigableSet对象，实际上返回的是当前对象的"Key集合"。
publicfinalNavigableSetnavigableKeySet(){
KeySetnksv=navigableKeySetView;
return(nksv!=null)?nksv:
(navigableKeySetView=newTreeMap.KeySet(this));
}
//返回"Key集合"对象
publicfinalSetkeySet(){
returnnavigableKeySet();
}
//返回“逆序”的Key集合
publicNavigableSetdescendingKeySet(){
returndescendingMap().navigableKeySet();
}
//排列fromKey(包含)到toKey(不包含)的子map
publicfinalSortedMapsubMap(KfromKey,KtoKey){
returnsubMap(fromKey,true,toKey,false);
}
//返回当前Map的头部(从第一个节点到toKey,不包括toKey)
publicfinalSortedMapheadMap(KtoKey){
returnheadMap(toKey,false);
}
//返回当前Map的尾部[从fromKey(包括fromKeyKey)到最后一个节点]
publicfinalSortedMaptailMap(KfromKey){
returntailMap(fromKey,true);
}
//Map的Entry的集合
abstractclassEntrySetViewextendsAbstractSet>{
privatetranwww.sm136.comsientintsize=-1,sizeModCount;
//获取EntrySet的大小
publicintsize(){
//若SubMap是从“开始节点”到“结尾节点”，则SubMap大小就是原TreeMap的大小
if(fromStart&&toEnd)
returnm.size();
//若SubMap不是从“开始节点”到“结尾节点”，则调用iterator()遍历EntrySetView中的元素
if(size==-1||sizeModCount!=m.modCount){
sizeModCount=m.modCount;
size=0;
Iteratori=iterator();
while(i.hasNext()){
size++;
i.next();
}
}
returnsize;
}
//判断EntrySetView是否为空
publicbooleanisEmpty(){
TreeMap.Entryn=absLowest();
returnn==null||tooHigh(n.key);
}
//判断EntrySetView是否包含Object
publicbooleancontains(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entryentry=(Map.Entry)o;
Kkey=entry.getKey();
if(!inRange(key))
returnfalse;
TreeMap.Entrynode=m.getEntry(key);
returnnode!=null&&
valEquals(node.getValue(),entry.getValue());
}
//从EntrySetView中删除Object
publicbooleanremove(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entryentry=(Map.Entry)o;
Kkey=entry.getKey();
if(!inRange(key))
returnfalse;
TreeMap.Entrynode=m.getEntry(key);
if(node!=null&&valEquals(node.getValue(),entry.getValue())){
m.deleteEntry(node);
returntrue;
}
returnfalse;
}
}
//SubMap的迭代器
abstractclassSubMapIteratorimplementsIterator{
//上一次被返回的Entry
TreeMap.EntrylastReturned;
//指向下一个Entry
TreeMap.Entrynext;
//“栅栏key”。根据SubMap是“升序”还是“降序”具有不同的意义
finalKfenceKey;
intexpectedModCount;
//构造函数
SubMapIterator(TreeMap.Entryfirst,
TreeMap.Entryfence){
//每创建一个SubMapIterator时，保存修改次数
//若后面发现expectedModCount和modCount不相等，则抛出ConcurrentModificationException异常。
//这就是所说的fast-fail机制的原理！
expectedModCount=m.modCount;
lastReturned=null;
next=first;
fenceKey=fence==null?null:fence.key;
}
//是否存在下一个Entry
publicfinalbooleanhasNext(){
returnnext!=null&&next.key!=fenceKey;
}
//返回下一个Entry
finalTreeMap.EntrynextEntry(){
TreeMap.Entrye=next;
if(e==null||e.key==fenceKey)
thrownewNoSuchElementException();
if(m.modCount!=expectedModCount)
thrownewConcurrentModificationException();
//next指向e的后继节点
next=successor(e);
lastReturned=e;
returne;
}
//返回上一个Entry
finalTreeMap.EntryprevEntry(){
TreeMap.Entrye=next;
if(e==null||e.key==fenceKey)
thrownewNoSuchElementException();
if(m.modCount!=expectedModCount)
thrownewConcurrentModificationException();
//next指向e的前继节点
next=predecessor(e);
lastReturned=e;
returne;
}
//删除当前节点(用于“升序的SubMap”)。
//删除之后，可以继续升序遍历；红黑树特性没变。
finalvoidremoveAscending(){
if(lastReturned==null)
thrownewIllegalStateException();
if(m.modCount!=expectedModCount)
thrownewConcurrentModificationException();
//这里重点强调一下“为什么当lastReturned的左右孩子都不为空时，要将其赋值给next”。
//目的是为了“删除lastReturned节点之后，next节点指向的仍然是下一个节点”。
//根据“红黑树”的特性可知：
//当被删除节点有两个儿子时。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
//这意味着“当被删除节点有两个儿子时，删除当前节点之后，''新的当前节点''实际上是‘原有的后继节点(即下一个节点)’”。
//而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点；能继续遍历红黑树。
if(lastReturned.left!=null&&lastReturned.right!=null)
next=lastReturned;
m.deleteEntry(lastReturned);
lastReturned=null;
expectedModCount=m.modCount;
}
//删除当前节点(用于“降序的SubMap”)。
//删除之后，可以继续降序遍历；红黑树特性没变。
finalvoidremoveDescending(){
if(lastReturned==null)
thrownewIllegalStateException();
if(m.modCount!=expectedModCount)
thrownewConcurrentModificationException();
m.deleteEntry(lawww.shanxiwang.netstReturned);
lastReturned=null;
expectedModCount=m.modCount;
}
}
//SubMap的Entry迭代器，它只支持升序操作，继承于SubMapIterator
finalclassSubMapEntryIteratorextendsSubMapIterator>{
SubMapEntryIterator(TreeMap.Entryfirst,
TreeMap.Entryfence){
super(first,fence);
}
//获取下一个节点(升序)
publicMap.Entrynext(){
returnnextEntry();
}
//删除当前节点(升序)
publicvoidremove(){
removeAscending();
}
}
//SubMap的Key迭代器，它只支持升序操作，继承于SubMapIterator
finalclassSubMapKeyIteratorextendsSubMapIterator{
SubMapKeyIterator(TreeMap.Entryfirst,
TreeMap.Entryfence){
super(first,fence);
}
//获取下一个节点(升序)
publicKnext(){
returnnextEntry().key;
}
//删除当前节点(升序)
publicvoidremove(){
removeAscending();
}
}
//降序SubMap的Entry迭代器，它只支持降序操作，继承于SubMapIterator
finalclassDescendingSubMapEntryIteratorextendsSubMapIterator>{
DescendingSubMapEntryIterator(TreeMap.Entrylast,
TreeMap.Entryfence){
super(last,fence);
}
//获取下一个节点(降序)
publicMap.Entrynext(){
returnprevEntry();
}
//删除当前节点(降序)
publicvoidremove(){
removeDescending();
}
}
//降序SubMap的Key迭代器，它只支持降序操作，继承于SubMapIterator
finalclassDescendingSubMapKeyIteratorextendsSubMapIterator{
DescendingSubMapKeyIterator(TreeMap.Entrylast,
TreeMap.Entryfence){
super(last,fence);
}
//获取下一个节点(降序)
publicKnext(){
returnprevEntry().key;
}
//删除当前节点(降序)
publicvoidremove(){
removeDescending();
}
}
}
//升序的SubMap，继承于NavigableSubMap
staticfinalclassAscendingSubMapextendsNavigableSubMap{
privatestaticfinallongserialVersionUID=912986545866124060L;
//构造函数
AscendingSubMap(TreeMapm, | | |
