Map大家族的那点事儿(3) :TreeMap

java admin 13800 2 评论

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

然后是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的抽象类:

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中的集合视图是非常多的,包括各种局部视图和不同排序的视图,有兴趣的读者可以自己去看看源码,后面的内容不会再对集合视图进行过多的解释了。

转载请注明: 飞嗨_分享互联网 » Map大家族的那点事儿(3) :TreeMap

赞 (0) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(2)个小伙伴在吐槽
  1. 3543534
    游客2018-09-10 14:16 (14天前) 回复
  2. 54645654
    游客2018-09-10 14:16 (14天前) 回复

高效,专业,符合SEO

联系我们