版權聲明：尊重部落客原創文章，轉載請注明出處哦~http://blog.csdn.net/eson_15/article/details/51217741
前面讨論完了hashmap和hashtable的源碼，這一節我們來讨論一下treemap。先從整體上把握treemap，然後分析其源碼，深入剖析treemap的實作。
java.lang.object
↳ java.util.abstractmap<k, v>
↳ java.util.treemap<k, v>
public class treemap<k,v>
extends abstractmap<k,v>
implements navigablemap<k,v>, cloneable, java.io.serializable {}
從繼承關系可以看出，treemap繼承與abstractmap，實作了navigablemap接口，意味着它支援一系列的導航方法，比如傳回有序的key集合。它還實作了cloneable接口，意味着它能被克隆。另外也實作了serializable接口，表示它支援序列化。
treemap是基于紅-黑樹實作的，該映射根據其key的自然順序進行排序，或者根據使用者建立映射時提供的comarator進行排序，另外，treemap是非同步的。
我們先總覽一下treemap都有哪些api：
entry<k, v> ceilingentry(k key)
k ceilingkey(k key)
void clear()
object clone()
comparator<? super k> comparator()
boolean containskey(object key)
navigableset<k> descendingkeyset()
navigablemap<k, v> descendingmap()
set<entry<k, v>> entryset()
entry<k, v> firstentry()
k firstkey()
entry<k, v> floorentry(k key)
k floorkey(k key)
v get(object key)
navigablemap<k, v> headmap(k to, boolean inclusive)
sortedmap<k, v> headmap(k toexclusive)
entry<k, v> higherentry(k key)
k higherkey(k key)
boolean isempty()
set<k> keyset()
entry<k, v> lastentry()
k lastkey()
entry<k, v> lowerentry(k key)
k lowerkey(k key)
navigableset<k> navigablekeyset()
entry<k, v> pollfirstentry()
entry<k, v> polllastentry()
v put(k key, v value)
v remove(object key)
int size()
sortedmap<k, v> submap(k frominclusive, k toexclusive)
navigablemap<k, v> submap(k from, boolean frominclusive, k to, boolean toinclusive)
navigablemap<k, v> tailmap(k from, boolean inclusive)
sortedmap<k, v> tailmap(k frominclusive)
從這些api中可以看出，總共可分為這幾大類：跟entry相關的，跟key相關的以及跟map相關的，另外還有keyset和entryset等方法，下文詳細讨論這些api。
private transient entry<k,v> root = null;
然後我們看看entry實體類的實作：
先看一下entry實體類：
private static final boolean red = false;
private static final boolean black = true;
//就是一個紅黑樹的節點
static final class entry<k,v> implements map.entry<k,v> {
k key;
v value;
entry<k,v> left = null; //左子節點
entry<k,v> right = null; //右子節點
entry<k,v> parent; //父節點
boolean color = black; //樹的顔色，預設為黑色
entry(k key, v value, entry<k,v> parent) { //構造方法
this.key = key;
this.value = value;
this.parent = parent;
}
public k getkey() { //獲得key
return key;
public v getvalue() { //獲得value
return value;
public v setvalue(v value) { //設定value
v oldvalue = this.value;
return oldvalue;
public boolean equals(object o) { //key和value均相等才傳回true
if (!(o instanceof map.entry))
return false;
map.entry<?,?> e = (map.entry<?,?>)o;
return valequals(key,e.getkey()) && valequals(value,e.getvalue());
public int hashcode() { //計算hashcode
int keyhash = (key==null ? 0 : key.hashcode());
int valuehash = (value==null ? 0 : value.hashcode());
return keyhash ^ valuehash;
public string tostring() { //重寫tostring方法
return key + "=" + value;
}
從entry實體類中可以看出，treemap中的entry就是一個紅黑樹的節點。跟這個entry相關的方法都有firstentry()、lastentry()、lowerentry()、higherentry()、floorentry()、ceilingentry()。它們的原理都是類似的，我們隻分析firstentry()，其他的放到源碼裡分析：
public map.entry<k,v> firstentry() {
return exportentry(getfirstentry());
//獲得treemap裡第一個節點(即根據key排序最小的節點)，如果treemap為空，傳回null
final entry<k,v> getfirstentry() {
entry<k,v> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
代碼很簡單，一直往下走，直到找到那個節點，然後傳回即可。這裡為什麼不直接調用getfirtstentry()，而是對外提供firstentry()供外界調用呢？這就說到了exportentry()方法的作用了，因為如果直接調用getfirstentry()方法的話，傳回的entry是可以被修改的，但是經過exportentry()方法包裝過之後就不能修改了，是以這麼做事防止用于修改傳回的entry。我們來看看exportentry()方法是如何對entry對象進行包裝的：
static <k,v> map.entry<k,v> exportentry(treemap.entry<k,v> e) {
return (e == null) ? null :
new abstractmap.simpleimmutableentry<>(e);
public static class simpleimmutableentry<k,v>
implements entry<k,v>, java.io.serializable
{
private static final long serialversionuid = 7138329143949025153l;
private final k key;
private final v value;
public simpleimmutableentry(k key, v value) { //通過key和value初始化對象
this.key = key;
public simpleimmutableentry(entry<? extends k, ? extends v> entry) { //通過傳進來一個entry初始化對象
this.key = entry.getkey();
this.value = entry.getvalue();
public k getkey() {
public v getvalue() {
public v setvalue(v value) { //!!!關鍵地方在這裡，不能setvalue，否則會抛出unsupportedoperationexception異常
throw new unsupportedoperationexception();
public boolean equals(object o) {
map.entry e = (map.entry)o;
return eq(key, e.getkey()) && eq(value, e.getvalue());
public int hashcode() {
return (key == null ? 0 : key.hashcode()) ^
(value == null ? 0 : value.hashcode());
//重寫了tostring方法，傳回key=value形式
public string tostring() {
從上面代碼中可以看出，被這個類包裝過的entry是不允許被修改内容的，這也就是為什麼treemap類不直接把getfirstentry()方法暴露出去，而是提供了firstentry()供外界調用的原因。關于entry的其他類似的方法我就不一一贅述了，我放到源代碼裡分析，都不難了解。如下：
/*********************** 與entry相關的方法 ******************************/
//擷取treemap中鍵為key對應的節點
final entry<k,v> getentry(object key) {
// 若比較器不為null，則通過getentryusingcomparator來獲得
if (comparator != null)
return getentryusingcomparator(key);
if (key == null)
throw new nullpointerexception();
comparable<? super k> k = (comparable<? super k>) key;
entry<k,v> p = root; //若沒有比較器，則正常往下走
while (p != null) {
int cmp = k.compareto(p.key);
if (cmp < 0)
else if (cmp > 0)
p = p.right;
else
return p; //找到了就傳回
return null;
//使用比較器獲得與key對應的entry
final entry<k,v> getentryusingcomparator(object key) {
k k = (k) key;
comparator<? super k> cpr = comparator;
if (cpr != null) {
entry<k,v> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
/*--------------------------------------------------------*/
/*-----------------------------------------------*/
public map.entry<k,v> lastentry() {
return exportentry(getlastentry());
//獲得treemap裡最後一個節點(根據key排序最大的節點)，如果treemap為空，傳回null
final entry<k,v> getlastentry() {
while (p.right != null)
/*------------------------------------------------*/
//彈出第一個節點，即删除
public map.entry<k,v> pollfirstentry() {
entry<k,v> p = getfirstentry();
map.entry<k,v> result = exportentry(p);
deleteentry(p);
return result;
//彈出最後一個節點，即删除
public map.entry<k,v> polllastentry() {
entry<k,v> p = getlastentry();
/*-------------------------------------------------*/
public map.entry<k,v> floorentry(k key) {
return exportentry(getfloorentry(key));
public map.entry<k,v> ceilingentry(k key) {
return exportentry(getceilingentry(key));
//擷取treemap中不小于key的最小的節點；
//若不存在(即treemap中所有節點的鍵都比key大)，就傳回null
final entry<k,v> getceilingentry(k key) {
int cmp = compare(key, p.key);
if (cmp < 0) { //情況1. 若p.key > key
if (p.left != null) //若p有左子節點
p = p.left; //往左下走
return p; //否則傳回p
} else if (cmp > 0) { //情況2：p.key < key
if (p.right != null) {
} else {
// 若 p 不存在右孩子，則找出 p 的後繼節點，并傳回
// 注意：這裡傳回的 “p的後繼節點”有2種可能性：第一，null；第二，treemap中大于key的最小的節點。
// 了解這一點的核心是，getceilingentry是從root開始周遊的。
// 若getceilingentry能走到這一步，那麼，它之前“已經周遊過的節點的key”都 > key。
// 能了解上面所說的，那麼就很容易明白，為什麼“p的後繼節點”又2種可能性了。
entry<k,v> parent = p.parent;
entry<k,v> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else //情況3：p.key = key
return p;
// 擷取treemap中不大于key的最大的節點；
// 若不存在(即treemap中所有節點的鍵都比key小)，就傳回null
// getfloorentry的原理和getceilingentry類似，這裡不再多說。
final entry<k,v> getfloorentry(k key) {
if (cmp > 0) {
if (p.right != null)
} else if (cmp < 0) {
if (p.left != null) {
while (parent != null && ch == parent.left) {
} else
/*--------------------------------------------------*/
public map.entry<k,v> lowerentry(k key) {
return exportentry(getlowerentry(key));
public map.entry<k,v> higherentry(k key) {
return exportentry(gethigherentry(key));
}
// 擷取treemap中大于key的最小的節點。
// 若不存在，就傳回null。
// 請參照getceilingentry來對gethigherentry進行了解。
final entry<k,v> getlowerentry(k key) {
} else {
// 擷取treemap中小于key的最大的節點。
// 請參照getceilingentry來對getlowerentry進行了解。
final entry<k,v> gethigherentry(k key) {
if (cmp < 0) {
if (p.left != null)
/*---------------------------------------------------*/
分析完了entry實體相關的源碼後，我們來看看treemap裡的成員屬性。
/********************* 成員屬性 ****************************/
private final comparator<? super k> comparator; //比較器
private transient entry<k,v> root = null; //實體對象
private transient int size = 0; //紅黑樹節點個數，即entry數
private transient int modcount = 0; //修改次數
/*********************** 構造方法 **************************/
public treemap() { //預設構造方法
comparator = null;
public treemap(comparator<? super k> comparator) { //帶比較器的構造方法
this.comparator = comparator;
public treemap(map<? extends k, ? extends v> m) { //帶map的構造方法，map會為treemap的子類
putall(m);
////帶sortedmap的構造方法，sortedmap會為treemap的子類
public treemap(sortedmap<k, ? extends v> m) {
comparator = m.comparator();
try {
buildfromsorted(m.size(), m.entryset().iterator(), null, null);
} catch (java.io.ioexception cannothappen) {
} catch (classnotfoundexception cannothappen) {
我們可以看出，treemap有四個構造函數，這裡分析一下第三個構造函數，内部調用了putall方法，我們看一下putall方法：
public void putall(map<? extends k, ? extends v> map) {
int mapsize = map.size();//擷取map的大小
//如果treemap大小是0，且map的大小不為0，且map是已排序的key-value對，才執行下面的程式
if (size==0 && mapsize!=0 && map instanceof sortedmap) {
comparator c = ((sortedmap)map).comparator();
if (c == comparator || (c != null && c.equals(comparator))) {
++modcount;
try {
buildfromsorted(mapsize, map.entryset().iterator(),
null, null);
} catch (java.io.ioexception cannothappen) {
} catch (classnotfoundexception cannothappen) {
return;
//否則調用abstractmap中的putall()
//abstractmap中的putall()又會調用treemap的put()方法
super.putall(map);
在putall方法内部，會先進行判斷，如果treemap是空的，且傳進來的map符合條件，則執行if内的語句，然後調用buildfromsorted方法（後面放到源碼中分析）來put進去，否則調用父類的putall方法，父類的putall方法則直接調用treemap的put方法。
如有錯誤之處，歡迎留言指正~
_____________________________________________________________________________________________________________________________________________________
-----樂于分享，共同進步！