一、概述

TreeMap 简介

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

TreeMap的构造函数

// 默认构造函数。使用该构造函数，TreeMap中的元素按照自然排序进行排列。TreeMap()// 创建的TreeMap包含MapTreeMap(Map
     copyFrom)// 指定Tree的比较器TreeMap(Comparator
     comparator)// 创建的TreeSet包含copyFromTreeMap(SortedMap
    
      copyFrom)
    

TreeMap的API

Entry
    
                     ceilingEntry(K key)K                          ceilingKey(K key)void                       clear()Object                     clone()Comparator
           comparator()boolean                    containsKey(Object key)NavigableSet
     
                  descendingKeySet()NavigableMap
      
                descendingMap()Set
       
        
         >           entrySet()Entry
         
                          firstEntry()K                          firstKey()Entry
          
                           floorEntry(K key)K                          floorKey(K key)V                          get(Object key)NavigableMap
           
                     headMap(K to, boolean inclusive)SortedMap
            
                         headMap(K toExclusive)Entry
             
                              higherEntry(K key)K                          higherKey(K key)boolean                    isEmpty()Set
              
                                    keySet()Entry
               
                                lastEntry()K                          lastKey()Entry
                
                                 lowerEntry(K key)K                          lowerKey(K key)NavigableSet
                 
                              navigableKeySet()Entry
                  
                                   pollFirstEntry()Entry
                   
                                    pollLastEntry()V                          put(K key, V value)V                          remove(Object key)int                        size()SortedMap
                    
                                 subMap(K fromInclusive, K toExclusive)NavigableMap
                     
                               subMap(K from, boolean fromInclusive, K to, boolean toInclusive)NavigableMap
                      
                                tailMap(K from, boolean inclusive)SortedMap
                       
                                    tailMap(K fromInclusive)
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

二、TreeMap数据结构

TreeMap的继承关系

java.lang.Object   ↳     java.util.AbstractMap
    
              ↳     java.util.TreeMap
     
      public class TreeMap
      
           extends AbstractMap
       
            implements NavigableMap
        
         , Cloneable, java.io.Serializable {}
        
       
      
     
    

TreeMap与Map关系如下图：

从图中可以看出：

三、TreeMap遍历方式

3.1 遍历TreeMap的键值对

第一步：根据entrySet()获取TreeMap的“键值对”的Set集合。

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

3.2 遍历TreeMap的键

第一步：根据keySet()获取TreeMap的“键”的Set集合。

// 假设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.3 遍历TreeMap的值

第一步：根据value()获取TreeMap的“值”的集合。

// 假设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遍历测试程序如下：

import java.util.Map;import java.util.Random;import java.util.Iterator;import java.util.TreeMap;import java.util.HashSet;import java.util.Map.Entry;import java.util.Collection;/* * @desc 遍历TreeMap的测试程序。 *   (01) 通过entrySet()去遍历key、value，参考实现函数： *        iteratorTreeMapByEntryset() *   (02) 通过keySet()去遍历key、value，参考实现函数： *        iteratorTreeMapByKeyset() *   (03) 通过values()去遍历value，参考实现函数： *        iteratorTreeMapJustValues() * * @author skywang */public class TreeMapIteratorTest {    public static void main(String[] args) {        int val = 0;        String key = null;        Integer value = null;        Random r = new Random();        TreeMap map = new TreeMap();        for (int i=0; i<12; i++) {            // 随机获取一个[0,100)之间的数字            val = r.nextInt(100);                        key = String.valueOf(val);            value = r.nextInt(5);            // 添加到TreeMap中            map.put(key, value);            System.out.println(" key:"+key+" value:"+value);        }        // 通过entrySet()遍历TreeMap的key-value        iteratorTreeMapByEntryset(map) ;                // 通过keySet()遍历TreeMap的key-value        iteratorTreeMapByKeyset(map) ;                // 单单遍历TreeMap的value        iteratorTreeMapJustValues(map);            }        /*     * 通过entry set遍历TreeMap     * 效率高!     */    private static void iteratorTreeMapByEntryset(TreeMap map) {        if (map == null)            return ;        System.out.println("\niterator TreeMap By entryset");        String key = null;        Integer integ = null;        Iterator iter = map.entrySet().iterator();        while(iter.hasNext()) {            Map.Entry entry = (Map.Entry)iter.next();                        key = (String)entry.getKey();            integ = (Integer)entry.getValue();            System.out.println(key+" -- "+integ.intValue());        }    }    /*     * 通过keyset来遍历TreeMap     * 效率低!     */    private static void iteratorTreeMapByKeyset(TreeMap map) {        if (map == null)            return ;        System.out.println("\niterator TreeMap By keyset");        String key = null;        Integer integ = null;        Iterator iter = map.keySet().iterator();        while (iter.hasNext()) {            key = (String)iter.next();            integ = (Integer)map.get(key);            System.out.println(key+" -- "+integ.intValue());        }    }        /*     * 遍历TreeMap的values     */    private static void iteratorTreeMapJustValues(TreeMap map) {        if (map == null)            return ;                Collection c = map.values();        Iterator iter= c.iterator();        while (iter.hasNext()) {            System.out.println(iter.next());       }    }}