一、類繼承圖
二、SortedMap接口概述和使用
SortedMap表示一個維護了key的順序的Map，通過key本身實作的Comparable接口或者SortedMap執行個體初始化時指定Comparator執行個體來排序。如果插入的key沒有實作Comparable接口，也不能被Comparator執行個體比較，則會抛出異ClassCastException。注意實作Comparable或者Comparator接口時，應保證與key的equals()方法保持一緻，即equals()方法相等時，通過Comparable或者Comparator比較的結果也應該是相等的，因為equals()方法是Map接口判斷key相等的基礎。
接口包含的方法如下：
SortedMap覆寫了Map接口中keySet()，values()，entrySet()的方法定義，增加了一條，要求傳回的視圖中的元素時按照鍵值K升序排序的。其他方法的使用參考示例：
public class User {
private String userName;
private Integer age;
public User() {
}
public User(String userName, Integer age) {
this.userName = userName;
this.age = age;
}
public String getUserName() {
return userName;
}
public void setUserName(String userName) {
this.userName = userName;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public String toString() {
return "User{" +
"userName='" + userName + '\'' +
", age=" + age +
'}';
}
}
public class UserComp implements Comparable<UserComp> {
private String userName;
private Integer age;
public UserComp() {
}
public UserComp(String userName, Integer age) {
this.userName = userName;
this.age = age;
}
//注意此處是this-o，如果反過來排序就是降序的
public int compareTo(UserComp o) {
return this.age-o.getAge();
}
public String getUserName() {
return userName;
}
public void setUserName(String userName) {
this.userName = userName;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public String toString() {
return "User{" +
"userName='" + userName + '\'' +
", age=" + age +
'}';
}
}
@Test
public void name() throws Exception {
//String實作了Comparable接口
SortedMap<String,Integer> sortedMap=new TreeMap();
sortedMap.put("a",1);
sortedMap.put("c",1);
sortedMap.put("b",1);
for(String key:sortedMap.keySet()){
System.out.println(key+":"+sortedMap.get(key));
}
}
@Test
public void test3() throws Exception {
//初始化時提供Comparator接口實作
Comparator<User> comparator=new Comparator<User>() {
//注意如果o2-o1,結果就是降序了
public int compare(User o1, User o2) {
return o1.getAge()-o2.getAge();
}
};
SortedMap<User,Integer> sortedMap=new TreeMap(comparator);
sortedMap.put(new User("shl",12),1);
sortedMap.put(new User("shl",13),1);
sortedMap.put(new User("shl",14),1);
for(User key:sortedMap.keySet()){
System.out.println(key+":"+sortedMap.get(key));
}
}
@Test
public void test4() throws Exception {
//UserComp實作了Comparable接口
SortedMap<UserComp,Integer> sortedMap=new TreeMap();
sortedMap.put(new UserComp("shl",12),1);
sortedMap.put(new UserComp("shl",13),1);
sortedMap.put(new UserComp("shl",14),1);
for(UserComp key:sortedMap.keySet()){
System.out.println(key+":"+sortedMap.get(key));
}
}
@Test
public void test5() throws Exception {
SortedMap<Integer,String> sortedMap=new TreeMap();
sortedMap.put(1,"a");
sortedMap.put(2,"a");
sortedMap.put(3,"a");
sortedMap.put(4,"a");
sortedMap.put(5,"a");
sortedMap.put(6,"a");
//SortedMap傳回子Map時都是半包含的，即包含最小值不包含最大值，NavigableMap中可以指定是否起止值
//傳回大于等于1，小于4的子Map
System.out.println("========subMap========");
SortedMap<Integer,String> subMap=sortedMap.subMap(1,4);
for(Integer key:subMap.keySet()){
System.out.println(key+":"+subMap.get(key));
}
//傳回小于5的子Map
System.out.println("========headMap========");
subMap=sortedMap.headMap(5);
for(Integer key:subMap.keySet()){
System.out.println(key+":"+subMap.get(key));
}
//傳回大于等于2的子Map
System.out.println("========tailMap========");
subMap=sortedMap.tailMap(2);
for(Integer key:subMap.keySet()){
System.out.println(key+":"+subMap.get(key));
}
System.out.println("firstKey:"+subMap.firstKey());
System.out.println("lastKey:"+subMap.lastKey());
}
三、NavigableMap接口概述和使用
NavigableMap擴充自SortedMap，增加了一些查找目标key的快捷方法，比如lowerEntry傳回小于，floorEntry傳回小于或者等于， ceilingEntry傳回大于或等于，higherEntry傳回大于給定key的Map.Entry對象。類似的有lowerKey，floorKey，ceilingKey， higherKey傳回符合條件的目标key。擴充了SortedMap的subMap，headMap，tailMap等方法，增加參數可以指定是否包含起止值，且傳回的是SortedMap的更新接口NavigableMap執行個體。增加對降序周遊的支援，通過descendingMap()傳回一個降序排序的視圖，注意預設的升序視圖的周遊比降序視圖要快。接口包含的方法如下：
參考如下示例：
@Test
public void test() throws Exception {
NavigableMap<Integer,String> sortedMap=new TreeMap();
sortedMap.put(1,"a");
sortedMap.put(2,"a");
sortedMap.put(3,"a");
sortedMap.put(4,"a");
sortedMap.put(5,"a");
sortedMap.put(6,"a");
//小于指定key的最大的一個key
Map.Entry<Integer,String> entry=sortedMap.lowerEntry(3);
System.out.println(entry);
//小于或等于指定key的最大的一個key
entry=sortedMap.floorEntry(3);
System.out.println(entry);
//大于指定key的最小的一個key
entry=sortedMap.higherEntry(3);
System.out.println(entry);
//大于等于指定key的最小的一個key
entry=sortedMap.ceilingEntry(3);
System.out.println(entry);
//傳回并移除第一個元素
Map.Entry first=sortedMap.pollFirstEntry();
System.out.println(first.getKey());
//傳回并移除最後一個元素
Map.Entry last=sortedMap.pollLastEntry();
System.out.println(last.getKey());
//表示不包含2，包含5
NavigableMap<Integer,String> subMap= sortedMap.subMap(2,false,5 ,true);
for(Integer key:subMap.keySet()){
System.out.println("key="+key+",value="+subMap.get(key));
}
}
@Test
public void test2() throws Exception {
NavigableMap<Integer,String> sortedMap=new TreeMap();
sortedMap.put(1,"a");
sortedMap.put(2,"a");
sortedMap.put(3,"a");
sortedMap.put(4,"a");
sortedMap.put(5,"a");
sortedMap.put(6,"a");
//預設是升序
for(Integer key:sortedMap.keySet()){
System.out.println(key+":"+sortedMap.get(key));
}
//傳回降序排列的key視圖
NavigableMap<Integer,String> desMap=sortedMap.descendingMap();
for(Integer key:desMap.keySet()){
System.out.println(key+":"+sortedMap.get(key));
}
//效果等同于descendingMap
for(Integer key:sortedMap.descendingKeySet()){
System.out.println(key+":"+sortedMap.get(key));
}
}
四、TreeMap接口實作源碼解讀
TreeMap是一個基于紅黑樹結構的NavigableMap接口實作，因為key必須可比，是以key不能是null，value可以是null。同HashMap，非線程安全，周遊時修改元素會快讀失敗。
1、全局屬性
//用于比較K順序，如果K實作了Comparable接口，可以為null
private final Comparator<? super K> comparator;
//紅黑樹的根節點
private transient Entry<K,V> root;
//節點個數
private transient int size = 0;
//修改次數
private transient int modCount = 0;
//節點顔色
private static final boolean RED = false;
private static final boolean BLACK = true;
//視圖屬性
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;
//表示無上限的常量
private static final Object UNBOUNDED = new Object();
2、構造方法
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
//判斷m是否是SortedMap執行個體，如果是利用buildFromSorted方法初始化，否則将Map中鍵值對逐一put到TreeMap中
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
//根據一個排序好的SortedMap建構紅黑樹
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
//如果目前TreeMap size為0，目标map size大于0且是SortedMap
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
//兩個Map的比較器一緻
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;
}
}
//周遊map将其中的元素逐一添加到TreeMap中
super.putAll(map);
}
3、紅黑樹節點實作
/**
* 基于紅黑樹節點的鍵值對的标準實作
*/
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
//左節點
Entry<K,V> left;
//右節點
Entry<K,V> right;
//父節點
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() {
return key;
}
public V getValue() {
return value;
}
//setValue時會傳回原來的值
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
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() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
4、元素插入
public V put(K key, V value) {
Entry<K,V> t = root;
//根節點為空，即第一次插入
if (t == null) {
//判斷該key是否可以比較，如果不能比較此處會抛出異常
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
//如果不存在相同key的節點則t為null跳出循環，parent為目标節點的父節點，cmp為跟父節點key比較的結果
do {
//從根節點開始往下周遊
parent = t;
cmp = cpr.compare(key, t.key);
//小于根節點，走左子樹繼續比較
if (cmp < 0)
t = t.left;
//大于根節點，走右子樹繼續比較
else if (cmp > 0)
t = t.right;
else
//找到key相同的，覆寫并傳回原值
return t.setValue(value);
} while (t != null);
}
else {
//非空判斷
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//不存在相同的key，此時parent為目标key的父節點
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;
}
5、元素查找
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// 基于comparator周遊紅黑樹
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
//如果comparator為空且K未實作Comparable接口，此處會抛出ClassCastException異常
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
//周遊紅黑樹查找key
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
//小于父節點的key，在左子樹中繼續查找
if (cmp < 0)
p = p.left;
//大于父節點的key，在右子樹中繼續查找
else if (cmp > 0)
p = p.right;
else
//key值相等則傳回該節點
return p;
}
return null;
}
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
//周遊紅黑樹查找key
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;
}
}
return null;
}
6、範圍查找
/**
* 擷取TreeMap中升序排序最前的鍵值對
*/
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
//周遊紅黑樹找到最左邊的一個左節點
while (p.left != null)
p = p.left;
return p;
}
/**
* 擷取TreeMap中升序排序最後的鍵值對
*/
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
//周遊紅黑樹找到最右邊的一個右節點
while (p.right != null)
p = p.right;
return p;
}
/**
* 傳回比t大的最小的元素
*/
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return 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;
/
//不斷往上周遊，直到目前節點為左節點為止，此時父節點的key值大于目前節點，傳回該父節點
//如果當節點為最右邊的節點，不斷往上周遊時傳回的null，即沒有下一個元素
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
/**
* 傳回目前元素在排序順序中的前一個元素，即比他小的最大的元素
*/
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.left != null) {
//如果存在左子樹，找左子樹中最右邊的一個節點
Entry<K,V> p = t.left;
while (p.right != null)
p = p.right;
return p;
} else {
//沒有左子樹，因為右子樹中節點都比目前節點大，是以隻能往上查找
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
//不斷往上周遊，直到目前節點為右節點為止，此時父節點的key小于目前節點，傳回該父節點
while (p != null && ch == p.left) {
ch = p;
p = p.parent;
}
return p;
}
}
/**
* 傳回大于或者等于目前key的最小的元素
*/
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
//小于父節點，周遊左子樹
if (cmp < 0) {
//左子樹不為空則在左子樹中繼續查找
if (p.left != null)
p = p.left;
//左子樹為空表示沒有比key更小的節點了，傳回該節點
else
return p;
} else if (cmp > 0) {
//右子樹不為空，周遊右子樹
if (p.right != null) {
p = p.right;
} else {
//右子樹為空，左子樹中所有節點比目前節點小，是以隻能往上查找大于key的最小元素
//不斷往上周遊，直到目前節點為父節點的左節點，此時父節點的key大于目标key值，傳回該父節點
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
//等于該節點
return p;
}
return null;
}
/**
傳回大于目标key的最小的一個key
*/
final Entry<K,V> getHigherEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
/**
* 傳回小于或者等于指定key的最大的元素
*/
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
//父節點的key值小于目标節點，因為左子樹的所有節點都比父節點小，是以要從右子樹中查找小于或者等于目标key的最大元素
if (cmp > 0) {
//右節點不為空，繼續在右子樹中查找
if (p.right != null)
p = p.right;
else
//右節點沒了，即目前節點是紅黑樹中最底層的右節點，小于key最大的一個節點
return p;
} else if (cmp < 0) {
//父節點的key值大于目标key，右子樹中所有節點比父節點大，隻能在左子樹中查找小于或等于目标key的最大元素
if (p.left != null) {
p = p.left;
} else {
//左子樹為空，隻能往上周遊查找小于目标key的最大節點
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
//一直往上周遊，直到目前節點為父節點的右節點，此時父節點的key值小于目标節點，傳回該父節點
//如果一直是左節點，周遊到根節點則傳回null，表示沒有比目标key小的節點
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
//等于目标key值，傳回該節點
return p;
}
return null;
}
/**
傳回小于目标key的最大的key
*/
final Entry<K,V> getLowerEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
7、擷取子Map方法
TreeMap中擷取子Map的方法傳回的執行個體都是内部實作的AscendingSubMap執行個體，該執行個體繼承自了NavigableSubMap，NavigableSubMap是TreeMap實作NavigableMap接口的内部類，子Map在指定範圍内周遊的核心實作在NavigableSubMap中，主要還是依賴于TreeMap中範圍查找的相關方法。
abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, java.io.Serializable {
private static final long serialVersionUID = -2102997345730753016L;
//父級TreeMap
final TreeMap<K,V> m;
//lo，hi表示取值範圍的最小值和最大值
final K lo, hi;
//fromStart為true表示不考慮起始值，從整個排序的最小值開始，toEnd為true表示不考慮終止值，一直到整個排序的最大值
final boolean fromStart, toEnd;
//loInclusive表示取值範圍是否包含最小值，hiInclusive表示取值範圍是否包含最大值，預設是不包含
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");
} else {
//存在最小值，判斷該key是否可比
if (!fromStart) // type check
m.compare(lo, lo);
/存在最大值，判斷該key是否可比
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;
}
//是否小于最小值
final boolean tooLow(Object key) {
if (!fromStart) {
int c = m.compare(key, lo);
if (c < 0 || (c == 0 && !loInclusive))
return true;
}
return false;
}
//是否大于最小值
final boolean tooHigh(Object key) {
if (!toEnd) {
int c = m.compare(key, hi);
if (c > 0 || (c == 0 && !hiInclusive))
return true;
}
return false;
}
//判斷目标key是否在取值範圍内，根據loInclusive和hiInclusive判斷是否包含起始值
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);
}
//該方法主要用于擷取子Map的子Map
final boolean inRange(Object key, boolean inclusive) {
//如果inclusive為true，需要父Map是否包含目标key值，如果父Map不包含，而子Map包含則傳回false
//如果inclusive為false，子Map不包含目标key值，則隻需要判斷目标key是否在父Map的取值範圍内即可
return inclusive ? inRange(key) : inClosedRange(key);
}
//擷取設定範圍的最小值
final TreeMap.Entry<K,V> absLowest() {
TreeMap.Entry<K,V> e =
(fromStart ? m.getFirstEntry() :
(loInclusive ? m.getCeilingEntry(lo) :
m.getHigherEntry(lo)));
return (e == null || tooHigh(e.key)) ? null : e;
}
//擷取設定範圍的最大值
final TreeMap.Entry<K,V> absHighest() {
TreeMap.Entry<K,V> e =
(toEnd ? m.getLastEntry() :
(hiInclusive ? m.getFloorEntry(hi) :
m.getLowerEntry(hi)));
return (e == null || tooLow(e.key)) ? null : e;
}
//擷取大于等于目前key的最小元素，如果低于最小值傳回最小值
final TreeMap.Entry<K,V> absCeiling(K key) {
if (tooLow(key))
return absLowest();
TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
//擷取大于目前key的最小元素，如果低于最小值傳回最小值
final TreeMap.Entry<K,V> absHigher(K key) {
if (tooLow(key))
return absLowest();
TreeMap.Entry<K,V> e = m.getHigherEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
//擷取小于等于目前key的最小元素，如果大于最大值傳回最大值
final TreeMap.Entry<K,V> absFloor(K key) {
if (tooHigh(key))
return absHighest();
TreeMap.Entry<K,V> e = m.getFloorEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
//擷取小于目前key的最小元素，如果大于最大值傳回最大值
final TreeMap.Entry<K,V> absLower(K key) {
if (tooHigh(key))
return absHighest();
TreeMap.Entry<K,V> e = m.getLowerEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
//擷取設定範圍的上限值
final TreeMap.Entry<K,V> absHighFence() {
return (toEnd ? null : (hiInclusive ?
m.getHigherEntry(hi) :
m.getCeilingEntry(hi)));
}
//擷取設定範圍的下限值
final TreeMap.Entry<K,V> absLowFence() {
return (fromStart ? null : (loInclusive ?
m.getLowerEntry(lo) :
m.getFloorEntry(lo)));
}
// View classes
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;
//周遊計算size
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<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
//不在範圍内傳回false
if (!inRange(key))
return false;
TreeMap.Entry<?,?> node = m.getEntry(key);
return node != null &&
valEquals(node.getValue(), entry.getValue());
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
if (!inRange(key))
return false;
TreeMap.Entry<K,V> node = m.getEntry(key);
if (node!=null && valEquals(node.getValue(),
entry.getValue())) {
m.deleteEntry(node);
return true;
}
return false;
}
}
/**
* 抽象實作類
*/
abstract class SubMapIterator<T> implements Iterator<T> {
TreeMap.Entry<K,V> lastReturned;
TreeMap.Entry<K,V> next;
final Object fenceKey;
int expectedModCount;
//first和fence分别辨別最小值和最大值，即在該範圍内周遊
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;
//如果e為null或者是邊界元素則抛出異常
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() {
TreeMap.Entry<K,V> e = next;
//如果e為null或者是邊界元素則抛出異常
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
//找到目前元素的上一個元素
next = predecessor(e);
lastReturned = e;
return e;
}
//順序周遊時移除元素
final void removeAscending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 删除lastReturned節點時，如果該節點的左右節點都存在，則該節點實際不會删除，隻是該節點的key/value會被改寫成
//下一個節點的key/value，是以此時next會等于lastReturned
//如果是倒序周遊，因為下一個元素時被删除元素的上一個元素是以不存在next = lastReturned
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
}
final void removeDescending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
}
}
//順序周遊的子類
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();
}
}
//倒序周遊的子類
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
super(last, fence);
}
public Map.Entry<K,V> next() {
return prevEntry();
}
public void remove() {
removeDescending();
}
}
}
/**
* @serial include
*/
static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
private static final long serialVersionUID = 912986545866124060L;
AscendingSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
public Comparator<? super K> comparator() {
return m.comparator();
}
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
//對fromKey和toKey做範圍判斷，即子Map的取值範圍必須在原子Map的取值範圍内
if (!inRange(fromKey, fromInclusive))
throw new IllegalArgumentException("fromKey out of range");
if (!inRange(toKey, toInclusive))
throw new IllegalArgumentException("toKey out of range");
//因為入參類型是TreeMap，是以此處隻能把父Map初始化的TreeMap執行個體繼續傳給子Map
return new AscendingSubMap<>(m,
false, fromKey, fromInclusive,
false, toKey, toInclusive);
}
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
//校驗toKey是否在原子Map的取值範圍内
if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
//注意此處把父Map的fromStart，lo，loInclusive三個參數繼續傳遞到子Map中，即子Map依然在原來的父子Map的取值範圍内
return new AscendingSubMap<>(m,
fromStart, lo, loInclusive,
false, toKey, inclusive);
}
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
if (!inRange(fromKey, inclusive))
throw new IllegalArgumentException("fromKey out of range");
return new AscendingSubMap<>(m,
false, fromKey, inclusive,
toEnd, hi, hiInclusive);
}
public NavigableMap<K,V> descendingMap() {
NavigableMap<K,V> mv = descendingMapView;
return (mv != null) ? mv :
(descendingMapView =
new DescendingSubMap<>(m,
fromStart, lo, loInclusive,
toEnd, hi, hiInclusive));
}
Iterator<K> keyIterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
Spliterator<K> keySpliterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
//注意傳回倒序周遊的疊代器時的入參，last即最大值，fence即最小值
Iterator<K> descendingKeyIterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
final class AscendingEntrySetView extends EntrySetView {
public Iterator<Map.Entry<K,V>> iterator() {
return new SubMapEntryIterator(absLowest(), absHighFence());
}
}
public Set<Map.Entry<K,V>> entrySet() {
EntrySetView es = entrySetView;
return (es != null) ? es : (entrySetView = 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); }
}
/**
* @serial include
*/
static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
private static final long serialVersionUID = 912986545866120460L;
DescendingSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
//此處反轉comparator主要用于子Map插入元素，正常倒序周遊用不到該comparator
private final Comparator<? super K> reverseComparator =
Collections.reverseOrder(m.comparator);
public Comparator<? super K> comparator() {
return reverseComparator;
}
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 DescendingSubMap<>(m,
false, toKey, toInclusive,
false, fromKey, fromInclusive);
}
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
return new DescendingSubMap<>(m,
false, toKey, inclusive,
toEnd, hi, hiInclusive);
}
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
if (!inRange(fromKey, inclusive))
throw new IllegalArgumentException("fromKey out of range");
return new DescendingSubMap<>(m,
fromStart, lo, loInclusive,
false, fromKey, inclusive);
}
public NavigableMap<K,V> descendingMap() {
NavigableMap<K,V> mv = descendingMapView;
return (mv != null) ? mv :
(descendingMapView =
new AscendingSubMap<>(m,
fromStart, lo, loInclusive,
toEnd, hi, hiInclusive));
}
//注意此處的入參
Iterator<K> keyIterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
Spliterator<K> keySpliterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
Iterator<K> descendingKeyIterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
final class DescendingEntrySetView extends EntrySetView {
public Iterator<Map.Entry<K,V>> iterator() {
return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
}
}
public Set<Map.Entry<K,V>> entrySet() {
EntrySetView es = entrySetView;
return (es != null) ? es : (entrySetView = 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); }
}
8、擷取視圖方法
同HashMap，視圖内部類的實作在疊代器，疊代器的實作與子Map中疊代器的實作基本是一樣的。
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() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = predecessor(e);
lastReturned = e;
return e;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 删除時如果該節點的左右節點都存在時，該節點不會被删除而是替換成繼承節點的值，該節點就是下一次next()傳回的節點，是以此處将next置為該節點
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
deleteEntry(lastReturned);
expectedModCount = modCount;
lastReturned = null;
}
}
final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
EntryIterator(Entry<K,V> first) {
super(first);
}
public Map.Entry<K,V> next() {
return nextEntry();
}
}
final class ValueIterator extends PrivateEntryIterator<V> {
ValueIterator(Entry<K,V> first) {
super(first);
}
public V next() {
return nextEntry().value;
}
}
final class KeyIterator extends PrivateEntryIterator<K> {
KeyIterator(Entry<K,V> first) {
super(first);
}
public K next() {
return nextEntry().key;
}
}
final class DescendingKeyIterator extends PrivateEntryIterator<K> {
DescendingKeyIterator(Entry<K,V> first) {
super(first);
}
public K next() {
return prevEntry().key;
}
//倒序周遊時跟正序不一樣，是以去除了對被删除節點是否左右節點非空的判斷
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = modCount;
}
}
9、buildFromSorted方法實作
此方法遞歸實作的巧妙之處在于充分利用了紅黑樹每個節點下面最多兩個節點的特點，通過對2取整，確定取元素的順序與建構節點的順序一緻。
/**
* 注意此方法是在TreeMap已經完成comparator和size初始化後才調用的，作為建構紅黑樹的快捷方法使用
*
* 注意此處的疊代器是已經升序排序的疊代器，如SortedMap或者SortedSet傳回的
* 此處的對象流str也是已經升序排序的按照key/value寫入的對象流
* 實作政策：根節點是中間元素，通過遞歸，先建構左子樹，然後建構右子樹。
* 注意此處建構的紅黑樹是一個相對簡化的紅黑樹，最底層全部是紅色節點，其餘的都是黑色節點，且根節點的左右子樹元素個數最多查一個
* 此處的lo和hi隻是為了保證元素時按照前後順序從疊代器或者對象流中順序取出而已，并不是元素真的有索引
*
* @param level 目前樹的高度，初始為0
* @param lo 第一個元素的索引，初始為0
* @param hi 最後一個元素的索引，初始為size-1，size為元素個數
* @param redLevel 紅色高度，根據size計算而來
*/
@SuppressWarnings("unchecked")
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
if (hi < lo) return null;
//取中間值，相當于除以2然後取整
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
//第一次lo==mid時，mid=0，該元素是序列中第一個元素，也是最小的一個元素，是紅黑樹中最左邊的左節點
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
K key;
V value;
//從疊代器或者對象流中讀取key/value
if (it != null) {
if (defaultVal==null) {
Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
key = (K)entry.getKey();
value = (V)entry.getValue();
} else {
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
Entry<K,V> middle = new Entry<>(key, value, null);
// 最下面一層的節點為紅色，level會随着遞歸不斷增加，對紅黑樹而言，左子樹跟右子樹的高度
if (level == redLevel)
middle.color = RED;
//建構左子樹
if (left != null) {
middle.left = left;
left.parent = middle;
}
//建構右子樹，第一次執行時mid=1，hi=2
if (mid < hi) {
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
}
return middle;
}
private static int computeRedLevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}