Java集合系列（8）--TreeMap

前面，通过学习HashMap和HashTable后，我们对Map的学习已经有个简单了了解，接下来，我们来学习Treemap。和之前一样，我们先对TreeMap有个系统的认识，接着学习它的源码，最后再通过代码示例掌握它的使用方法。

一、TreeMap基本概述

TreeMap是一个有序的Key-Value集合，底层是通过红黑树实现的；
TreeMap继承于AbstractMap，所以也是一个键值对方式的Map；
TreeMap实现了NavigableMap接口，意味着它支持一系列的导航方法，比如返回有序的key集合；
TreeMap实现了Cloneable接口，意味着它能被克隆；
TreeMap实现了java.io.Serializable接口，意味着它支持序列化。
由以上得到：
TreeMap是基于红黑树实现的，根据具体使用的构造方法，该映射根据其键值的自然顺序进行排序的，或者根据创建映射时提供的Comparator进行排序。
TreeMap是非同步的，它的Iterator方法的迭代器是Fail-Fast机制的。并且它的containKey、get、put和remove的时间复杂度是log（n）（效率高，是一个非常重要的性质）。

面试易考点：

关注点	结论
结合底层实现的数据结构	红黑树
集合中元素是否允许为空	key、value值都不允许为空
是否允许数据重复	key值不允许重复，value值允许重复
是否有序	有序
是否线程安全	非线程安全（是非同步）

二、TreeMap的数据结构

1>理解部分概念
TreeMap是通过红黑树实现的，TreeMap存储的是Key-Value键值对，TreeMap的排序是基于对键Key的排序；
TreeMap提供了操作Key、Key-Value、Value等方法，同时提供了对TreeMap整棵树进行操作的方法。
红黑树简要补充：
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
红黑树基本构造如下：

2>TreeMap的构造函数
1、默认构造函数，使用java的默认的比较器比较Key的大小，从而对TreeMap进行排序

public TreeMap() {
    comparator = null;
}

2、带比较器的构造函数

public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}

3、带Map的构造函数，Map会成为TreeMap的子集

public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

上面代码中会调用putAll(),将m中的所有元素添加到TreeMap中，putAll（）源码如下：

public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

从中，我们可以得到putAll（）就是将m中的key-value逐个的添加到TreeMap中。
4、带sortedMap的构造函数，SortedMap会成为TreeMap的子集

public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

该构造函数不同于上面的构造函数，在上一个构造函数中传入的参数是Map，Map不是有序的，所以要逐个的添加key，value值。而该构造函数的参数是SortMap,是一个有序的Map，我们通过buildFromSorted（）来创建对应的Map。buildFromSorted（）代码如下：

// 根据已经一个排好序的map创建一个TreeMap
// 将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根节点。
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
                         Iterator it,
                         java.io.ObjectInputStream str,
                         V defaultVal)
        throws  java.io.IOException, ClassNotFoundException {

if (hi < lo) return null;


// 获取中间元素
int mid = (lo + hi) / 2;

        Entry<K,V> left  = null;
// 若lo小于mid，则递归调用获取(middel的)左孩子。
if (lo < mid)
            left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                   it, str, defaultVal);

// 获取middle节点对应的key和value
        K key;
        V value;
if (it != null) {
if (defaultVal==null) {
                Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
                key = entry.getKey();
value = entry.getValue();
            } else {
                key = (K)it.next();
value = defaultVal;
            }
        } else { // use stream
            key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
        }

// 创建middle节点
        Entry<K,V> middle =  new Entry<K,V>(key, value, null);

// 若当前节点的深度=红色节点的深度，则将节点着色为红色。
if (level == redLevel)
            middle.color = RED;

// 设置middle为left的父亲，left为middle的左孩子
if (left != null) {
            middle.left = left;
            left.parent = middle;
        }

if (mid < hi) {
// 递归调用获取(middel的)右孩子。
            Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
                           it, str, defaultVal);
// 设置middle为left的父亲，left为middle的左孩子
            middle.right = right;
            right.parent = middle;
        }

return middle;
    }

重要理解以下几点：
a、buildFromSorted（）是通过递归将SortedMap中的元素逐个关联；
b、buildFromSorted（）返回middle节点（中间节点）作为root；
c、buildFromSorted添加到红黑树中时，只是将level==redLevel的节点设为红色。第level级节点，实际上是buildFromSorted转换成红黑树的最底端的节点；只将红黑树最底端的阶段着色为红色，其余为黑色。

三、TreeMap遍历方式

1、遍历TreeMap的键值对
一是根据entrySet（）获取TreeMap的键值对的Set的集合；
二是通过Iterator迭代器遍历第一步得到的集合。

// 假设map是TreeMap对象
// map中的key是String类型，value是Integer类型
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
// 获取key
    key = (String)entry.getKey();
// 获取value
    integ = (Integer)entry.getValue();
}

2、遍历TreeMap的键
一是根据keySet（）获取TreeMap的键的Set集合；
二是通过Iterator迭代器遍历第一步得到的集合。

// 假设map是TreeMap对象
// map中的key是String类型，value是Integer类型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
// 获取key
    key = (String)iter.next();
// 根据key，获取value
    integ = (Integer)map.get(key);
}

3、遍历TreeMap的值
一是根据value（）获取TreeMap的值的集合；
二是通过Iterator迭代器遍历第一步得到的集合

// 假设map是TreeMap对象
// map中的key是String类型，value是Integer类型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

四、TreeMap代码示例

package Test;

import java.util.*;

/**
 * Created by LKL on 2017/2/18.
 * TreeMap测试程序
 */
public class TestTreeMap {

        public static void main(String[] args) {
            // 测试常用的API
            testTreeMapOridinaryAPIs();

            // 测试TreeMap的导航函数
            //testNavigableMapAPIs();

            // 测试TreeMap的子Map函数
            //testSubMapAPIs();
        }

/**
 * 测试常用的API
 */
        private static void testTreeMapOridinaryAPIs() {
            // 初始化随机种子
            Random r = new Random();
            // 新建TreeMap
            TreeMap tmap = new TreeMap();
            // 添加操作
            tmap.put("one", r.nextInt(10));
            tmap.put("two", r.nextInt(10));
            tmap.put("three", r.nextInt(10));

            System.out.printf("\n ---- testTreeMapOridinaryAPIs ----\n");
            // 打印出TreeMap
            System.out.printf("%s\n",tmap );

            // 通过Iterator遍历key-value
            Iterator iter = tmap.entrySet().iterator();
            while(iter.hasNext()) {
                Map.Entry entry = (Map.Entry)iter.next();
                System.out.printf("next : %s - %s\n", entry.getKey(), entry.getValue());
            }

            // TreeMap的键值对个数
            System.out.printf("size: %s\n", tmap.size());

            // containsKey(Object key) :是否包含键key
            System.out.printf("contains key two : %s\n",tmap.containsKey("two"));
            System.out.printf("contains key five : %s\n",tmap.containsKey("five"));

            // containsValue(Object value) :是否包含值value
            System.out.printf("contains value 0 : %s\n",tmap.containsValue(new Integer(0)));

            // remove(Object key) ： 删除键key对应的键值对
            tmap.remove("three");

            System.out.printf("tmap:%s\n",tmap );

            // clear() ： 清空TreeMap
            tmap.clear();

            // isEmpty() : TreeMap是否为空
            System.out.printf("%s\n", (tmap.isEmpty()?"tmap is empty":"tmap is not empty") );
        }


/**
 * 测试TreeMap的子Map函数
 */
        public static void testSubMapAPIs() {
            // 新建TreeMap
            TreeMap tmap = new TreeMap();
            // 添加“键值对”
            tmap.put("a", 101);
            tmap.put("b", 102);
            tmap.put("c", 103);
            tmap.put("d", 104);
            tmap.put("e", 105);

            System.out.printf("\n ---- testSubMapAPIs ----\n");
            // 打印出TreeMap
            System.out.printf("tmap:\n\t%s\n", tmap);

            // 测试 headMap(K toKey)
            System.out.printf("tmap.headMap(\"c\"):\n\t%s\n", tmap.headMap("c"));
            // 测试 headMap(K toKey, boolean inclusive)
            System.out.printf("tmap.headMap(\"c\", true):\n\t%s\n", tmap.headMap("c", true));
            System.out.printf("tmap.headMap(\"c\", false):\n\t%s\n", tmap.headMap("c", false));

            // 测试 tailMap(K fromKey)
            System.out.printf("tmap.tailMap(\"c\"):\n\t%s\n", tmap.tailMap("c"));
            // 测试 tailMap(K fromKey, boolean inclusive)
            System.out.printf("tmap.tailMap(\"c\", true):\n\t%s\n", tmap.tailMap("c", true));
            System.out.printf("tmap.tailMap(\"c\", false):\n\t%s\n", tmap.tailMap("c", false));

            // 测试 subMap(K fromKey, K toKey)
            System.out.printf("tmap.subMap(\"a\", \"c\"):\n\t%s\n", tmap.subMap("a", "c"));
            // 测试
            System.out.printf("tmap.subMap(\"a\", true, \"c\", true):\n\t%s\n",
                    tmap.subMap("a", true, "c", true));
            System.out.printf("tmap.subMap(\"a\", true, \"c\", false):\n\t%s\n",
                    tmap.subMap("a", true, "c", false));
            System.out.printf("tmap.subMap(\"a\", false, \"c\", true):\n\t%s\n",
                    tmap.subMap("a", false, "c", true));
            System.out.printf("tmap.subMap(\"a\", false, \"c\", false):\n\t%s\n",
                    tmap.subMap("a", false, "c", false));

            // 测试 navigableKeySet()
            System.out.printf("tmap.navigableKeySet():\n\t%s\n", tmap.navigableKeySet());
            // 测试 descendingKeySet()
            System.out.printf("tmap.descendingKeySet():\n\t%s\n", tmap.descendingKeySet());
        }

/**
 * 测试TreeMap的导航函数
 */
        public static void testNavigableMapAPIs() {
            // 新建TreeMap
            NavigableMap nav = new TreeMap();
            // 添加“键值对”
            nav.put("aaa", 111);
            nav.put("bbb", 222);
            nav.put("eee", 333);
            nav.put("ccc", 555);
            nav.put("ddd", 444);

            System.out.printf("\n ---- testNavigableMapAPIs ----\n");
            // 打印出TreeMap
            System.out.printf("Whole list:%s%n", nav);

            // 获取第一个key、第一个Entry
            System.out.printf("First key: %s\tFirst entry: %s%n",nav.firstKey(), nav.firstEntry());

            // 获取最后一个key、最后一个Entry
            System.out.printf("Last key: %s\tLast entry: %s%n",nav.lastKey(), nav.lastEntry());

            // 获取“小于/等于bbb”的最大键值对
            System.out.printf("Key floor before bbb: %s%n",nav.floorKey("bbb"));

            // 获取“小于bbb”的最大键值对
            System.out.printf("Key lower before bbb: %s%n", nav.lowerKey("bbb"));

            // 获取“大于/等于bbb”的最小键值对
            System.out.printf("Key ceiling after ccc: %s%n",nav.ceilingKey("ccc"));

            // 获取“大于bbb”的最小键值对
            System.out.printf("Key higher after ccc: %s%n\n",nav.higherKey("ccc"));
        }

}

运行结果如下：

 ---- testTreeMapOridinaryAPIs ----
{one=5, three=8, two=1}
next : one - 5
next : three - 8
next : two - 1
size: 3
contains key two : true
contains key five : false
contains value 0 : false
tmap:{one=5, two=1}
tmap is empty

文章只是作为自己的学习笔记，借鉴了网上的许多案例，如果觉得阔以的话，希望多交流，在此
谢过…