TreeMap解析-白红宇

TreeMap解析

阅读量：4217 次

发布时间：2019-05-26

本文共 4409 字，大约阅读时间需要 14 分钟。

TreeMap基于红黑树的NavigableMap实现。相对于HashMap来说，TreeMap多继承一个NavigableMap接口，因此HashMap的key是无序的，TreeMap的key是有序的，其是根据key的自然顺序或在创建时提供的Comparator来存储元素。TreeMap是非同步的，它返回的迭代器是快速失败的。

Comparable和Comparator的区别：Comparable是排序接口，如果一个类实现了Comparable接口，则意味着该类支持排序；Comparator是比较器接口，当需要控制某个类的次序，而该类本身并不支持排序，那么可以建立一个该类的比较器来进行排序；Comparable相当于内部比较器，而Comparator相当于外部比较器。

TreeMap的源码解析

TreeMap的继承关系

public class TreeMap
   
        extends AbstractMap
    
         implements NavigableMap
     
      , Cloneable, java.io.Serializable

TreeMap本质是一棵红黑树，关于红黑树的原理，参考http://www.cnblogs.com/tianex/p/5093350.html

TreeMap的构造函数

1. 默认的构造函数，使用key的自然顺序来进行排序

public TreeMap() {　　comparator = null;}

2. 使用带比较器的构造函数

public TreeMap(Comparator
    comparator) {　　this.comparator = comparator;}

3. 带有Map的构造函数，参数Map成为TreeMap的子集。Map中的key必须实现Comparable接口，插入后的顺序是按照key的自然顺序来排序的

public TreeMap(Map
    m) {　　comparator = null;　　putAll(m);}

该构造函数会调用putAll方法将参数Map中的所有元素添加到TreeMap中，putAll的源码如下：

public void putAll(Map
    map) {　　int mapSize = map.size();　　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;　　　　}　　}　　super.putAll(map);}

可知其是通过buildFromSorted实现的，其源码如下：

// 根据已经一个排好序的map创建一个TreeMap// 将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根节点private final Entry
   
     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) >>> 1;　　Entry
    
      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
      entry = (Map.Entry
     )it.next();　　　　　　key = (K)entry.getKey();　　　　　　value = (V)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
     
       middle =  new Entry<>(key, value, null);　　// 若当前节点的深度=红色节点的深度，则将节点着色为红色。　　if (level == redLevel)　　　　middle.color = RED;　　// 设置middle为left的父亲，left为middle的左孩子　　if (left != null) {　　　　middle.left = left;　　　　left.parent = middle;　　}　　// 递归调用获取(middel的)右孩子　　if (mid < hi) {　　　　Entry
      
        right = buildFromSorted(level+1, mid+1, hi, redLevel, it, str, defaultVal);　　　　// 设置middle为left的父亲，left为middle的左孩子　　　　middle.right = right;　　　　right.parent = middle;　　}　　return middle;}

4. 带有SortedMap的构造函数。此构造函数参数是一个有序的Map

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

对于 TreeMap 而言，它采用一种被称为“红黑树”的排序二叉树来保存 Map 中每个 Entry —— 每个 Entry 都被当成“红黑树”的一个节点对待。

TreeMap中的红黑树算法实现

对于TreeMap而言，它采用红黑树来保存Map中的每个Entry，每个Entry都被当成红黑树的一个节点来对待。

Entry是在TreeMap中用于保存插入的键值对的内部数据结构，源码如下：

static final class Entry
   
     implements Map.Entry
    
      {        K key;        V value;        Entry
     
       left;        Entry
      
        right;        Entry
       
         parent;        boolean color = BLACK;      //...}

它总共包含了6部分内容：键（key），值（value），左孩子（left）和右孩子（right），父节点（parent）以及颜色。Entry节点根据Key进行排序。

相关操作

左旋操作：

private void rotateLeft(Entry
   
     p) { ... }

右旋操作：

private void rotateRight(Entry
   
     p) { ... }

插入操作：

public V put(K key, V value) { ... }

插入修正操作，当完成插入操作后，红黑树可能失去平衡，此时需要通过重新着色和其他操作对其进行调整：

private void fixAfterInsertion(Entry
   
     x) { ... }

删除操作：

private void deleteEntry(Entry
   
     p) { ... }

删除修正操作：

private void fixAfterDeletion(Entry
   
     x) { ... }

具体关于红黑树的调整操作可参见：http://www.cnblogs.com/tianex/p/5093350.html　

你可能感兴趣的文章