版權聲明：尊重部落客原創文章，轉載請注明出處哦~http://blog.csdn.net/eson_15/article/details/51239885
我們繼續分析treemap的源碼
/*************************** put和remove **********************************/
//将key-value對添加到treemap中，了解treemap的前提是了解紅黑樹
//因為和紅黑樹中的添加基本一樣
public v put(k key, v value) {
entry<k,v> t = root;
if (t == null) { //若紅黑樹為空，直接添加根節點
compare(key, key); // type (and possibly null) check
root = new entry<>(key, value, null);
size = 1;
modcount++;
return null;
}
int cmp;
entry<k,v> parent;
//在紅黑樹中找到插入的位置
comparator<? super k> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setvalue(value);
} while (t != null);
else {
if (key == null)
throw new nullpointerexception();
comparable<? super k> k = (comparable<? super k>) key;
cmp = k.compareto(t.key);
//建立紅黑樹的節點e
entry<k,v> e = new entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixafterinsertion(e);//插入新節點後，要重新修複紅黑樹的特性
size++;
modcount++;
return null;
}
//插入新節點後的修正操作，保證紅黑樹的平衡性
//跟紅黑樹中的修正方式一樣的
private void fixafterinsertion(entry<k,v> x) {
x.color = red;
while (x != null && x != root && x.parent.color == red) {
if (parentof(x) == leftof(parentof(parentof(x)))) {
entry<k,v> y = rightof(parentof(parentof(x)));
if (colorof(y) == red) {
setcolor(parentof(x), black);
setcolor(y, black);
setcolor(parentof(parentof(x)), red);
x = parentof(parentof(x));
} else {
if (x == rightof(parentof(x))) {
x = parentof(x);
rotateleft(x);
}
rotateright(parentof(parentof(x)));
}
} else {
entry<k,v> y = leftof(parentof(parentof(x)));
if (x == leftof(parentof(x))) {
rotateright(x);
rotateleft(parentof(parentof(x)));
}
root.color = black;
//左旋操作
private void rotateleft(entry<k,v> p) {
if (p != null) {
entry<k,v> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
//右旋操作
private void rotateright(entry<k,v> p) {
entry<k,v> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
//删除指定key的entry
public v remove(object key) {
entry<k,v> p = getentry(key);
if (p == null)
v oldvalue = p.value;
deleteentry(p);
return oldvalue;
private void deleteentry(entry<k,v> p) {
size--;
// if strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
entry<k,v> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// start fixup at replacement node, if it exists.
entry<k,v> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// link replacement to parent
replacement.parent = p.parent;
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
p.parent.right = replacement;
// null out links so they are ok to use by fixafterdeletion.
p.left = p.right = p.parent = null;
// fix replacement
if (p.color == black)
fixafterdeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // no children. use self as phantom replacement and unlink.
fixafterdeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
//删除後的修複，與紅黑樹一樣
private void fixafterdeletion(entry<k,v> x) {
while (x != root && colorof(x) == black) {
if (x == leftof(parentof(x))) {
entry<k,v> sib = rightof(parentof(x));
if (colorof(sib) == red) {
setcolor(sib, black);
setcolor(parentof(x), red);
rotateleft(parentof(x));
sib = rightof(parentof(x));
if (colorof(leftof(sib)) == black &&
colorof(rightof(sib)) == black) {
setcolor(sib, red);
x = parentof(x);
if (colorof(rightof(sib)) == black) {
setcolor(leftof(sib), black);
setcolor(sib, red);
rotateright(sib);
sib = rightof(parentof(x));
setcolor(sib, colorof(parentof(x)));
setcolor(rightof(sib), black);
x = root;
} else { // symmetric
entry<k,v> sib = leftof(parentof(x));
rotateright(parentof(x));
sib = leftof(parentof(x));
if (colorof(rightof(sib)) == black &&
colorof(leftof(sib)) == black) {
if (colorof(leftof(sib)) == black) {
setcolor(rightof(sib), black);
rotateleft(sib);
sib = leftof(parentof(x));
setcolor(leftof(sib), black);
setcolor(x, black);
了解了紅黑樹，這裡的源碼基本沒啥好看的……因為是一回事！其他的方法我就放到源碼裡了，這裡也不贅述了。到最後我們再看一下treemap的周遊方式。下面要耐住性子，因為treemap的源碼很多……
public int size() {
return size;
//傳回treemap中是否包含“鍵(key)”
public boolean containskey(object key) {
return getentry(key) != null;
//傳回treemap中是否包含"值(value)"
public boolean containsvalue(object value) {
//從最小的節點開始找
for (entry<k,v> e = getfirstentry(); e != null; e = successor(e))
if (valequals(value, e.value))
return true;
return false;
// 擷取“鍵(key)”對應的“值(value)”
public v get(object key) {
return (p==null ? null : p.value);
public comparator<? super k> comparator() {
return comparator;
// 擷取第一個節點對應的key
public k firstkey() {
return key(getfirstentry());
// 擷取最後一個節點對應的key
public k lastkey() {
return key(getlastentry());
// 傳回不大于key的最大的鍵值對所對應的key，沒有的話傳回null
public k floorkey(k key) {
return keyornull(getfloorentry(key));
// 傳回不小于key的最小的鍵值對所對應的key，沒有的話傳回null
public k ceilingkey(k key) {
return keyornull(getceilingentry(key));
// 傳回小于key的最大的鍵值對所對應的key，沒有的話傳回null
public k lowerkey(k key) {
return keyornull(getlowerentry(key));
// 傳回大于key的最小的鍵值對所對應的key，沒有的話傳回null
public k higherkey(k key) {
return keyornull(gethigherentry(key));
//treemap的紅黑樹節點對應的集合
private transient entryset entryset = null;
//navigablekeyset為keyset導航類
private transient keyset<k> navigablekeyset = null;
//descendingmap為鍵值對的倒序“映射”
private transient navigablemap<k,v> descendingmap = null;
// 傳回treemap的“鍵的集合”
public set<k> keyset() {
return navigablekeyset();
// 擷取“可導航”的key的集合
// 實際上是傳回keyset類的對象。
public navigableset<k> navigablekeyset() {
keyset<k> nks = navigablekeyset;
return (nks != null) ? nks : (navigablekeyset = new keyset(this));
// 擷取treemap的降序的key的集合
public navigableset<k> descendingkeyset() {
return descendingmap().navigablekeyset();
// 擷取treemap的降序map
// 實際上是傳回descendingsubmap類的對象
public navigablemap<k, v> descendingmap() {
navigablemap<k, v> km = descendingmap;
return (km != null) ? km :
(descendingmap = new descendingsubmap(this,
true, null, true,
true, null, true));
// 傳回“treemap的值對應的集合”
public collection<v> values() {
collection<v> vs = values;
return (vs != null) ? vs : (values = new values());
// ”treemap的值的集合“對應的類，它繼承于abstractcollection
class values extends abstractcollection<v> {
public iterator<v> iterator() {
return new valueiterator(getfirstentry());
public int size() {
return treemap.this.size();
public boolean contains(object o) {
return treemap.this.containsvalue(o);
public boolean remove(object o) {
for (entry<k,v> e = getfirstentry(); e != null; e = successor(e)) {
if (valequals(e.getvalue(), o)) {
deleteentry(e);
return true;
return false;
public void clear() {
treemap.this.clear();
// 擷取treemap的entry的集合，實際上是傳回entryset類的對象。
public set<map.entry<k,v>> entryset() {
entryset es = entryset;
return (es != null) ? es : (entryset = new entryset());
// entryset是“treemap的所有鍵值對組成的集合”，
// entryset集合的機關是單個“鍵值對”。
class entryset extends abstractset<map.entry<k,v>> {
public iterator<map.entry<k,v>> iterator() {
return new entryiterator(getfirstentry());
if (!(o instanceof map.entry))
return false;
map.entry<k,v> entry = (map.entry<k,v>) o;
v value = entry.getvalue();
entry<k,v> p = getentry(entry.getkey());
return p != null && valequals(p.getvalue(), value);
if (p != null && valequals(p.getvalue(), value)) {
deleteentry(p);
// 擷取treemap的子map
// 範圍是從fromkey 到 tokey；frominclusive是是否包含fromkey的标記，toinclusive是是否包含tokey的标記
public navigablemap<k,v> submap(k fromkey, boolean frominclusive,
k tokey, boolean toinclusive) {
return new ascendingsubmap(this,
false, fromkey, frominclusive,
false, tokey, toinclusive);
// 擷取“map的頭部”
// 範圍從第一個節點 到 tokey, inclusive是是否包含tokey的标記
public navigablemap<k,v> headmap(k tokey, boolean inclusive) {
true, null, true,
false, tokey, inclusive);
// 擷取“map的尾部”。
// 範圍是從 fromkey 到 最後一個節點，inclusive是是否包含fromkey的标記
public navigablemap<k,v> tailmap(k fromkey, boolean inclusive) {
false, fromkey, inclusive,
true, null, true);
// 擷取“子map”。
// 範圍是從fromkey(包括) 到 tokey(不包括)
public sortedmap<k,v> submap(k fromkey, k tokey) {
return submap(fromkey, true, tokey, false);
// 擷取“map的頭部”。
// 範圍從第一個節點 到 tokey(不包括)
public sortedmap<k,v> headmap(k tokey) {
return headmap(tokey, false);
// 範圍是從 fromkey(包括) 到 最後一個節點
public sortedmap<k,v> tailmap(k fromkey) {
return tailmap(fromkey, true);
//傳回“treemap的key組成的疊代器(順序)”
iterator<k> keyiterator() {
return new keyiterator(getfirstentry());
// 傳回“treemap的key組成的疊代器(逆序)”
iterator<k> descendingkeyiterator() {
return new descendingkeyiterator(getlastentry());
// keyset是“treemap中所有的key組成的集合”
// keyset繼承于abstractset，而且實作了navigableset接口。
static final class keyset<e> extends abstractset<e> implements navigableset<e> {
private final navigablemap<e, object> m;
keyset(navigablemap<e,object> map) { m = map; }
//升序疊代器
public iterator<e> iterator() {
// 若是treemap對象，則調用treemap的疊代器keyiterator()
// 否則，調用treemap子類navigablesubmap的疊代器keyiterator()
if (m instanceof treemap)
return ((treemap<e,object>)m).keyiterator();
return (iterator<e>)(((treemap.navigablesubmap)m).keyiterator());
//降序疊代器
public iterator<e> descendingiterator() {
// 若是treemap對象，則調用treemap的疊代器descendingkeyiterator()
// 否則，調用treemap子類navigablesubmap的疊代器descendingkeyiterator()
return ((treemap<e,object>)m).descendingkeyiterator();
return (iterator<e>)(((treemap.navigablesubmap)m).descendingkeyiterator());
public int size() { return m.size(); }
public boolean isempty() { return m.isempty(); }
public boolean contains(object o) { return m.containskey(o); }
public void clear() { m.clear(); }
public e lower(e e) { return m.lowerkey(e); }
public e floor(e e) { return m.floorkey(e); }
public e ceiling(e e) { return m.ceilingkey(e); }
public e higher(e e) { return m.higherkey(e); }
public e first() { return m.firstkey(); }
public e last() { return m.lastkey(); }
public comparator<? super e> comparator() { return m.comparator(); }
public e pollfirst() {
map.entry<e,object> e = m.pollfirstentry();
return (e == null) ? null : e.getkey();
public e polllast() {
map.entry<e,object> e = m.polllastentry();
int oldsize = size();
m.remove(o);
return size() != oldsize;
public navigableset<e> subset(e fromelement, boolean frominclusive,
e toelement, boolean toinclusive) {
return new keyset<>(m.submap(fromelement, frominclusive,
toelement, toinclusive));
public navigableset<e> headset(e toelement, boolean inclusive) {
return new keyset<>(m.headmap(toelement, inclusive));
public navigableset<e> tailset(e fromelement, boolean inclusive) {
return new keyset<>(m.tailmap(fromelement, inclusive));
public sortedset<e> subset(e fromelement, e toelement) {
return subset(fromelement, true, toelement, false);
public sortedset<e> headset(e toelement) {
return headset(toelement, false);
public sortedset<e> tailset(e fromelement) {
return tailset(fromelement, true);
public navigableset<e> descendingset() {
return new keyset(m.descendingmap());
/// 它是treemap中的一個抽象疊代器，實作了一些通用的接口。
abstract class privateentryiterator<t> implements iterator<t> {
entry<k,v> next;
entry<k,v> lastreturned;
int expectedmodcount;
privateentryiterator(entry<k,v> first) {
expectedmodcount = modcount;
lastreturned = null;
next = first;
public final boolean hasnext() {
return next != null;
final entry<k,v> nextentry() {
entry<k,v> e = next;
if (e == null)
throw new nosuchelementexception();
if (modcount != expectedmodcount)
throw new concurrentmodificationexception();
next = successor(e);
lastreturned = e;
return e;
final entry<k,v> preventry() {
next = predecessor(e);
public void remove() {
if (lastreturned == null)
throw new illegalstateexception();
// 這裡重點強調一下“為什麼當lastreturned的左右孩子都不為空時，要将其指派給next”。
// 目的是為了“删除lastreturned節點之後，next節點指向的仍然是下一個節點”。
// 根據“紅黑樹”的特性可知：
// 當被删除節點有兩個兒子時。那麼，首先把“它的後繼節點的内容”複制給“該節點的内容”；之後，删除“它的後繼節點”。
// 這意味着“當被删除節點有兩個兒子時，删除目前節點之後，'新的目前節點'實際上是‘原有的後繼節點(即下一個節點)’”。
// 而此時next仍然指向"新的目前節點"。也就是說next是仍然是指向下一個節點；能繼續周遊紅黑樹。
if (lastreturned.left != null && lastreturned.right != null)
next = lastreturned;
deleteentry(lastreturned);
// treemap的entry對應的疊代器
final class entryiterator extends privateentryiterator<map.entry<k,v>> {
entryiterator(entry<k,v> first) {
super(first);
public map.entry<k,v> next() {
return nextentry();
// treemap的value對應的疊代器
final class valueiterator extends privateentryiterator<v> {
valueiterator(entry<k,v> first) {
public v next() {
return nextentry().value;
// reemap的key組成的疊代器(順序)
final class keyiterator extends privateentryiterator<k> {
keyiterator(entry<k,v> first) {
public k next() {
return nextentry().key;
// treemap的key組成的疊代器(逆序)
final class descendingkeyiterator extends privateentryiterator<k> {
descendingkeyiterator(entry<k,v> first) {
return preventry().key;
// 比較兩個對象的大小
final int compare(object k1, object k2) {
return comparator==null ? ((comparable<? super k>)k1).compareto((k)k2)
: comparator.compare((k)k1, (k)k2);
// 判斷兩個對象是否相等
static final boolean valequals(object o1, object o2) {
return (o1==null ? o2==null : o1.equals(o2));
// 傳回“key-value鍵值對”的一個簡單拷貝(abstractmap.simpleimmutableentry<k,v>對象)
// 可用來讀取“鍵值對”的值
static <k,v> map.entry<k,v> exportentry(treemap.entry<k,v> e) {
return (e == null) ? null :
new abstractmap.simpleimmutableentry<>(e);
// 若“鍵值對”不為null，則傳回key；否則，傳回null
static <k,v> k keyornull(treemap.entry<k,v> e) {
return (e == null) ? null : e.key;
// 若“鍵值對”不為null，則傳回key；否則，抛出異常
static <k> k key(entry<k,?> e) {
if (e==null)
throw new nosuchelementexception();
return e.key;
private static final object unbounded = new object();
// treemap的submap，它一個抽象類，實作了公共操作。
// 它包括了"(升序)ascendingsubmap"和"(降序)descendingsubmap"兩個子類。
abstract static class navigablesubmap<k,v> extends abstractmap<k,v>
implements navigablemap<k,v>, java.io.serializable {
// treemap的拷貝
final treemap<k,v> m;
// lo是“子map範圍的最小值”，hi是“子map範圍的最大值”；
// loinclusive是“是否包含lo的标記”，hiinclusive是“是否包含hi的标記”
// fromstart是“表示是否從第一個節點開始計算”，
// toend是“表示是否計算到最後一個節點
final k lo, hi;
final boolean fromstart, toend;
final boolean loinclusive, hiinclusive;
navigablesubmap(treemap<k,v> m,
boolean fromstart, k lo, boolean loinclusive,
boolean toend, k hi, boolean hiinclusive) {
if (!fromstart && !toend) {
if (m.compare(lo, hi) > 0)
throw new illegalargumentexception("fromkey > tokey");
if (!fromstart) // type check
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是否太小
final boolean toolow(object key) {
// 若該submap不包括“起始節點”，
// 并且，“key小于最小鍵(lo)”或者“key等于最小鍵(lo)，但最小鍵卻沒包括在該submap内”
// 則判斷key太小。其餘情況都不是太小！
if (!fromstart) {
int c = m.compare(key, lo);
if (c < 0 || (c == 0 && !loinclusive))
// 判斷key是否太大
final boolean toohigh(object key) {
// 若該submap不包括“結束節點”，
// 并且，“key大于最大鍵(hi)”或者“key等于最大鍵(hi)，但最大鍵卻沒包括在該submap内”
// 則判斷key太大。其餘情況都不是太大！
if (!toend) {
int c = m.compare(key, hi);
if (c > 0 || (c == 0 && !hiinclusive))
// 判斷key是否在“lo和hi”開區間範圍内
final boolean inrange(object key) {
return !toolow(key) && !toohigh(key);
// 判斷key是否在封閉區間内
final boolean inclosedrange(object key) {
return (fromstart || m.compare(key, lo) >= 0)
&& (toend || m.compare(hi, key) >= 0);
// 判斷key是否在區間内, inclusive是區間開關标志
final boolean inrange(object key, boolean inclusive) {
return inclusive ? inrange(key) : inclosedrange(key);
// 傳回最低的entry
final treemap.entry<k,v> abslowest() {
// 若“包含起始節點”，則調用getfirstentry()傳回第一個節點
// 否則的話，若包括lo，則調用getceilingentry(lo)擷取大于/等于lo的最小的entry;
// 否則，調用gethigherentry(lo)擷取大于lo的最小entry
treemap.entry<k,v> e =
(fromstart ? m.getfirstentry() :
(loinclusive ? m.getceilingentry(lo) :
m.gethigherentry(lo)));
return (e == null || toohigh(e.key)) ? null : e;
// 傳回最高的entry
final treemap.entry<k,v> abshighest() {
// 若“包含結束節點”，則調用getlastentry()傳回最後一個節點
// 否則的話，若包括hi，則調用getfloorentry(hi)擷取小于/等于hi的最大的entry;
// 否則，調用getlowerentry(hi)擷取大于hi的最大entry
(toend ? m.getlastentry() :
(hiinclusive ? m.getfloorentry(hi) :
m.getlowerentry(hi)));
return (e == null || toolow(e.key)) ? null : e;
// 傳回"大于/等于key的最小的entry"
final treemap.entry<k,v> absceiling(k key) {
// 隻有在“key太小”的情況下，abslowest()傳回的entry才是“大于/等于key的最小entry”
// 其它情況下不行。例如，當包含“起始節點”時，abslowest()傳回的是最小entry了！
if (toolow(key))
return abslowest();
// 擷取“大于/等于key的最小entry”
treemap.entry<k,v> e = m.getceilingentry(key);
// 傳回"大于key的最小的entry"
final treemap.entry<k,v> abshigher(k key) {
// 隻有在“key太小”的情況下，abslowest()傳回的entry才是“大于key的最小entry”
// 其它情況下不行。例如，當包含“起始節點”時，abslowest()傳回的是最小entry了,而不一定是“大于key的最小entry”！
// 擷取“大于key的最小entry”
treemap.entry<k,v> e = m.gethigherentry(key);
// 傳回"小于/等于key的最大的entry"
final treemap.entry<k,v> absfloor(k key) {
// 隻有在“key太大”的情況下，(abshighest)傳回的entry才是“小于/等于key的最大entry”
// 其它情況下不行。例如，當包含“結束節點”時，abshighest()傳回的是最大entry了！
if (toohigh(key))
return abshighest();
// 擷取"小于/等于key的最大的entry"
treemap.entry<k,v> e = m.getfloorentry(key);
// 傳回"小于key的最大的entry"
final treemap.entry<k,v> abslower(k key) {
// 隻有在“key太大”的情況下，(abshighest)傳回的entry才是“小于key的最大entry”
// 其它情況下不行。例如，當包含“結束節點”時，abshighest()傳回的是最大entry了,而不一定是“小于key的最大entry”！
// 擷取"小于key的最大的entry"
treemap.entry<k,v> e = m.getlowerentry(key);
// 傳回“大于最大節點中的最小節點”，不存在的話，傳回null
final treemap.entry<k,v> abshighfence() {
return (toend ? null : (hiinclusive ?
m.gethigherentry(hi) :
m.getceilingentry(hi)));
// 傳回“小于最小節點中的最大節點”，不存在的話，傳回null
final treemap.entry<k,v> abslowfence() {
return (fromstart ? null : (loinclusive ?
m.getlowerentry(lo) :
m.getfloorentry(lo)));
// 下面幾個abstract方法是需要navigablesubmap的實作類實作的方法
abstract treemap.entry<k,v> sublowest();
abstract treemap.entry<k,v> subhighest();
abstract treemap.entry<k,v> subceiling(k key);
abstract treemap.entry<k,v> subhigher(k key);
abstract treemap.entry<k,v> subfloor(k key);
abstract treemap.entry<k,v> sublower(k key);
// 傳回“順序”的鍵疊代器
abstract iterator<k> keyiterator();
// 傳回“逆序”的鍵疊代器
abstract iterator<k> descendingkeyiterator();
// 傳回submap是否為空。空的話，傳回true，否則傳回false
public boolean isempty() {
return (fromstart && toend) ? m.isempty() : entryset().isempty();
// 傳回submap的大小
return (fromstart && toend) ? m.size() : entryset().size();
// 傳回submap是否包含鍵key
public final boolean containskey(object key) {
return inrange(key) && m.containskey(key);
// 将key-value 插入submap中
public final v put(k key, v value) {
if (!inrange(key))
throw new illegalargumentexception("key out of range");
return m.put(key, value);
// 擷取key對應值
public final v get(object key) {
return !inrange(key) ? null : m.get(key);
// 删除key對應的鍵值對
public final v remove(object key) {
return !inrange(key) ? null : m.remove(key);
// 擷取“大于/等于key的最小鍵值對”
public final map.entry<k,v> ceilingentry(k key) {
return exportentry(subceiling(key));
// 擷取“大于/等于key的最小鍵”
public final k ceilingkey(k key) {
return keyornull(subceiling(key));
// 擷取“大于key的最小鍵值對”
public final map.entry<k,v> higherentry(k key) {
return exportentry(subhigher(key));
// 擷取“大于key的最小鍵”
public final k higherkey(k key) {
return keyornull(subhigher(key));
// 擷取“小于/等于key的最大鍵值對”
public final map.entry<k,v> floorentry(k key) {
return exportentry(subfloor(key));
// 擷取“小于/等于key的最大鍵”
public final k floorkey(k key) {
return keyornull(subfloor(key));
// 擷取“小于key的最大鍵值對”
public final map.entry<k,v> lowerentry(k key) {
return exportentry(sublower(key));
// 擷取“小于key的最大鍵”
public final k lowerkey(k key) {
return keyornull(sublower(key));
// 擷取"submap的第一個鍵"
public final k firstkey() {
return key(sublowest());
// 擷取"submap的最後一個鍵"
public final k lastkey() {
return key(subhighest());
// 擷取"submap的第一個鍵值對"
public final map.entry<k,v> firstentry() {
return exportentry(sublowest());
// 擷取"submap的最後一個鍵值對"
public final map.entry<k,v> lastentry() {
return exportentry(subhighest());
// 傳回"submap的第一個鍵值對"，并從submap中删除改鍵值對
public final map.entry<k,v> pollfirstentry() {
treemap.entry<k,v> e = sublowest();
map.entry<k,v> result = exportentry(e);
if (e != null)
m.deleteentry(e);
return result;
// 傳回"submap的最後一個鍵值對"，并從submap中删除改鍵值對
public final map.entry<k,v> polllastentry() {
treemap.entry<k,v> e = subhighest();
// views
transient navigablemap<k,v> descendingmapview = null;
transient entrysetview entrysetview = null;
transient keyset<k> navigablekeysetview = null;
// 傳回navigableset對象，實際上傳回的是目前對象的"key集合"。
public final navigableset<k> navigablekeyset() {
keyset<k> nksv = navigablekeysetview;
return (nksv != null) ? nksv :
(navigablekeysetview = new treemap.keyset(this));
// 傳回"key集合"對象
public final set<k> keyset() {
return navigablekeyset();
// 傳回“逆序”的key集合
public navigableset<k> descendingkeyset() {
return descendingmap().navigablekeyset();
// 排列fromkey(包含) 到 tokey(不包含) 的子map
public final sortedmap<k,v> submap(k fromkey, k tokey) {
return submap(fromkey, true, tokey, false);
// 傳回目前map的頭部(從第一個節點 到 tokey, 不包括tokey)
public final sortedmap<k,v> headmap(k tokey) {
return headmap(tokey, false);
// 傳回目前map的尾部[從 fromkey(包括fromkeykey) 到 最後一個節點]
public final sortedmap<k,v> tailmap(k fromkey) {
return tailmap(fromkey, true);
// map的entry的集合
abstract class entrysetview extends abstractset<map.entry<k,v>> {
private transient int size = -1, sizemodcount;
public int size() {
if (fromstart && toend)
return m.size();
if (size == -1 || sizemodcount != m.modcount) {
sizemodcount = m.modcount;
size = 0;
iterator i = iterator();
while (i.hasnext()) {
size++;
i.next();
return size;
public boolean isempty() {
treemap.entry<k,v> n = abslowest();
return n == null || toohigh(n.key);
public boolean contains(object o) {
if (!(o instanceof map.entry))
return false;
map.entry<k,v> entry = (map.entry<k,v>) o;
k key = entry.getkey();
if (!inrange(key))
treemap.entry node = m.getentry(key);
return node != null &&
valequals(node.getvalue(), entry.getvalue());
public boolean remove(object o) {
treemap.entry<k,v> node = m.getentry(key);
if (node!=null && valequals(node.getvalue(),
entry.getvalue())) {
m.deleteentry(node);
// submap的疊代器
abstract class submapiterator<t> implements iterator<t> {
treemap.entry<k,v> lastreturned;
treemap.entry<k,v> next;
final object fencekey;
int expectedmodcount;
submapiterator(treemap.entry<k,v> first,
treemap.entry<k,v> fence) {
expectedmodcount = m.modcount;
lastreturned = null;
next = first;
fencekey = fence == null ? unbounded : fence.key;
public final boolean hasnext() {
return next != null && next.key != fencekey;
final treemap.entry<k,v> nextentry() {
treemap.entry<k,v> e = next;
if (e == null || e.key == fencekey)
throw new nosuchelementexception();
if (m.modcount != expectedmodcount)
throw new concurrentmodificationexception();
next = successor(e);
lastreturned = e;
return e;
final treemap.entry<k,v> preventry() {
next = predecessor(e);
// 删除目前節點(用于“升序的submap”)。
// 删除之後，可以繼續升序周遊；紅黑樹特性沒變。
final void removeascending() {
if (lastreturned == null)
throw new illegalstateexception();
// 這裡重點強調一下“為什麼當lastreturned的左右孩子都不為空時，要将其指派給next”。
// 目的是為了“删除lastreturned節點之後，next節點指向的仍然是下一個節點”。
// 根據“紅黑樹”的特性可知：
// 當被删除節點有兩個兒子時。那麼，首先把“它的後繼節點的内容”複制給“該節點的内容”；之後，删除“它的後繼節點”。
// 這意味着“當被删除節點有兩個兒子時，删除目前節點之後，'新的目前節點'實際上是‘原有的後繼節點(即下一個節點)’”。
// 而此時next仍然指向"新的目前節點"。也就是說next是仍然是指向下一個節點；能繼續周遊紅黑樹。
if (lastreturned.left != null && lastreturned.right != null)
next = lastreturned;
m.deleteentry(lastreturned);
// 删除目前節點(用于“降序的submap”)。
// 删除之後，可以繼續降序周遊；紅黑樹特性沒變。
final void removedescending() {
// submap的entry疊代器，它隻支援升序操作，繼承于submapiterator
final class submapentryiterator extends submapiterator<map.entry<k,v>> {
submapentryiterator(treemap.entry<k,v> first,
treemap.entry<k,v> fence) {
super(first, fence);
public map.entry<k,v> next() {
return nextentry();
public void remove() {
removeascending();
// submap的key疊代器，它隻支援升序操作，繼承于submapiterator
final class submapkeyiterator extends submapiterator<k> {
submapkeyiterator(treemap.entry<k,v> first,
treemap.entry<k,v> fence) {
// 擷取下一個節點(升序)
public k next() {
return nextentry().key;
// 删除目前節點(升序)
// 降序submap的entry疊代器，它隻支援降序操作，繼承于submapiterator
final class descendingsubmapentryiterator extends submapiterator<map.entry<k,v>> {
descendingsubmapentryiterator(treemap.entry<k,v> last,
treemap.entry<k,v> fence) {
super(last, fence);
// 擷取下一個節點(降序)
return preventry();
// 删除目前節點(降序)
removedescending();
// 降序submap的key疊代器，它隻支援降序操作，繼承于submapiterator
final class descendingsubmapkeyiterator extends submapiterator<k> {
descendingsubmapkeyiterator(treemap.entry<k,v> last,
treemap.entry<k,v> fence) {
return preventry().key;
// 升序的submap，繼承于navigablesubmap
static final class ascendingsubmap<k,v> extends navigablesubmap<k,v> {
private static final long serialversionuid = 912986545866124060l;
ascendingsubmap(treemap<k,v> m,
super(m, fromstart, lo, loinclusive, toend, hi, hiinclusive);
public comparator<? super k> comparator() {
return m.comparator();
// 擷取“子map”。
// 範圍是從fromkey 到 tokey；frominclusive是是否包含fromkey的标記，toinclusive是是否包含tokey的标記
public navigablemap<k,v> submap(k fromkey, boolean frominclusive,
k tokey, boolean toinclusive) {
if (!inrange(fromkey, frominclusive))
throw new illegalargumentexception("fromkey out of range");
if (!inrange(tokey, toinclusive))
throw new illegalargumentexception("tokey out of range");
return new ascendingsubmap(m,
false, fromkey, frominclusive,
false, tokey, toinclusive);
// 擷取“map的頭部”。
// 範圍從第一個節點 到 tokey, inclusive是是否包含tokey的标記
public navigablemap<k,v> headmap(k tokey, boolean inclusive) {
if (!inrange(tokey, inclusive))
fromstart, lo, loinclusive,
false, tokey, inclusive);
// 擷取“map的尾部”。
// 範圍是從 fromkey 到 最後一個節點，inclusive是是否包含fromkey的标記
public navigablemap<k,v> tailmap(k fromkey, boolean inclusive) {
if (!inrange(fromkey, inclusive))
false, fromkey, inclusive,
toend, hi, hiinclusive);
// 擷取對應的降序map
public navigablemap<k,v> descendingmap() {
navigablemap<k,v> mv = descendingmapview;
return (mv != null) ? mv :
(descendingmapview =
new descendingsubmap(m,
fromstart, lo, loinclusive,
toend, hi, hiinclusive));
// 傳回“升序key疊代器”
iterator<k> keyiterator() {
return new submapkeyiterator(abslowest(), abshighfence());
// 傳回“降序key疊代器”
iterator<k> descendingkeyiterator() {
return new descendingsubmapkeyiterator(abshighest(), abslowfence());
// “升序entryset集合”類
// 實作了iterator()
final class ascendingentrysetview extends entrysetview {
public iterator<map.entry<k,v>> iterator() {
return new submapentryiterator(abslowest(), abshighfence());
// 傳回“升序entryset集合”
public set<map.entry<k,v>> entryset() {
entrysetview es = entrysetview;
return (es != null) ? es : new ascendingentrysetview();
treemap.entry<k,v> sublowest() { return abslowest(); }
treemap.entry<k,v> subhighest() { return abshighest(); }
treemap.entry<k,v> subceiling(k key) { return absceiling(key); }
treemap.entry<k,v> subhigher(k key) { return abshigher(key); }
treemap.entry<k,v> subfloor(k key) { return absfloor(key); }
treemap.entry<k,v> sublower(k key) { return abslower(key); }
// 降序的submap，繼承于navigablesubmap
// 相比于升序submap，它的實作機制是将“submap的比較器反轉”！
static final class descendingsubmap<k,v> extends navigablesubmap<k,v> {
private static final long serialversionuid = 912986545866120460l;
descendingsubmap(treemap<k,v> m,
// 反轉的比較器：是将原始比較器反轉得到的。
private final comparator<? super k> reversecomparator =
collections.reverseorder(m.comparator);
// 擷取反轉比較器
return reversecomparator;
return new descendingsubmap(m,
false, tokey, toinclusive,
false, fromkey, frominclusive);
false, tokey, inclusive,
toend, hi, hiinclusive);
fromstart, lo, loinclusive,
false, fromkey, inclusive);
new ascendingsubmap(m,
fromstart, lo, loinclusive,
toend, hi, hiinclusive));
// “降序entryset集合”類
final class descendingentrysetview extends entrysetview {
return new descendingsubmapentryiterator(abshighest(), abslowfence());
// 傳回“降序entryset集合”
return (es != null) ? es : new descendingentrysetview();
treemap.entry<k,v> sublowest() { return abshighest(); }
treemap.entry<k,v> subhighest() { return abslowest(); }
treemap.entry<k,v> subceiling(k key) { return absfloor(key); }
treemap.entry<k,v> subhigher(k key) { return abslower(key); }
treemap.entry<k,v> subfloor(k key) { return absceiling(key); }
treemap.entry<k,v> sublower(k key) { return abshigher(key); }
// submap是舊版本的類，新的java中沒有用到。
private class submap extends abstractmap<k,v>
implements sortedmap<k,v>, java.io.serializable {
private static final long serialversionuid = -6520786458950516097l;
private boolean fromstart = false, toend = false;
private k fromkey, tokey;
private object readresolve() {
return new ascendingsubmap(treemap.this,
fromstart, fromkey, true,
toend, tokey, false);
public set<map.entry<k,v>> entryset() { throw new internalerror(); }
public k lastkey() { throw new internalerror(); }
public k firstkey() { throw new internalerror(); }
public sortedmap<k,v> submap(k fromkey, k tokey) { throw new internalerror(); }
public sortedmap<k,v> headmap(k tokey) { throw new internalerror(); }
public sortedmap<k,v> tailmap(k fromkey) { throw new internalerror(); }
public comparator<? super k> comparator() { throw new internalerror(); }
private static final boolean red = false;
private static final boolean black = true;
// 傳回“節點t的後繼節點”
static <k,v> treemap.entry<k,v> successor(entry<k,v> t) {
if (t == null)
else if (t.right != null) {
entry<k,v> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
entry<k,v> p = t.parent;
entry<k,v> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
// 傳回“節點t的前繼節點”
static <k,v> entry<k,v> predecessor(entry<k,v> t) {
else if (t.left != null) {
entry<k,v> p = t.left;
while (p.right != null)
p = p.right;
while (p != null && ch == p.left) {
// 傳回“節點p的顔色”
// 根據“紅黑樹的特性”可知：空節點顔色是黑色。
private static <k,v> boolean colorof(entry<k,v> p) {
return (p == null ? black : p.color);
// 傳回“節點p的父節點”
private static <k,v> entry<k,v> parentof(entry<k,v> p) {
return (p == null ? null: p.parent);
// 設定“節點p的顔色為c”
private static <k,v> void setcolor(entry<k,v> p, boolean c) {
if (p != null)
p.color = c;
// 設定“節點p的左孩子”
private static <k,v> entry<k,v> leftof(entry<k,v> p) {
return (p == null) ? null: p.left;
// 設定“節點p的右孩子”
private static <k,v> entry<k,v> rightof(entry<k,v> p) {
return (p == null) ? null: p.right;
private static final long serialversionuid = 919286545866124006l;
// java.io.serializable的寫入函數
// 将treemap的“容量，所有的entry”都寫入到輸出流中
private void writeobject(java.io.objectoutputstream s)
throws java.io.ioexception {
// write out the comparator and any hidden stuff
s.defaultwriteobject();
// write out size (number of mappings)
s.writeint(size);
// write out keys and values (alternating)
for (iterator<map.entry<k,v>> i = entryset().iterator(); i.hasnext(); ) {
map.entry<k,v> e = i.next();
s.writeobject(e.getkey());
s.writeobject(e.getvalue());
// java.io.serializable的讀取函數：根據寫入方式讀出
// 先将treemap的“容量、所有的entry”依次讀出
private void readobject(final java.io.objectinputstream s)
throws java.io.ioexception, classnotfoundexception {
// read in the comparator and any hidden stuff
s.defaultreadobject();
// read in size
int size = s.readint();
buildfromsorted(size, null, s, null);
/** intended to be called only from treeset.readobject */
void readtreeset(int size, java.io.objectinputstream s, v defaultval)
buildfromsorted(size, null, s, defaultval);
/** intended to be called only from treeset.addall */
void addallfortreeset(sortedset<? extends k> set, v defaultval) {
try {
buildfromsorted(set.size(), set.iterator(), null, defaultval);
} catch (java.io.ioexception cannothappen) {
} catch (classnotfoundexception cannothappen) {
// 根據已經一個排好序的map建立一個treemap
private void buildfromsorted(int size, iterator it,
java.io.objectinputstream str,
v defaultval)
throws java.io.ioexception, classnotfoundexception {
this.size = size;
root = buildfromsorted(0, 0, size-1, computeredlevel(size),
it, str, defaultval);
// 将map中的元素逐個添加到treemap中，并傳回map的中間元素作為根節點。
private final entry<k,v> buildfromsorted(int level, int lo, int hi,
int redlevel,
iterator it,
java.io.objectinputstream str,
v defaultval)
if (hi < lo) return null;
// 擷取中間元素
int mid = (lo + hi) >>> 1;
entry<k,v> left = null;
// 若lo小于mid，則遞歸調用擷取(middel的)左孩子。
if (lo < mid)
left = buildfromsorted(level+1, lo, mid - 1, redlevel,
it, str, defaultval);
// 擷取middle節點對應的key和value
k key;
v value;
if (it != null) {
if (defaultval==null) {
map.entry<k,v> entry = (map.entry<k,v>)it.next();
key = entry.getkey();
value = entry.getvalue();
key = (k)it.next();
value = defaultval;
} else { // use stream
key = (k) str.readobject();
value = (defaultval != null ? defaultval : (v) str.readobject());
// 建立middle節點
entry<k,v> middle = new entry<>(key, value, null);
// 若目前節點的深度=紅色節點的深度，則将節點着色為紅色。
if (level == redlevel)
middle.color = red;
// 設定middle為left的父親，left為middle的左孩子
if (left != null) {
middle.left = left;
left.parent = middle;
if (mid < hi) {
// 遞歸調用擷取(middel的)右孩子。
entry<k,v> right = buildfromsorted(level+1, mid+1, hi, redlevel,
it, str, defaultval);
// 設定middle為left的父親，left為middle的左孩子
middle.right = right;
right.parent = middle;
return middle;
// 計算節點樹為sz的最大深度，也是紅色節點的深度值。
private static int computeredlevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
……終于結束了源碼，treemap有這麼多我也沒辦法……最後看一下treemap的周遊方式。
treemap的周遊方式一般分為兩步：
1. 先通過entryset()或keyset()或value()方法獲得相應的集合；
2. 通過iterator疊代器周遊上面得到的集合。
// 假設map是treemap對象
// map中的key是string類型，value是integer類型
integer integ = null;
iterator iter = map.entryset().iterator();
while(iter.hasnext()) {
map.entry entry = (map.entry)iter.next();
// 擷取key
key = (string)entry.getkey();
// 擷取value
integ = (integer)entry.getvalue();
string key = null;
iterator iter = map.keyset().iterator();
while (iter.hasnext()) {
// 擷取key
key = (string)iter.next();
// 根據key，擷取value
integ = (integer)map.get(key);
integer value = null;
collection c = map.values();
iterator iter= c.iterator();
value = (integer)iter.next();
treemap就介紹這麼多吧，如有錯誤之處，歡迎留言指正~
_____________________________________________________________________________________________________________________________________________________
-----樂于分享，共同進步！