前面讨论完了HashMap和HashTable的源码，这一节我们来讨论一下TreeMap。先从整体上把握TreeMap，然后分析其源码，深入剖析TreeMap的实现。

1. TreeMap简介

TreeMap是一个有序的key-value集合，它内部是通过红-黑树实现的，如果对红-黑树不太了解，请先参考下这篇博文：红-黑树。下面我们先来看看TreeMap的继承关系：

 
    [java] 
    view plain
    copy

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

从继承关系可以看出，TreeMap继承与AbstractMap，实现了NavigableMap接口，意味着它支持一系列的导航方法，比如返回有序的key集合。它还实现了Cloneable接口，意味着它能被克隆。另外也实现了Serializable接口，表示它支持序列化。

TreeMap是基于红-黑树实现的，该映射根据其key的自然顺序进行排序，或者根据用户创建映射时提供的Comarator进行排序，另外，TreeMap是非同步的。

我们先总览一下TreeMap都有哪些API：

 
    [java] 
    view plain
    copy

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

从这些API中可以看出，总共可分为这几大类：跟Entry相关的，跟key相关的以及跟Map相关的，另外还有keySet和entrySet等方法，下文详细讨论这些API。

2. TreeMap的源码分析（基于JDK1.7)

2.1 存储结构

由于TreeMap是基于红黑树实现的，所以其内部维护了一个红-黑树的数据结构，每个key-value对也存储在一个Entry里，只不过这个Entry和前面HashMap或者HashTable中的Entry不同，TreeMap的Entry其实是红-黑树的一个节点。我们来看一下TreeMap中的Entry定义：

 
    [java] 
    view plain
    copy

private transient Entry<K,V> root = null;

然后我们看看Entry实体类的实现：

2.2 Entry实体类和相关方法

先看一下Entry实体类：

 
    [java] 
    view plain
    copy

     
    
     
   
private static final boolean RED   = false;  
private static final boolean BLACK = true;  
//就是一个红黑树的节点  
static final class Entry<K,V> implements Map.Entry<K,V> {  
    K key;  
    V value;  
    Entry<K,V> left = null; //左子节点  
    Entry<K,V> right = null; //右子节点  
    Entry<K,V> parent; //父节点  
    boolean color = BLACK; //树的颜色，默认为黑色  
  
    Entry(K key, V value, Entry<K,V> parent) { //构造方法  
        this.key = key;  
        this.value = value;  
        this.parent = parent;  
    }  
  
    public K getKey() { //获得key  
        return key;  
    }  
  
    public V getValue() { //获得value  
        return value;  
    }  
  
    public V setValue(V value) { //设置value  
        V oldValue = this.value;  
        this.value = value;  
        return oldValue;  
    }  
  
    public boolean equals(Object o) { //key和value均相等才返回true  
        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() { //计算hashCode  
        int keyHash = (key==null ? 0 : key.hashCode());  
        int valueHash = (value==null ? 0 : value.hashCode());  
        return keyHash ^ valueHash;  
    }  
  
    public String toString() { //重写toString方法  
        return key + "=" + value;  
    }  
}  

从Entry实体类中可以看出，TreeMap中的Entry就是一个红黑树的节点。跟这个Entry相关的方法都有 firstEntry()、lastEntry()、lowerEntry()、higherEntry()、floorEntry()、ceilingEntry()。它们的原理都是类似的，我们只分析firstEntry()，其他的放到源码里分析：

 
    [java] 
    view plain
    copy

     
    
     
   
public Map.Entry<K,V> firstEntry() {  
    return exportEntry(getFirstEntry());  
}  
  
//获得TreeMap里第一个节点(即根据key排序最小的节点)，如果TreeMap为空，返回null  
final Entry<K,V> getFirstEntry() {  
    Entry<K,V> p = root;  
    if (p != null)  
        while (p.left != null)  
            p = p.left;  
    return p;  
}  

代码很简单，一直往下走，直到找到那个节点，然后返回即可。这里为什么不直接调用getFirtstEntry()，而是对外提供firstEntry()供外界调用呢？这就说到了exportEntry()方法的作用了，因为如果直接调用getFirstEntry()方法的话，返回的Entry是可以被修改的，但是经过exportEntry()方法包装过之后就不能修改了，所以这么做事防止用于修改返回的Entry。我们来看看exportEntry()方法是如何对Entry对象进行包装的：

 
    [java] 
    view plain
    copy

static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {  
    return (e == null) ? null :  
        new AbstractMap.SimpleImmutableEntry<>(e);  
}

我们可以看出，它是通过新new一个AbstractMap类中的一个静态类SimpleImmutableEntry实现的，那么SimpleImmutableEntry类中是如何实现的呢，为了方便，我们也把该类拿过来（当然也可以看这篇博文 Map架构与源码分析，里面有讲到AbstractMap抽象类的源码），下面看看这个SimpleImmutableEntry静态类是如何实现的：

 
    [java] 
    view plain
    copy

     
    
     
   
public static class SimpleImmutableEntry<K,V>  
    implements Entry<K,V>, java.io.Serializable  
{  
    private static final long serialVersionUID = 7138329143949025153L;  
  
    private final K key;  
    private final V value;  
  
    public SimpleImmutableEntry(K key, V value) { //通过key和value初始化对象  
        this.key   = key;  
        this.value = value;  
    }  
  
    public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) { //通过传进来一个Entry初始化对象  
        this.key   = entry.getKey();  
        this.value = entry.getValue();  
    }  
  
    public K getKey() {  
        return key;  
    }  
  
    public V getValue() {  
        return value;  
    }  
  
    public V setValue(V value) { //!!!关键地方在这里，不能setValue，否则会抛出UnsupportedOperationException异常  
        throw new UnsupportedOperationException();  
    }  
  
    public boolean equals(Object o) {  
        if (!(o instanceof Map.Entry))  
            return false;  
        Map.Entry e = (Map.Entry)o;  
        return eq(key, e.getKey()) && eq(value, e.getValue());  
    }  
  
    public int hashCode() {  
        return (key   == null ? 0 :   key.hashCode()) ^  
               (value == null ? 0 : value.hashCode());  
    }  
      
    //重写了toString方法，返回key=value形式  
    public String toString() {  
        return key + "=" + value;  
    }  
}  

从上面代码中可以看出，被这个类包装过的Entry是不允许被修改内容的，这也就是为什么TreeMap类不直接把getFirstEntry()方法暴露出去，而是提供了firstEntry()供外界调用的原因。关于Entry的其他类似的方法我就不一一赘述了，我放到源代码里分析，都不难理解。如下：

 
    [java] 
    view plain
    copy

     
    
     
   
/*********************** 与Entry相关的方法 ******************************/      
  
 //获取TreeMap中键为key对应的节点  
 final Entry<K,V> getEntry(Object key) {  
    // 若比较器不为null，则通过getEntryUsingComparator来获得  
    if (comparator != null)  
        return getEntryUsingComparator(key);  
    if (key == null)  
        throw new NullPointerException();  
    Comparable<? super K> k = (Comparable<? super K>) key;  
    Entry<K,V> p = root; //若没有比较器，则正常往下走  
    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对应的Entry  
final Entry<K,V> getEntryUsingComparator(Object key) {  
    K k = (K) key;  
    Comparator<? super K> cpr = comparator;  
    if (cpr != null) {  
        Entry<K,V> p = root;  
        while (p != null) {  
            int cmp = cpr.compare(k, p.key);  
            if (cmp < 0)  
                p = p.left;  
            else if (cmp > 0)  
                p = p.right;  
            else  
                return p;  
        }  
    }  
    return null;  
}  
/*--------------------------------------------------------*/  
public Map.Entry<K,V> firstEntry() {  
    return exportEntry(getFirstEntry());  
}  
//获得TreeMap里第一个节点(即根据key排序最小的节点)，如果TreeMap为空，返回null  
final Entry<K,V> getFirstEntry() {  
    Entry<K,V> p = root;  
    if (p != null)  
        while (p.left != null)  
            p = p.left;  
    return p;  
}  
/*-----------------------------------------------*/  
public Map.Entry<K,V> lastEntry() {  
    return exportEntry(getLastEntry());  
}  
//获得TreeMap里最后一个节点(根据key排序最大的节点)，如果TreeMap为空，返回null  
final Entry<K,V> getLastEntry() {  
    Entry<K,V> p = root;  
    if (p != null)  
        while (p.right != null)  
            p = p.right;  
    return p;  
}  
/*------------------------------------------------*/  
//弹出第一个节点，即删除  
public Map.Entry<K,V> pollFirstEntry() {  
    Entry<K,V> p = getFirstEntry();   
    Map.Entry<K,V> result = exportEntry(p);  
    if (p != null)  
        deleteEntry(p);  
    return result;  
}  
//弹出最后一个节点，即删除  
public Map.Entry<K,V> pollLastEntry() {  
    Entry<K,V> p = getLastEntry();  
    Map.Entry<K,V> result = exportEntry(p);  
    if (p != null)  
        deleteEntry(p);  
    return result;  
}  
/*-------------------------------------------------*/  
public Map.Entry<K,V> floorEntry(K key) {  
    return exportEntry(getFloorEntry(key));  
}  
public Map.Entry<K,V> ceilingEntry(K key) {  
    return exportEntry(getCeilingEntry(key));  
}  
  
//获取TreeMap中不小于key的最小的节点；  
//若不存在(即TreeMap中所有节点的键都比key大)，就返回null  
final Entry<K,V> getCeilingEntry(K key) {  
    Entry<K,V> p = root;  
    while (p != null) {  
        int cmp = compare(key, p.key);  
        if (cmp < 0) { //情况1. 若p.key > key  
            if (p.left != null) //若p有左子节点  
                p = p.left; //往左下走  
            else  
                return p; //否则返回p  
        } else if (cmp > 0) { //情况2：p.key < key  
            if (p.right != null) {  
                p = p.right;  
            } else {  
                // 若 p 不存在右孩子，则找出 p 的后继节点，并返回  
                // 注意：这里返回的 “p的后继节点”有2种可能性：第一，null；第二，TreeMap中大于key的最小的节点。  
                // 理解这一点的核心是，getCeilingEntry是从root开始遍历的。  
                // 若getCeilingEntry能走到这一步，那么，它之前“已经遍历过的节点的key”都 > key。  
                // 能理解上面所说的，那么就很容易明白，为什么“p的后继节点”又2种可能性了。  
                Entry<K,V> parent = p.parent;  
                Entry<K,V> ch = p;  
                while (parent != null && ch == parent.right) {  
                    ch = parent;  
                    parent = parent.parent;  
                }  
                return parent;  
            }  
        } else //情况3：p.key = key  
            return p;  
    }  
    return null;  
}  
// 获取TreeMap中不大于key的最大的节点；  
// 若不存在(即TreeMap中所有节点的键都比key小)，就返回null  
// getFloorEntry的原理和getCeilingEntry类似，这里不再多说。  
final Entry<K,V> getFloorEntry(K key) {  
    Entry<K,V> p = root;  
    while (p != null) {  
        int cmp = compare(key, p.key);  
        if (cmp > 0) {  
            if (p.right != null)  
                p = p.right;  
            else  
                return p;  
        } else if (cmp < 0) {  
            if (p.left != null) {  
                p = p.left;  
            } else {  
                Entry<K,V> parent = p.parent;  
                Entry<K,V> ch = p;  
                while (parent != null && ch == parent.left) {  
                    ch = parent;  
                    parent = parent.parent;  
                }  
                return parent;  
            }  
        } else  
            return p;  
  
    }  
    return null;  
}  
/*--------------------------------------------------*/  
public Map.Entry<K,V> lowerEntry(K key) {  
    return exportEntry(getLowerEntry(key));  
}  
public Map.Entry<K,V> higherEntry(K key) {  
    return exportEntry(getHigherEntry(key));  
}   
  
// 获取TreeMap中大于key的最小的节点。  
// 若不存在，就返回null。  
// 请参照getCeilingEntry来对getHigherEntry进行理解。  
final Entry<K,V> getLowerEntry(K key) {  
    Entry<K,V> p = root;  
    while (p != null) {  
        int cmp = compare(key, p.key);  
        if (cmp > 0) {  
            if (p.right != null)  
                p = p.right;  
            else  
                return p;  
        } else {  
            if (p.left != null) {  
                p = p.left;  
            } else {  
                Entry<K,V> parent = p.parent;  
                Entry<K,V> ch = p;  
                while (parent != null && ch == parent.left) {  
                    ch = parent;  
                    parent = parent.parent;  
                }  
                return parent;  
            }  
        }  
    }  
    return null;  
}  
// 获取TreeMap中小于key的最大的节点。  
// 若不存在，就返回null。  
// 请参照getCeilingEntry来对getLowerEntry进行理解。  
final Entry<K,V> getHigherEntry(K key) {  
    Entry<K,V> p = root;  
    while (p != null) {  
        int cmp = compare(key, p.key);  
        if (cmp < 0) {  
            if (p.left != null)  
                p = p.left;  
            else  
                return p;  
        } else {  
            if (p.right != null) {  
                p = p.right;  
            } else {  
                Entry<K,V> parent = p.parent;  
                Entry<K,V> ch = p;  
                while (parent != null && ch == parent.right) {  
                    ch = parent;  
                    parent = parent.parent;  
                }  
                return parent;  
            }  
        }  
    }  
    return null;  
}  
/*---------------------------------------------------*/  

2.3 成员属性的构造方法

分析完了Entry实体相关的源码后，我们来看看TreeMap里的成员属性。

 
    [java] 
    view plain
    copy

     
    
     
   
/********************* 成员属性 ****************************/  
private final Comparator<? super K> comparator; //比较器  
private transient Entry<K,V> root = null; //实体对象  
private transient int size = 0; //红黑树节点个数，即Entry数  
private transient int modCount = 0; //修改次数  
  
/*********************** 构造方法 **************************/  
public TreeMap() {  //默认构造方法  
    comparator = null;  
}  
public TreeMap(Comparator<? super K> comparator) { //带比较器的构造方法  
    this.comparator = comparator;  
}  
public TreeMap(Map<? extends K, ? extends V> m) { //带Map的构造方法，Map会为TreeMap的子类  
    comparator = null;  
    putAll(m);  
}  
////带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) {  
    }  
}  

我们可以看出，TreeMap有四个构造函数，这里分析一下第三个构造函数，内部调用了putAll方法，我们看一下putAll方法：

 
    [java] 
    view plain
    copy

     
    
     
   
public void putAll(Map<? extends K, ? extends V> map) {  
    int mapSize = map.size();//获取map的大小  
    //如果TreeMap大小是0，且map的大小不为0，且map是已排序的key-value对，才执行下面的程序  
    if (size==0 && mapSize!=0 && map instanceof SortedMap) {  
        Comparator c = ((SortedMap)map).comparator();  
        if (c == comparator || (c != null && c.equals(comparator))) {  
            ++modCount;  
            try {  
                buildFromSorted(mapSize, map.entrySet().iterator(),  
                                null, null);  
            } catch (java.io.IOException cannotHappen) {  
            } catch (ClassNotFoundException cannotHappen) {  
            }  
            return;  
        }  
    }  
    //否则调用AbstractMap中的putAll()  
    //AbstractMap中的putAll()又会调用TreeMap的put()方法  
    super.putAll(map);  
}  

在putAll方法内部，会先进行判断，如果TreeMap是空的，且传进来的map符合条件，则执行if内的语句，然后调用buildFromSorted方法（后面放到源码中分析）来put进去，否则调用父类的putAll方法，父类的putAll方法则直接调用TreeMap的put方法。

由于TreeMap的源码比较多，这里先写到这，后面的源码分析放到下一篇博客中写：java集合框架11——TreeMap和源码分析（二）。

如有错误之处，欢迎留言指正~

_____________________________________________________________________________________________________________________________________________________

-----乐于分享，共同进步！

-----更多文章请看：http://blog.csdn.net/eson_15

java集合框架10——TreeMap和源码分析（一）

1. TreeMap简介

2. TreeMap的源码分析（基于JDK1.7)

2.1 存储结构

2.2 Entry实体类和相关方法

2.3 成员属性的构造方法

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

java集合框架10——TreeMap和源码分析（一）

1. TreeMap简介

2. TreeMap的源码分析（基于JDK1.7)

2.1 存储结构

2.2 Entry实体类和相关方法

2.3 成员属性的构造方法

热门文章

最新文章

相关课程

相关电子书

相关实验场景