一.TreeMap介绍

TreeMap 简介

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。
TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。
TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap 实现了Cloneable接口，意味着它能被克隆。
TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

TreeMap的构造函数

  1. // 默认构造函数。使用该构造函数，TreeMap中的元素按照自然排序进行排列。
  2. TreeMap()
  4. // 创建的TreeMap包含Map
  5. TreeMap(Map<? extends K, ? extends V> copyFrom)
  7. // 指定Tree的比较器
  8. TreeMap(Comparator<? super K> comparator)
  10. // 创建的TreeSet包含copyFrom
  11. TreeMap(SortedMap<K, ? extends V> copyFrom)

TreeMap的API

  1. Entry<K, V>                ceilingEntry(K key)
  2. K                          ceilingKey(K key)
  3. void                       clear()
  4. Object                     clone()
  5. Comparator<? super K>      comparator()
  6. boolean                    containsKey(Object key)
  7. NavigableSet<K>            descendingKeySet()
  8. NavigableMap<K, V>         descendingMap()
  9. Set<Entry<K, V>>           entrySet()
  10. Entry<K, V>                firstEntry()
  11. K                          firstKey()
  12. Entry<K, V>                floorEntry(K key)
  13. K                          floorKey(K key)
  14. V                          get(Object key)
  15. NavigableMap<K, V>         headMap(K to, boolean inclusive)
  16. SortedMap<K, V>            headMap(K toExclusive)
  17. Entry<K, V>                higherEntry(K key)
  18. K                          higherKey(K key)
  19. boolean                    isEmpty()
  20. Set<K>                     keySet()
  21. Entry<K, V>                lastEntry()
  22. K                          lastKey()
  23. Entry<K, V>                lowerEntry(K key)
  24. K                          lowerKey(K key)
  25. NavigableSet<K>            navigableKeySet()
  26. Entry<K, V>                pollFirstEntry()
  27. Entry<K, V>                pollLastEntry()
  28. V                          put(K key, V value)
  29. V                          remove(Object key)
  30. int                        size()
  31. SortedMap<K, V>            subMap(K fromInclusive, K toExclusive)
  32. NavigableMap<K, V>         subMap(K from, boolean fromInclusive, K to, boolean toInclusive)
  33. NavigableMap<K, V>         tailMap(K from, boolean inclusive)
  34. SortedMap<K, V>            tailMap(K fromInclusive)

二.TreeMap数据结构

TreeMap的继承关系

  1. java.lang.Object
  2.    ↳     java.util.AbstractMap<K, V>
  3.          ↳     java.util.TreeMap<K, V>
  5. public class TreeMap<K,V>
  6.     extends AbstractMap<K,V>
  7.     implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}

TreeMap与Map关系如下图：

TreeMap详细介绍和使用示例 - 图1

从图中可以看出：
(01) TreeMap实现继承于AbstractMap，并且实现了NavigableMap接口。
(02) TreeMap的本质是R-B Tree(红黑树)，它包含几个重要的成员变量： root, size, comparator。
　　root 是红黑数的根节点。它是Entry类型，Entry是红黑数的节点，它包含了红黑数的6个基本组成成分：key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序，Entry节点包含的内容为value。
　　红黑数排序时，根据Entry中的key进行排序；Entry中的key比较大小是根据比较器comparator来进行判断的。
　　size是红黑数中节点的个数。

关于红黑数的具体算法，请参考”红黑树(一) 原理和算法详细介绍“。

四.TreeMap遍历方式

4.1 遍历TreeMap的键值对

第一步：根据entrySet()获取TreeMap的“键值对”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。

  1. // 假设map是TreeMap对象
  2. // map中的key是String类型，value是Integer类型
  3. Integer integ = null;
  4. Iterator iter = map.entrySet().iterator();
  5. while(iter.hasNext()) {
  6.     Map.Entry entry = (Map.Entry)iter.next();
  7.     // 获取key
  8.     key = (String)entry.getKey();
  9.         // 获取value
  10.     integ = (Integer)entry.getValue();
  11. }

4.2 遍历TreeMap的键

第一步：根据keySet()获取TreeMap的“键”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。

  1. // 假设map是TreeMap对象
  2. // map中的key是String类型，value是Integer类型
  3. String key = null;
  4. Integer integ = null;
  5. Iterator iter = map.keySet().iterator();
  6. while (iter.hasNext()) {
  7.         // 获取key
  8.     key = (String)iter.next();
  9.         // 根据key，获取value
  10.     integ = (Integer)map.get(key);
  11. }

4.3 遍历TreeMap的值

第一步：根据value()获取TreeMap的“值”的集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。

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

TreeMap遍历测试程序如下：

  1. import java.util.Map;
  2. import java.util.Random;
  3. import java.util.Iterator;
  4. import java.util.TreeMap;
  5. import java.util.HashSet;
  6. import java.util.Map.Entry;
  7. import java.util.Collection;
  9. /*
  10.  * @desc 遍历TreeMap的测试程序。
  11.  *   (01) 通过entrySet()去遍历key、value，参考实现函数：
  12.  *        iteratorTreeMapByEntryset()
  13.  *   (02) 通过keySet()去遍历key、value，参考实现函数：
  14.  *        iteratorTreeMapByKeyset()
  15.  *   (03) 通过values()去遍历value，参考实现函数：
  16.  *        iteratorTreeMapJustValues()
  17.  *
  18.  * @author skywang
  19.  */
  20. public class TreeMapIteratorTest {
  22.     public static void main(String[] args) {
  23.         int val = 0;
  24.         String key = null;
  25.         Integer value = null;
  26.         Random r = new Random();
  27.         TreeMap map = new TreeMap();
  29.         for (int i=0; i<12; i++) {
  30.             // 随机获取一个[0,100)之间的数字
  31.             val = r.nextInt(100);
  33.             key = String.valueOf(val);
  34.             value = r.nextInt(5);
  35.             // 添加到TreeMap中
  36.             map.put(key, value);
  37.             System.out.println(" key:"+key+" value:"+value);
  38.         }
  39.         // 通过entrySet()遍历TreeMap的key-value
  40.         iteratorTreeMapByEntryset(map) ;
  42.         // 通过keySet()遍历TreeMap的key-value
  43.         iteratorTreeMapByKeyset(map) ;
  45.         // 单单遍历TreeMap的value
  46.         iteratorTreeMapJustValues(map);        
  47.     }
  49.     /*
  50.      * 通过entry set遍历TreeMap
  51.      * 效率高!
  52.      */
  53.     private static void iteratorTreeMapByEntryset(TreeMap map) {
  54.         if (map == null)
  55.             return ;
  57.         System.out.println("\niterator TreeMap By entryset");
  58.         String key = null;
  59.         Integer integ = null;
  60.         Iterator iter = map.entrySet().iterator();
  61.         while(iter.hasNext()) {
  62.             Map.Entry entry = (Map.Entry)iter.next();
  64.             key = (String)entry.getKey();
  65.             integ = (Integer)entry.getValue();
  66.             System.out.println(key+" -- "+integ.intValue());
  67.         }
  68.     }
  70.     /*
  71.      * 通过keyset来遍历TreeMap
  72.      * 效率低!
  73.      */
  74.     private static void iteratorTreeMapByKeyset(TreeMap map) {
  75.         if (map == null)
  76.             return ;
  78.         System.out.println("\niterator TreeMap By keyset");
  79.         String key = null;
  80.         Integer integ = null;
  81.         Iterator iter = map.keySet().iterator();
  82.         while (iter.hasNext()) {
  83.             key = (String)iter.next();
  84.             integ = (Integer)map.get(key);
  85.             System.out.println(key+" -- "+integ.intValue());
  86.         }
  87.     }
  90.     /*
  91.      * 遍历TreeMap的values
  92.      */
  93.     private static void iteratorTreeMapJustValues(TreeMap map) {
  94.         if (map == null)
  95.             return ;
  97.         Collection c = map.values();
  98.         Iterator iter= c.iterator();
  99.         while (iter.hasNext()) {
  100.             System.out.println(iter.next());
  101.        }
  102.     }
  103. }

五.TreeMap示例

下面通过实例来学习如何使用TreeMap

  1. import java.util.*;
  3. /**
  4.  * @desc TreeMap测试程序 
  5.  *
  6.  * @author skywang
  7.  */
  8. public class TreeMapTest  {
  10.     public static void main(String[] args) {
  11.         // 测试常用的API
  12.         testTreeMapOridinaryAPIs();
  14.         // 测试TreeMap的导航函数
  15.         //testNavigableMapAPIs();
  17.         // 测试TreeMap的子Map函数
  18.         //testSubMapAPIs();
  19.     }
  21.     /**
  22.      * 测试常用的API
  23.      */
  24.     private static void testTreeMapOridinaryAPIs() {
  25.         // 初始化随机种子
  26.         Random r = new Random();
  27.         // 新建TreeMap
  28.         TreeMap tmap = new TreeMap();
  29.         // 添加操作
  30.         tmap.put("one", r.nextInt(10));
  31.         tmap.put("two", r.nextInt(10));
  32.         tmap.put("three", r.nextInt(10));
  34.         System.out.printf("\n ---- testTreeMapOridinaryAPIs ----\n");
  35.         // 打印出TreeMap
  36.         System.out.printf("%s\n",tmap );
  38.         // 通过Iterator遍历key-value
  39.         Iterator iter = tmap.entrySet().iterator();
  40.         while(iter.hasNext()) {
  41.             Map.Entry entry = (Map.Entry)iter.next();
  42.             System.out.printf("next : %s - %s\n", entry.getKey(), entry.getValue());
  43.         }
  45.         // TreeMap的键值对个数        
  46.         System.out.printf("size: %s\n", tmap.size());
  48.         // containsKey(Object key) :是否包含键key
  49.         System.out.printf("contains key two : %s\n",tmap.containsKey("two"));
  50.         System.out.printf("contains key five : %s\n",tmap.containsKey("five"));
  52.         // containsValue(Object value) :是否包含值value
  53.         System.out.printf("contains value 0 : %s\n",tmap.containsValue(new Integer(0)));
  55.         // remove(Object key) ： 删除键key对应的键值对
  56.         tmap.remove("three");
  58.         System.out.printf("tmap:%s\n",tmap );
  60.         // clear() ： 清空TreeMap
  61.         tmap.clear();
  63.         // isEmpty() : TreeMap是否为空
  64.         System.out.printf("%s\n", (tmap.isEmpty()?"tmap is empty":"tmap is not empty") );
  65.     }
  68.     /**
  69.      * 测试TreeMap的子Map函数
  70.      */
  71.     public static void testSubMapAPIs() {
  72.         // 新建TreeMap
  73.         TreeMap tmap = new TreeMap();
  74.         // 添加“键值对”
  75.         tmap.put("a", 101);
  76.         tmap.put("b", 102);
  77.         tmap.put("c", 103);
  78.         tmap.put("d", 104);
  79.         tmap.put("e", 105);
  81.         System.out.printf("\n ---- testSubMapAPIs ----\n");
  82.         // 打印出TreeMap
  83.         System.out.printf("tmap:\n\t%s\n", tmap);
  85.         // 测试 headMap(K toKey)
  86.         System.out.printf("tmap.headMap(\"c\"):\n\t%s\n", tmap.headMap("c"));
  87.         // 测试 headMap(K toKey, boolean inclusive) 
  88.         System.out.printf("tmap.headMap(\"c\", true):\n\t%s\n", tmap.headMap("c", true));
  89.         System.out.printf("tmap.headMap(\"c\", false):\n\t%s\n", tmap.headMap("c", false));
  91.         // 测试 tailMap(K fromKey)
  92.         System.out.printf("tmap.tailMap(\"c\"):\n\t%s\n", tmap.tailMap("c"));
  93.         // 测试 tailMap(K fromKey, boolean inclusive)
  94.         System.out.printf("tmap.tailMap(\"c\", true):\n\t%s\n", tmap.tailMap("c", true));
  95.         System.out.printf("tmap.tailMap(\"c\", false):\n\t%s\n", tmap.tailMap("c", false));
  97.         // 测试 subMap(K fromKey, K toKey)
  98.         System.out.printf("tmap.subMap(\"a\", \"c\"):\n\t%s\n", tmap.subMap("a", "c"));
  99.         // 测试 
  100.         System.out.printf("tmap.subMap(\"a\", true, \"c\", true):\n\t%s\n", 
  101.                 tmap.subMap("a", true, "c", true));
  102.         System.out.printf("tmap.subMap(\"a\", true, \"c\", false):\n\t%s\n", 
  103.                 tmap.subMap("a", true, "c", false));
  104.         System.out.printf("tmap.subMap(\"a\", false, \"c\", true):\n\t%s\n", 
  105.                 tmap.subMap("a", false, "c", true));
  106.         System.out.printf("tmap.subMap(\"a\", false, \"c\", false):\n\t%s\n", 
  107.                 tmap.subMap("a", false, "c", false));
  109.         // 测试 navigableKeySet()
  110.         System.out.printf("tmap.navigableKeySet():\n\t%s\n", tmap.navigableKeySet());
  111.         // 测试 descendingKeySet()
  112.         System.out.printf("tmap.descendingKeySet():\n\t%s\n", tmap.descendingKeySet());
  113.     }
  115.     /**
  116.      * 测试TreeMap的导航函数
  117.      */
  118.     public static void testNavigableMapAPIs() {
  119.         // 新建TreeMap
  120.         NavigableMap nav = new TreeMap();
  121.         // 添加“键值对”
  122.         nav.put("aaa", 111);
  123.         nav.put("bbb", 222);
  124.         nav.put("eee", 333);
  125.         nav.put("ccc", 555);
  126.         nav.put("ddd", 444);
  128.         System.out.printf("\n ---- testNavigableMapAPIs ----\n");
  129.         // 打印出TreeMap
  130.         System.out.printf("Whole list:%s%n", nav);
  132.         // 获取第一个key、第一个Entry
  133.         System.out.printf("First key: %s\tFirst entry: %s%n",nav.firstKey(), nav.firstEntry());
  135.         // 获取最后一个key、最后一个Entry
  136.         System.out.printf("Last key: %s\tLast entry: %s%n",nav.lastKey(), nav.lastEntry());
  138.         // 获取“小于/等于bbb”的最大键值对
  139.         System.out.printf("Key floor before bbb: %s%n",nav.floorKey("bbb"));
  141.         // 获取“小于bbb”的最大键值对
  142.         System.out.printf("Key lower before bbb: %s%n", nav.lowerKey("bbb"));
  144.         // 获取“大于/等于bbb”的最小键值对
  145.         System.out.printf("Key ceiling after ccc: %s%n",nav.ceilingKey("ccc"));
  147.         // 获取“大于bbb”的最小键值对
  148.         System.out.printf("Key higher after ccc: %s%n\n",nav.higherKey("ccc"));
  149.     }
  151. }

运行结果：

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