Map集合类——TreeMap

参考文章

http://www.importnew.com/29713.html

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

红黑树

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

任意节点最多含有两个子节点。
任意节点的左、右节点都可以看做为一棵二叉查找树。
如果任意节点的左子树不为空,那么左子树上的所有节点的值均小于它的根节点的值。
如果任意节点的右子树不为空,那么右子树上的所有节点的值均大于它的根节点的值。
任意节点的key都是不同的。
Map集合类——TreeMap
尽管二叉查找树看起来很美好,但事与愿违,二叉查找树在极端情况下会变得并不是那么有效率,假设我们有一个有序的整数序列: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
}
上一篇:java – TreeMap的lastKey查找时间


下一篇:java – 如何获取Treemap的最后n个元素