Map(三)：TreeMap

TreeMap是基于红黑树（一种自平衡的二叉查找树）实现的一个保证有序性的Map，在继承关系结构图中可以得知TreeMap实现了NavigableMap接口，而该接口又继承了SortedMap接口，我们先来看看这两个接口定义了一些什么功能。

SortedMap

首先是SortedMap接口，实现该接口的实现类应当按照自然排序保证key的有序性，所谓自然排序即是根据key的compareTo()函数（需要实现Comparable接口）或者在构造函数中传入的Comparator实现类来进行排序，集合视图遍历元素的顺序也应当与key的顺序一致。SortedMap接口还定义了以下几个有效利用有序性的函数：

package java.util;

public interface SortedMap<K,V> extends Map<K,V> {

/**

* 用于在此Map中对key进行排序的比较器，如果为null，则使用key的compareTo()函数进行比较。

*/

Comparator<? super K> comparator();

/**

* 返回一个key的范围为从fromKey到toKey的局部视图（包括fromKey，不包括toKey，包左不包右），

* 如果fromKey和toKey是相等的，则返回一个空视图。

* 返回的局部视图同样是此Map的集合视图，所以对它的操作是会与Map互相影响的。

*/

SortedMap<K,V> subMap(K fromKey, K toKey);

/**

* 返回一个严格地小于toKey的局部视图。

*/

SortedMap<K,V> headMap(K toKey);

/**

* 返回一个大于或等于fromKey的局部视图。

*/

SortedMap<K,V> tailMap(K fromKey);

/**

* 返回当前Map中的第一个key（最小）。

*/

K firstKey();

/**

* 返回当前Map中的最后一个key（最大）。

*/

K lastKey();

Set<K> keySet();

Collection<V> values();

Set<Map.Entry<K, V>> entrySet();

}

NavigableMap

然后是SortedMap的子接口NavigableMap，该接口扩展了一些用于导航（Navigation）的方法，像函数lowerEntry(key)会根据传入的参数key返回一个小于key的最大的一对键值对，例如，我们如下调用lowerEntry(6)，那么将返回key为5的键值对，如果没有key为5，则会返回key为4的键值对，以此类推，直到返回null（实在找不到的情况下）。

public static void main(String[] args) {

NavigableMap<Integer, Integer> map = new TreeMap<>();

for (int i = 0; i < 10; i++)

map.put(i, i);

assert map.lowerEntry(6).getKey() == 5;

assert map.lowerEntry(5).getKey() == 4;

assert map.lowerEntry(0).getKey() == null;

}

NavigableMap定义的都是一些类似于lowerEntry(key)的方法和以逆序、升序排序的集合视图，这些方法利用有序性实现了相比SortedMap接口更加灵活的操作。

package java.util;

public interface NavigableMap<K,V> extends SortedMap<K,V> {

/**

* 返回一个小于指定key的最大的一对键值对，如果找不到则返回null。

*/

Map.Entry<K,V> lowerEntry(K key);

/**

* 返回一个小于指定key的最大的一个key，如果找不到则返回null。

*/

K lowerKey(K key);

/**

* 返回一个小于或等于指定key的最大的一对键值对，如果找不到则返回null。

*/

Map.Entry<K,V> floorEntry(K key);

/**

* 返回一个小于或等于指定key的最大的一个key，如果找不到则返回null。

*/

K floorKey(K key);

/**

* 返回一个大于或等于指定key的最小的一对键值对，如果找不到则返回null。

*/

Map.Entry<K,V> ceilingEntry(K key);

/**

* 返回一个大于或等于指定key的最小的一个key，如果找不到则返回null。

*/

K ceilingKey(K key);

/**

* 返回一个大于指定key的最小的一对键值对，如果找不到则返回null。

*/

Map.Entry<K,V> higherEntry(K key);

/**

* 返回一个大于指定key的最小的一个key，如果找不到则返回null。

*/

K higherKey(K key);

/**

* 返回该Map中最小的键值对，如果Map为空则返回null。

*/

Map.Entry<K,V> firstEntry();

/**

* 返回该Map中最大的键值对，如果Map为空则返回null。

*/

Map.Entry<K,V> lastEntry();

/**

* 返回并删除该Map中最小的键值对，如果Map为空则返回null。

*/

Map.Entry<K,V> pollFirstEntry();

/**

* 返回并删除该Map中最大的键值对，如果Map为空则返回null。

*/

Map.Entry<K,V> pollLastEntry();

/**

* 返回一个以当前Map降序（逆序）排序的集合视图

*/

NavigableMap<K,V> descendingMap();

/**

* 返回一个包含当前Map中所有key的集合视图，该视图中的key以升序（正序）排序。

*/

NavigableSet<K> navigableKeySet();

/**

* 返回一个包含当前Map中所有key的集合视图，该视图中的key以降序（逆序）排序。

*/

NavigableSet<K> descendingKeySet();

/**

* 与SortedMap.subMap基本一致，区别在于多的两个参数fromInclusive和toInclusive，

* 它们代表是否包含from和to，如果fromKey与toKey相等，并且fromInclusive与toInclusive

* 都为true，那么不会返回空集合。

*/

NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,

K toKey, boolean toInclusive);

/**

* 返回一个小于或等于（inclusive为true的情况下）toKey的局部视图。

*/

NavigableMap<K,V> headMap(K toKey, boolean inclusive);

/**

* 返回一个大于或等于（inclusive为true的情况下）fromKey的局部视图。

*/

NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

/**

* 等价于subMap(fromKey, true, toKey, false)。

*/

SortedMap<K,V> subMap(K fromKey, K toKey);

/**

* 等价于headMap(toKey, false)。

*/

SortedMap<K,V> headMap(K toKey);

/**

* 等价于tailMap(fromKey, true)。

*/

SortedMap<K,V> tailMap(K fromKey);

}

NavigableMap接口相对于SortedMap接口来说灵活了许多，正因为TreeMap也实现了该接口，所以在需要数据有序而且想灵活地访问它们的时候，使用TreeMap就非常合适了。

红黑树

上文我们提到TreeMap的内部实现基于红黑树，而红黑树又是二叉查找树的一种。二叉查找树是一种有序的树形结构，优势在于查找、插入的时间复杂度只有O(log n)，特性如下：

任意节点最多含有两个子节点。
任意节点的左、右节点都可以看做为一棵二叉查找树。
如果任意节点的左子树不为空，那么左子树上的所有节点的值均小于它的根节点的值。
如果任意节点的右子树不为空，那么右子树上的所有节点的值均大于它的根节点的值。
任意节点的key都是不同的。

尽管二叉查找树看起来很美好，但事与愿违，二叉查找树在极端情况下会变得并不是那么有效率，假设我们有一个有序的整数序列：1,2,3,4,5,6,7,8,9,10,...，如果把这个序列按顺序全部插入到二叉查找树时会发生什么呢？二叉查找树会产生倾斜，序列中的每一个元素都大于它的根节点（前一个元素），左子树永远是空的，那么这棵二叉查找树就跟一个普通的链表没什么区别了，查找操作的时间复杂度只有O(n)。

为了解决这个问题需要引入自平衡的二叉查找树，所谓自平衡，即是在树结构将要倾斜的情况下进行修正，这个修正操作被称为旋转，通过旋转操作可以让树趋于平衡。

红黑树是平衡二叉查找树的一种实现，它的名字来自于它的子节点是着色的，每个子节点非黑即红，由于只有两种颜色（两种状态），一般使用boolean来表示，下面为TreeMap中实现的Entry，它代表红黑树中的一个节点：

// Red-black mechanics

private static final boolean RED = false;

private static final boolean BLACK = true;

/**

* Node in the Tree. Doubles as a means to pass key-value pairs back to

* user (see Map.Entry).

*/

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;

/**

* Make a new cell with given key, value, and parent, and with

* {@code null} child links, and BLACK color.

*/

Entry(K key, V value, Entry<K,V> parent) {

this.key = key;

this.value = value;

this.parent = parent;

}

/**

* Returns the key.

*

* @return the key

*/

public K getKey() {

return key;

}

/**

* Returns the value associated with the key.

*

* @return the value associated with the key

*/

public V getValue() {

return value;

}

/**

* Replaces the value currently associated with the key with the given

* value.

*

* @return the value associated with the key before this method was

* called

*/

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;

}

任何平衡二叉查找树的查找操作都是与二叉查找树是一样的，因为查找操作并不会影响树的结构，也就不需要进行修正，代码如下：

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();

@SuppressWarnings("unchecked")

Comparable<? super K> k = (Comparable<? super K>) key;

Entry<K,V> p = root;

// 从根节点开始，不断比较key的大小进行查找

while (p != null) {

int cmp = k.compareTo(p.key);

if (cmp < 0) // 小于，转向左子树

p = p.left;

else if (cmp > 0) // 大于，转向右子树

p = p.right;

else

return p;

}

return null; // 没有相等的key，返回null

}

而插入和删除操作与平衡二叉查找树的细节是息息相关的，关于红黑树的实现细节，我之前写过的一篇博客红黑树的那点事儿已经讲的很清楚了，对这方面不了解的读者建议去阅读一下，就不在这里重复叙述了。

集合视图

最后看一下TreeMap的集合视图的实现，集合视图一般都是实现了一个封装了当前实例的类，所以对集合视图的修改本质上就是在修改当前实例，TreeMap也不例外。

TreeMap的headMap()、tailMap()以及subMap()函数都返回了一个静态内部类AscendingSubMap，从名字上也能猜出来，为了支持倒序，肯定也还有一个DescendingSubMap，它们都继承于NavigableSubMap，一个继承AbstractMap并实现了NavigableMap的抽象类：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>

implements NavigableMap<K,V>, java.io.Serializable {

private static final long serialVersionUID = -2102997345730753016L;

final TreeMap<K,V> m;

/**

* (fromStart, lo, loInclusive) 与 (toEnd, hi, hiInclusive)代表了两个三元组，

* 如果fromStart为true，那么范围的下限（绝对）为map（被封装的TreeMap）的起始key，

* 其他值将被忽略。

* 如果loInclusive为true，lo将会被包含在范围内，否则lo是在范围外的。

* toEnd与hiInclusive与上述逻辑相似，只不过考虑的是上限。

*/

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");

} 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;

}

// internal utilities

final boolean tooLow(Object key) {

if (!fromStart) {

int c = m.compare(key, lo);

// 如果key小于lo，或等于lo（需要lo不包含在范围内）

if (c < 0 || (c == 0 && !loInclusive))

return true;

}

return false;

}

final boolean tooHigh(Object key) {

if (!toEnd) {

int c = m.compare(key, hi);

// 如果key大于hi，或等于hi（需要hi不包含在范围内）

if (c > 0 || (c == 0 && !hiInclusive))

return true;

}

return false;

}

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);

}

// 判断key是否在该视图的范围之内

final boolean inRange(Object key, boolean inclusive) {

return inclusive ? inRange(key) : inClosedRange(key);

}

/*

* 以abs开头的函数为关系操作的绝对版本。

*/

/*

* 获得最小的键值对：

* 如果fromStart为true，那么直接返回当前map实例的第一个键值对即可，

* 否则，先判断lo是否包含在范围内，

* 如果是，则获得当前map实例中大于或等于lo的最小的键值对，

* 如果不是，则获得当前map实例中大于lo的最小的键值对。

* 如果得到的结果e超过了范围的上限，那么返回null。

*/

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;

}

// 与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) {

if (tooLow(key))

return absLowest();

TreeMap.Entry<K,V> e = m.getCeilingEntry(key);

return (e == null || tooHigh(e.key)) ? null : e;

}

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;

}

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;

}

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)));

}

// 剩下的就是实现NavigableMap的方法以及一些抽象方法

// 和NavigableSubMap中的集合视图函数。

// 大部分操作都是靠当前实例map的方法和上述用于判断边界的方法提供支持

.....

}

一个局部视图最重要的是要能够判断出传入的key是否属于该视图的范围内，在上面的代码中可以发现NavigableSubMap提供了非常多的辅助函数用于判断范围，接下来我们看看NavigableSubMap的迭代器是如何实现的：

/**

* Iterators for SubMaps

*/

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;

// UNBOUNDED是一个虚拟值（一个Object对象），表示无边界。

fenceKey = fence == null ? UNBOUNDED : fence.key;

}

// 只要next不为null并且没有超过边界

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();

// modCount是一个记录操作数的计数器

// 如果与expectedModCount不一致

// 则代表当前map实例在遍历过程中已被修改过了（从其他线程）

if (m.modCount != expectedModCount)

throw new ConcurrentModificationException();

// 向后移动next指针

// successor()返回指定节点的继任者

// 它是节点e的右子树的最左节点

// 也就是比e大的最小的节点

// 如果e没有右子树，则会试图向上寻找

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()返回指定节点的前任

// 它与successor()逻辑相反。

next = predecessor(e);

lastReturned = e;

return e;

}

final void removeAscending() {

if (lastReturned == null)

throw new IllegalStateException();

if (m.modCount != expectedModCount)

throw new ConcurrentModificationException();

// 被删除的节点被它的继任者取代

// 执行完删除后，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();

}

到目前为止，我们已经针对集合视图讨论了许多，想必大家也能够理解集合视图的概念了，由于SortedMap与NavigableMap的缘故，TreeMap中的集合视图是非常多的，包括各种局部视图和不同排序的视图，有兴趣的读者可以自己去看看源码，后面的内容不会再对集合视图进行过多的解释了。

相关推荐