Java集合类源代码之TreeMap

• 简介
• • 二叉排序树的基本性质如下
• 源码
• • （一）treemap的存储结构
  • （二）构造方法
  • • 1、无参构造方法
    • 2、带有比较器的构造方法
    • 3、带Map的构造方法
    • 4、带有SortedMap的构造方法
  • (三) 插入删除
  • • put源码的实现：
    • deleteEntry方法的实现
• 总结

简介

TreeMap是基于红黑树实现的，这里只对红黑树做个简单的介绍，红黑树是一种特殊的二叉排序树，红黑树通过一些限制，使其不会出现二叉树排序树中极端的一边倒的情况，相对二叉排序树而言，这自然提高了查询的效率。

如果不理解红黑树的家人们 可以来看看这位大佬的博客

二叉排序树的基本性质如下

源码

（一）treemap的存储结构

TreeMap的排序是基于对key的排序实现的，它的每一个Entry代表红黑树的一个节点。

Entry的数据结构如下：

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;    
     } 
} 

（二）构造方法

TreeMap一共有4个构造方法。

1、无参构造方法

采用无参构造方法，不指定比较器，这时候，排序的实现要依赖 key.compareTo() 方法，因此key必须实现Comparable接口，并覆写其中的compareTo方法。

public TreeMap() {    
    comparator = null;    
}

2、带有比较器的构造方法

该构造方法同样不指定比较器，调用putAll方法将Map中的所有元素加入到TreeMap中

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

3、带Map的构造方法

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

该构造方法同样不指定比较器，调用putAll方法将Map中的所有元素加入到TreeMap中。

putAll的源码

// 将map中的全部节点添加到TreeMap中    
public void putAll(Map<? extends K, ? extends V> map) {    
    // 获取map的大小    
    int mapSize = map.size();    
    // 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value对”    
    if (size==0 && mapSize!=0 && map instanceof SortedMap) {    
        Comparator c = ((SortedMap)map).comparator();    
        // 如果TreeMap和map的比较器相等；    
        // 则将map的元素全部拷贝到TreeMap中，然后返回！    
        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);    
}  

显然，如果Map里的元素是排好序的，就调用buildFromSorted方法来拷贝Map中的元素，这在下一个构造方法中会重点提及，而如果Map中的元素不是排好序的，就调用AbstractMap的**putAll(map)**方法，该方法源码如下：

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

很明显它是将Map中的元素一个个put（插入）到TreeMap中的，主要因为Map中的元素是无序存放的，因此要一个个插入到红黑树中，使其有序存放，并满足红黑树的性质。

4、带有SortedMap的构造方法

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) {

        }  
}    

首先将比较器指定为m的比较器，这取决于生成m时调用构造方法是否传入了指定的构造器，而后调用buildFromSorted方法，将SortedMap中的元素插入到TreeMap中，由于SortedMap中的元素师有序的，实际上它是根据SortedMap创建的TreeMap，将SortedMap中对应的元素添加到TreeMap中。

(三) 插入删除

插入操作即对应TreeMap的put方法，put操作实际上只需按照二叉排序树的插入步骤来操作即可，插入到指定位置后，再做调整，使其保持红黑树的特性。

put源码的实现：

public V put(K key, V value) {    
    Entry<K,V> t = root;    
    // 若红黑树为空，则插入根节点    
    if (t == null) {    
    // TBD:    
    // 5045147: (coll) Adding null to an empty TreeSet should    
    // throw NullPointerException    
    //    
    // compare(key, key); // type check    
        root = new Entry<K,V>(key, value, null);    
        size = 1;    
        modCount++;    
        return null;    
    }    
    int cmp;    
    Entry<K,V> parent;    
    // split comparator and comparable paths    
    Comparator<? super K> cpr = comparator;    
    // 找出(key, value)在二叉排序树中的插入位置。    
    // 红黑树是以key来进行排序的，所以这里以key来进行查找。    
    if (cpr != null) {    
        do {    
            parent = t;    
            cmp = cpr.compare(key, t.key);    
            if (cmp < 0)    
                t = t.left;    
            else if (cmp > 0)    
                t = t.right;    
            else   
                return t.setValue(value);    
        } while (t != null);    
    }    
    else {    
        if (key == null)    
            throw new NullPointerException();    
        Comparable<? super K> k = (Comparable<? super K>) key;    
        do {    
            parent = t;    
            cmp = k.compareTo(t.key);    
            if (cmp < 0)    
                t = t.left;    
            else if (cmp > 0)    
                t = t.right;    
            else   
                return t.setValue(value);    
        } while (t != null);    
    }    
    // 为（key-value）新建节点    
    Entry<K,V> e = new Entry<K,V>(key, value, parent);    
    if (cmp < 0)    
        parent.left = e;    
    else   
        parent.right = e;    
    // 插入新的节点后，调用fixAfterInsertion调整红黑树。    
    fixAfterInsertion(e);    
    size++;    
    modCount++;    
    return null;    
}    

这里的fixAfterInsertion便是节点插入后对树进行调整的方法 也就是红黑树调整的机制

删除操作及对应TreeMap的deleteEntry方法，deleteEntry方法同样也只需按照二叉排序树的操作步骤实现即可，删除指定节点后，再对树进行调整即可。

deleteEntry方法的实现

将节点删除之后需要通过变色 + 旋转使树平衡

private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;
        // 节点p的左右节点都存在，将p节点的下一个节点s，即大于P的最小节点，即P的右子树中最左边的一个节点，将s中的值拷贝到p中，然后删除s
        //此时s最多有一个右节点
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children
 
        // replacement表示替代被删除节点的节点，p节点被删除了，只能用其子节点代替
        // 经过上面的转换，p要么没有子节点，要么只有一个子节点
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);
 
        //p有一个子节点
        if (replacement != null) {
            // 设置replacement的父节点
            replacement.parent = p.parent;
            if (p.parent == null)//父节点为空，replacement为根节点
                root = replacement;
            else if (p == p.parent.left)//p为其父节点的左节点，replacement代替p
                p.parent.left  = replacement;
            else
                //p为其父节点的右节点，replacement代替p
                p.parent.right = replacement;
 
            //将p节点的引用置空
            p.left = p.right = p.parent = null;
 
            //这种情形p节点就是黑色的，子节点即replacement必须是红色的，fixAfterDeletion实际只是将replacement涂黑
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { //无替换节点且p为根节点，直接删除
            root = null;
        } else {
            //无替换节点，即p无子节点，注意此处是先调整红黑树，再删除p节点，如果先删除再调整就找不到p节点的父节点了，无法调整
            //如果p是黑色节点需要调整红黑树，此时需要考虑p的兄弟节点以及p的位置，如果是红色节点则可以直接删除
            if (p.color == BLACK)
                fixAfterDeletion(p);
 
            //删除父节点对该节点的引用
            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

总结

本文对TreeMap的分析较前几篇文章有些浅尝辄止，TreeMap用的没有HashMap那么多