Map大家族的那点事儿(3) :TreeMap - JAVA - 编程开发
设为首页 加入收藏

TOP

Map大家族的那点事儿(3) :TreeMap(一)
2018-09-05 11:46:47 】 浏览:26
Tags:Map 大家族 那点 事儿 TreeMap

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相等,并且fromInclusi
编程开发网
首页 上一页 1 2 3 4 5 下一页 尾页 1/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇没有了 下一篇按钮条件逻辑配置化的可选技术方案

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目