TreeMap源码分析——深入分析（基于JDK1.6）
编者注：本文为历史博文归档；涉及 JDK、框架与工具链版本请以当前官方文档为准。引用外链图片可能失效，阅读时请注意时效性。
内部类概述
TreeMap 共包含十三个内部类，分别是：Values、EntrySet、KeySet、PrivateEntryIterator、EntryIterator、ValueIterator、KeyIterator、DescendingKeyIterator、NavigableSubMap、AscendingSubMap、DescendingSubMap、SubMap 以及 Entry。
其中，Entry 是在 TreeMap 中用于表示树的节点的内部类，已在 《TreeMap 源码分析——基础分析》 中详细分析过。下面将逐一介绍其余内部类以及 TreeMap 中与它们相关的方法。
Values 类
首先来看 Values 类。
// 从类的定义可以看出，Values 是一个集合类
class Values extends AbstractCollection<V> {
// 提供集合类 Values 的迭代器
public Iterator<V> iterator() {
return new ValueIterator(getFirstEntry());
}
// 返回 TreeMap 中保存的节点数
public int size() {
return TreeMap.this.size();
}
// 判断 TreeMap 中是否存在 Value 为 o 的节点
public boolean contains(Object o) {
return TreeMap.this.containsValue(o);
}
// 删除一个对象
public boolean remove(Object o) {
// 遍历 TreeMap
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
// 寻找值相等的节点
if (valEquals(e.getValue(), o)) {
// 删除找到的节点
deleteEntry(e);
return true;
}
}
return false;
}
// 清空 TreeMap
public void clear() {
TreeMap.this.clear();
}
}Values 类实际上是一个代理，多数方法都是直接调用 TreeMap 的方法。在 Values 的 iterator() 方法中返回了一个 ValueIterator 对象，下面来看和迭代器相关的内部类。
迭代器相关内部类
PrivateEntryIterator 是 TreeMap 中和迭代器相关的类的基础，以下是 PrivateEntryIterator 的内容。
abstract class PrivateEntryIterator<T> implements Iterator<T> {
// 指向 next 的引用
Entry<K,V> next;
// 保留对上一次返回节点的引用
Entry<K,V> lastReturned;
int expectedModCount;
// 构造方法，lastReturned 置空，next 指向传入的节点
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 移动到它的继承者
next = successor(e);
// 记录被返回的节点
lastReturned = e;
// 返回原先记录的 next 节点
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();
// deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
/* 如果被删除节点有两个孩子，删除节点 e 的时候 e 的引用会被修改为指向原节点的继承者，
所以这里先保留 next 对 lastReturned 的引用，这样在删除节点后就能获取到继承者的引用，
继而继续遍历树 */
next = lastReturned;
// 删除节点
deleteEntry(lastReturned);
expectedModCount = modCount;
lastReturned = null;
}
}PrivateEntryIterator 类的 prevEntry() 方法用到了 predecessor(Entry<K,V> t) 方法，下面对这个方法进行介绍。
predecessor(Entry<K,V> t) 方法返回传入节点的“前一个”节点，至于前一个节点是哪个节点，这和树的遍历次序相关。根据 successor(Entry<K,V> t) 和 predecessor(Entry<K,V> t) 方法可以推出 TreeMap 中树的遍历次序是中根遍历（左孩子 - 根 - 右孩子，即中序遍历）。
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 {
// 获取 t 的父节点
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
// 沿着右孩子向上查找继承者，直到根节点或找到节点 ch 是其父节点的右孩子的节点
while (p != null && ch == p.left) {
ch = p;
p = p.parent;
}
return p;
}
}下面是 TreeMap 中其它和迭代器相关的内部类。
// EntryIterator 就是树节点的迭代器，和 PrivateEntryIterator 完全一样，
// 因为提供的方法都直接的调用而来父类的方法。
final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
EntryIterator(Entry<K,V> first) {
super(first);
}
public Map.Entry<K,V> next() {
return nextEntry();
}
}
/** Value 的迭代器 */
final class ValueIterator extends PrivateEntryIterator<V> {
ValueIterator(Entry<K,V> first) {
super(first);
}
// next() 方法返回的是节点的 value 值
public V next() {
return nextEntry().value;
}
}
/** Key 迭代器 */
final class KeyIterator extends PrivateEntryIterator<K> {
KeyIterator(Entry<K,V> first) {
super(first);
}
// next() 方法返回的是节点的 key
public K next() {
return nextEntry().key;
}
}
/** 逆序的 Key 迭代器 */
final class DescendingKeyIterator extends PrivateEntryIterator<K> {
DescendingKeyIterator(Entry<K,V> first) {
super(first);
}
// next() 方法返回的是节点的“前任”（按照遍历次序的前一个节点）的 key
public K next() {
return prevEntry().key;
}
}Set 相关内部类
除了迭代器相关的内部类，TreeMap 还有两个和 Set 相关的内部类，分别是 EntrySet 和 KeySet。两个类分别表示节点的集合和键的集合。下面具体看这两个类的实现。
// 继承自 AbstractSet 说明是一个 Set
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
// iterator() 方法返回的是上面介绍过的 EntryIterator 对象
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator(getFirstEntry());
}
// 判断是否包含某个节点的方法
public boolean contains(Object o) {
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());
// 判断是否包含某个对象的标准是存在节点的 key 与传入对象的 key 值，
// 且该节点的 value 也与存入对象的 value 值相等
return p != null && valEquals(p.getValue(), value);
}
// 删除一个对象
public boolean remove(Object o) {
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());
// 如果存在该对象，则进行删除操作并返回 true
if (p != null && valEquals(p.getValue(), value)) {
deleteEntry(p);
return true;
}
// 不存在直接返回 false
return false;
}
// size() 返回的是 TreeMap 中包含的节点的数量
public int size() {
return TreeMap.this.size();
}
// clear() 方法实际调用了 TreeMap 的 clear() 方法，和 size() 方法都是代理方法
public void clear() {
TreeMap.this.clear();
}
}// KeySet 同样继承自 AbstractSet。KeySet 实现了 NavigableSet 接口，
// 意味着是“可导航”的 Set，包含更多的获取指定节点的方法
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() {
if (m instanceof TreeMap)
return ((TreeMap<E,Object>)m).keyIterator();
else
// 这里涉及到的 NavigableSubMap 将在后面介绍
return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
}
public Iterator<E> descendingIterator() {
if (m instanceof TreeMap)
return ((TreeMap<E,Object>)m).descendingKeyIterator();
else
return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
}
// size() 方法返回的是通过构造方法传入的 map 的大小
public int size() {
return m.size();
}
// isEmpty() 判断是否为空也是判断的传入的 map 是否为空
public boolean isEmpty() {
return m.isEmpty();
}
// contains(Object o) 方法判断传入 map 中是否包含这个 key
public boolean contains(Object o) {
return m.containsKey(o);
}
public void clear() {
m.clear();
}
// 因为传入的 map 是 NavigableMap，所以下面这几个方法都是代理方法，调用 map 中相应的方法
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();
}
// 获取传入 map 的比较器
public Comparator<? super E> comparator() {
return m.comparator();
}
// 获取 map 中第一个节点的 key
public E pollFirst() {
Map.Entry<E,Object> e = m.pollFirstEntry();
return e == null ? null : e.getKey();
}
// 获取 map 中最后一个节点的 key
public E pollLast() {
Map.Entry<E,Object> e = m.pollLastEntry();
return e == null ? null : e.getKey();
}
// 删除一个对象，实际上是删除 map 中以这个对象为 key 的一个节点
public boolean remove(Object o) {
int oldSize = size();
m.remove(o);
return size() != oldSize;
}
// 下面的方法都是通过 NavigableMap 和 TreeSet 实现的，
// NavigableMap 将在下文介绍，TreeSet 将另开博文介绍
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<E>(m.headMap(toElement, inclusive));
}
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<E>(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 TreeSet(m.descendingMap());
}
}SubMap 相关内部类
介绍完了两个和 Set 相关的内部类，现在还剩下四个和 SubMap 相关的内部类：NavigableSubMap、AscendingSubMap、DescendingSubMap、SubMap。
NavigableSubMap
首先看 NavigableSubMap，它代码量较大，逻辑较为复杂。
// NavigableSubMap 是一个抽象类，继承了 AbstractMap，实现了 NavigableMap 接口
static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, java.io.Serializable {
// 存储内容的 Map
final TreeMap<K,V> m;
// lowKey、highKey
final K lo, hi;
// 标识 map 的边界是否是 map 的第一个节点和最后一个节点
final boolean fromStart, toEnd;
// 是否包含最低 lo、最高位置 hi
final boolean loInclusive, hiInclusive;
// 通过上面的三组变量可以组成两个三元组表示一个集合的两个端点
// 构造方法
NavigableSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
if (!fromStart && !toEnd) {
// lo>hi 抛出异常
if (m.compare(lo, hi) > 0)
throw new IllegalArgumentException("fromKey > toKey");
} else {
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;
}
// tooLow 判断传入的 key 是否太小
final boolean tooLow(Object key) {
// 如果 fromStart 为 false，需要判断最低边界
if (!fromStart) {
int c = m.compare(key, lo);
// 如果 key<lo 或者相等但是 map 的边界不包含 lo，那么 key 越界了，即小于最小值
if (c < 0 || (c == 0 && !loInclusive))
return true;
}
// 默认返回 false
return false;
}
// 与上面的 tooLow 类似
final boolean tooHigh(Object key) {
if (!toEnd) {
int c = m.compare(key, hi);
if (c > 0 || (c == 0 && !hiInclusive))
return true;
}
return false;
}
// 判断是否在范围内，即满足最低最高限制，结合 tooLow 和 tooHigh 即可
final boolean inRange(Object key) {
return !tooLow(key) && !tooHigh(key);
}
// 是否在封闭的区间内
final boolean inClosedRange(Object key) {
return (fromStart || m.compare(key, lo) >= 0)
&& (toEnd || m.compare(hi, key) >= 0);
}
// 判断是否是在一个区间内
final boolean inRange(Object key, boolean inclusive) {
return inclusive ? inRange(key) : inClosedRange(key);
}
// 获取绝对的最低的节点
final TreeMap.Entry<K,V> absLowest() {
/* 如果 fromStart 为 true，获取第一个节点，否则根据 loInclusive 是否为 true，
即是否包含 lo 来决定获取 Ceiling 节点或 Higher 节点；
getCeilingEntry 意为获取指定 key 的节点或者比指定 key 大的最小节点，如果不存在则返回 null；
getHigherEntry 意为获取比指定 key 大的最小节点，如果不存在，返回 null */
TreeMap.Entry<K,V> e =
(fromStart ? m.getFirstEntry() :
(loInclusive ? m.getCeilingEntry(lo) :
m.getHigherEntry(lo)));
// 判断得到的节点是否为空或者 key 过大
return (e == null || tooHigh(e.key)) ? null : e;
}
// 与 absLowest 类似
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) {
// 如果 key 太小，返回绝对的最小的节点
if (tooLow(key))
return absLowest();
// 获取允许的 key 的极限节点（满足要求的最小的节点）
TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
// 和 absCeiling 类似，只是获取的不包含相等的情况，而是寻找大于 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) {
// 指定的 key 超出了 hi，直接返回绝对的允许的最大的节点
if (tooHigh(key))
return absHighest();
/* getFloorEntry 获取的是指定 key 的节点，如果不存在这样的节点，
就去获取比指定 key 小的最大的节点，如果这样的节点也不存在，返回 null*/
TreeMap.Entry<K,V> e = m.getFloorEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
// 与上面的 absFloor 类似，只是不包含等于的情况
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;
}
// 返回比最大的节点“还要大”的节点（Fence 是栅栏、围栏的意思）
final TreeMap.Entry<K,V> absHighFence() {
/* 如果 toEnd 是 true，那么“围在”它外面的是 null，如果是 false，
根据 hi 是否被包含返回 getHigherEntry 或 getCeilingEntry，
这两个方法意思在上面的方法中说明过了 */
return (toEnd ? null : (hiInclusive ?
m.getHigherEntry(hi) :
m.getCeilingEntry(hi)));
}
// 与 absHighFence 类似
final TreeMap.Entry<K,V> absLowFence() {
return (fromStart ? null : (loInclusive ?
m.getLowerEntry(lo) :
m.getFloorEntry(lo)));
}
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();
// 如果 fromStart、toEnd 都是 true，那么判断空、获取大小都是直接通过 m，
// 不然就必须使用 entrySet() 先获取节点集
public boolean isEmpty() {
return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
}
public int size() {
return (fromStart && toEnd) ? m.size() : entrySet().size();
}
// 判断是否存在 key 先判断范围，在通过 TreeMap 的 containKey 方法来判断
public final boolean containsKey(Object key) {
return inRange(key) && m.containsKey(key);
}
// 添加节点
public final V put(K key, V value) {
// 判断要添加的 key 是否在范围内
if (!inRange(key))
throw new IllegalArgumentException("key out of range");
return m.put(key, value);
}
public final V get(Object key) {
return !inRange(key) ? null : m.get(key);
}
public final V remove(Object key) {
return !inRange(key) ? null : m.remove(key);
}
public final Map.Entry<K,V> ceilingEntry(K key) {
/* exportEntry(TreeMap.Entry<K,V> e) 方法返回的是 Map.Entry<K,V> 对象，
它的 Key 和 Value 和传入的节点的 Key 和 Value 相同 */
return exportEntry(subCeiling(key));
}
public final K ceilingKey(K key) {
// keyOrNull 根据传入的节点是否为 null 返回 null 或节点的 key
// 相当于提供了一个 null 安全的获取 key 的方法
return keyOrNull(subCeiling(key));
}
public final Map.Entry<K,V> higherEntry(K key) {
return exportEntry(subHigher(key));
}
public final K higherKey(K key) {
return keyOrNull(subHigher(key));
}
public final Map.Entry<K,V> floorEntry(K key) {
return exportEntry(subFloor(key));
}
public final K floorKey(K key) {
return keyOrNull(subFloor(key));
}
public final Map.Entry<K,V> lowerEntry(K key) {
return exportEntry(subLower(key));
}
public final K lowerKey(K key) {
return keyOrNull(subLower(key));
}
public final K firstKey() {
return key(subLowest());
}
public final K lastKey() {
return key(subHighest());
}
public final Map.Entry<K,V> firstEntry() {
return exportEntry(subLowest());
}
public final Map.Entry<K,V> lastEntry() {
return exportEntry(subHighest());
}
// 返回并删除第一个节点
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;
}
// 返回并删除最后一个节点
public final Map.Entry<K,V> pollLastEntry() {
TreeMap.Entry<K,V> e = subHighest();
Map.Entry<K,V> result = exportEntry(e);
if (e != null)
m.deleteEntry(e);
return result;
}
// 这些都是视图
transient NavigableMap<K,V> descendingMapView = null;
transient EntrySetView entrySetView = null;
transient KeySet<K> navigableKeySetView = null;
// 返回 TreeMap 的 KeySet
public final NavigableSet<K> navigableKeySet() {
KeySet<K> nksv = navigableKeySetView;
return (nksv != null) ? nksv :
(navigableKeySetView = new TreeMap.KeySet(this));
}
public final Set<K> keySet() {
return navigableKeySet();
}
// 逆序的 KeySet
public NavigableSet<K> descendingKeySet() {
return descendingMap().navigableKeySet();
}
// 返回一个子 Map
public final SortedMap<K,V> subMap(K fromKey, K toKey) {
return subMap(fromKey, true, toKey, false);
}
// 下面这几个方法会在后面给出分析
public final SortedMap<K,V> headMap(K toKey) {
return headMap(toKey, false);
}
public final SortedMap<K,V> tailMap(K fromKey) {
return tailMap(fromKey, true);
}
// 视图类
abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
private transient int size = -1, sizeModCount;
// 返回子 Map 的大小
public int size() {
// 如果 fromStart 和 toEnd 都是 true，返回的是 m 的 size
if (fromStart && toEnd)
return m.size();
// size=-1 或标记 size 不同，重新计算一次 size
if (size == -1 || sizeModCount != m.modCount) {
sizeModCount = m.modCount;
size = 0;
Iterator i = iterator();
while (i.hasNext()) {
size++;
i.next();
}
}
return size;
}
// 判断 EntrySet 是否为空
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();
// key 不在范围内，返回 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<K,V> entry = (Map.Entry<K,V>) o;
K key = entry.getKey();
if (!inRange(key))
return false;
TreeMap.Entry<K,V> node = m.getEntry(key);
// 找到节点并移除，返回 true
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;
// “栅栏”key（如果是向大的方向遍历，不能访问 key 大于等于 fenceKey 的节点；
// 如果是向小的方向遍历，不能访问 key 小于等于 fenceKey 的节点）
final K fenceKey;
int expectedModCount;
// 构造方法
SubMapIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
expectedModCount = m.modCount;
lastReturned = null;
next = first;
fenceKey = fence == null ? null : fence.key;
}
// 判断是否还有下一个节点
public final boolean hasNext() {
// 与普通的 hasNext 的判断不同的是这里必须判断 next 的 key 是否超出了 fenceKey
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() {
TreeMap.Entry<K,V> e = next;
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
next = predecessor(e);
lastReturned = e;
return e;
}
// 删除节点后可以继续遍历剩余的节点，因为删除前用 next 保留了 lastReturned 节点，
// 而这个节点在删除操作的过程中被替换成了它的继承者
final void removeAscending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
if (lastReturned.left != null && lastReturned.right != null)
// next 指向 lastReturned 所指向的节点，这个节点的内容在删除 lastReturned 的时候被改变了
next = lastReturned;
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
}
// 删除之后 next 指向的节点其实被删除了，不能继续迭代访问
final void removeDescending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
}
}
// 下面的几个内部类很简单，都是对 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();
}
}
final class SubMapKeyIterator extends SubMapIterator<K> {
SubMapKeyIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
super(first, fence);
}
public K next() {
return nextEntry().key;
}
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();
}
}
final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
super(last, fence);
}
public K next() {
return prevEntry().key;
}
public void remove() {
removeDescending();
}
}
}NavigableSubMap 类算是看了一遍，很复杂，自身是个内部类，它里面还包含了好几个类。理解它的代码需要部分 TreeMap 中的其他代码的深入理解，如涉及到的 deleteEntry 等方法（见 《TreeMap 源码分析——基础分析》）。
下面看 TreeMap 的其他内部类，它们是 NavigableSubMap 的子类。
AscendingSubMap
// AscendingSubMap 继承自 NavigableSubMap
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();
}
// “截取”子 Map
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，headMap 通过构造方法便可以实现
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
return new AscendingSubMap(m,
fromStart, lo, loInclusive,
false, toKey, inclusive);
}
// 和 headMap 类似
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);
}
// 这个方法涉及到 DescendingSubMap 类的构造方法，在下面会介绍到
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());
}
Iterator<K> descendingKeyIterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
// AscendingEntrySetView 是一个视图类，重写了父类的 iterator() 方法，
// 调用 SubMapEntryIterator 构造迭代器
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 : 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); }
}DescendingSubMap
// DescendingSubMap 也继承自 NavigableSubMap，和上面的 AscendingSubMap 对应
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);
}
// 构造一个“相反”的比较器
private final Comparator<? super K> reverseComparator =
Collections.reverseOrder(m.comparator);
// 获取的比较器是“相反”的比较器，比较结果会对调
public Comparator<? super K> comparator() {
return reverseComparator;
}
// subMap 方法和 AscendingSubMap 类中类似
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);
}
// 与 AscendingSubMap 中其实是相反的
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
// 因为 DescendingSubMap 表示的是逆序的 map，所以其实是通过获取原序的尾部
return new DescendingSubMap(m,
false, toKey, inclusive,
toEnd, hi, hiInclusive);
}
// 与 headMap 对应，tailMap 其实获取的是原序中的头部
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));
}
// 剩余内容和 AscendingSubMap 很类似，就不说了
Iterator<K> keyIterator() {
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 : 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
最后一个内部类是 SubMap，它比较特别。这个类存在仅仅为了序列化兼容之前的版本（不支持 NavigableMap 的 TreeMap）。它被映射成一个旧版本 AscendingSubMap 子映射到一个新版本。这个类是从来没有以其他方式使用。
// SubMap 继承自 AbstractMap；
// 这个类存在仅仅为了序列化兼容之前的版本不支持 NavigableMap TreeMap。
// 它被翻译成一个旧版本 AscendingSubMap 子映射到一个新版本。
// 这个类是从来没有以其他方式使用。
private class SubMap extends AbstractMap<K,V>
implements SortedMap<K,V>, java.io.Serializable {
private static final long serialVersionUID = -6520786458950516097L;
// 标识是否从 map 的开始到结尾都属于子 map
private boolean fromStart = false, toEnd = false;
// 开始位置和结束位置的 key
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(); }
}总结
结合上面的内部类分析和 《TreeMap 源码分析——基础分析》，对 TreeMap 的实现应该有个大致轮廓。不过 TreeMap 的代码很长很复杂，不自己看一遍分析一边，很难想明白，很难理解进去。
由于 TreeMap 实现复杂，若有疏漏之处，欢迎读者指正。
说明
- 版本适用性：本文基于 JDK 1.6 源码进行分析。现代 JDK 版本（如 JDK 8、11、17 等）中 TreeMap 的核心逻辑保持一致，但内部实现细节、方法签名或优化策略可能有所调整，请以当前官方文档为准。
- 链接时效：文中引用的外部链接可能随时间失效，如遇链接无法访问，请通过搜索引擎查找相关归档内容。
版权声明：本文为原创文章，版权归 戴老师的博客 所有，转载请联系博主获得授权。
本文地址：https://1diff.fun/archives/treemap-yuan-ma-fen-xi--shen-ru-fen-xi--ji-yu-jdk16.html
如果对本文有什么问题或疑问都可以在评论区留言，我看到后会尽量解答。
