TreeMap源码分析

心已赠人 2023-01-17 10:58 145阅读 0赞

**阅读本文章之前需要了解Comparator接口及Comparable接口的基本使用，推荐先阅读博主关于红黑树的讲解文章，传送地址：[快速理解红黑树，从二叉排序树 → AVL树 → 红黑树的演变][_ AVL_ _]**

# TreeMap源码分析 #

### 文章目录 ###

*  TreeMap源码分析
 *   *  一、基本介绍
     *  二、源码分析
     *   *  1. 常见属性
         *  2. 内部类
         *  3. 构造方法
         *  4. get(Object key)方法
         *  5. put(K key, V value)方法
         *  6. 删除节点
         *  7. 总结

## 一、基本介绍 ##

*  TreeMap使用红黑树存储元素，可以保证元素按key值的大小进行排序
    
     *  TreeMap利用了红黑树左节点小，右节点大的性质，根据 key 进行排序，使每个元素能够插入到红黑树适当的位置，维护了 key 的大小关系，适用于 key 需要排序的场景
     *  因为底层使用的是红黑树，所以 TreeMap 中的 `containsKey、get、put、remove` 等方法的时间复杂度都是 log(n)
        
        ![image-20210427134033648][]
 *  继承体系
    
    ![image-20210427133500956][]
    
    TreeMap实现了Map、SortedMap、NavigableMap、Cloneable、Serializable等接口

## 二、源码分析 ##

### 1. 常见属性 ###

//比较器，如果外部有传进来Comparator比较器，首先用外部的
    //如果外部比较器为空，则使用key自己实现的Comparable接口重写的compareTo方法进行比较
    private final Comparator<? super K> comparator;
    
    //红黑树的根节点
    private transient Entry<K,V> root;
    
    //红黑树的已有元素个数
    private transient int size = 0;
    
    //树结构变化的版本号，用于迭代过程中的快速失败场景
    private transient int modCount = 0;

### 2. 内部类 ###

Entry表示红黑树的节点，典型的红黑树节点的结构

static final class Entry<K,V> implements Map.Entry<K,V> { 
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
        //省略其余
    }

### 3. 构造方法 ###

//空参构造器，要求key必须实现Comparable接口，否则无法排序，报错
    public TreeMap() { 
        comparator = null;
    }
    
    //使用传入的comparator比较器比较两个key的大小
    public TreeMap(Comparator<? super K> comparator) { 
        this.comparator = comparator;
    }
    
    //把参数Map中的所有元素保存到新的TreeMap中，要求key必须实现Comparable接口，否则无法排序，报错
    public TreeMap(Map<? extends K, ? extends V> m) { 
        comparator = null;
        putAll(m);
    }
    
    //把参数中的所有元素保存到新的TreeMap中，并使用SortedMap中指定的比较器
    public TreeMap(SortedMap<K, ? extends V> m) { 
        comparator = m.comparator();
        try { 
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException | ClassNotFoundException cannotHappen) { 
        }
    }

观察上述源码，可得出如下结论：

*  构造方法主要分成两类，一类是使用Comparator比较器，另一类是key必须实现Comparable接口
    
     *  如果以上两种情况都满足，优先使用外部的Comparator比较器

### 4. get(Object key)方法 ###

`get(Object key)` 方法源码如下：

public V get(Object key) { 
    
        //调用getEntry方法得到对应的节点
        Entry<K,V> p = getEntry(key);
        
        //找到了返回value值，没找到返回null
        return (p==null ? null : p.value);
    }

`getEntry(Object key)` 方法源码如下：

final Entry<K,V> getEntry(Object key) { 
        
        //如果构造器中传入了比较器，则使用指定的比较器进行比较
        if (comparator != null)
            return getEntryUsingComparator(key);
        
        //key为空，抛出空指针异常
        if (key == null)
            throw new NullPointerException();
       
        @SuppressWarnings("unchecked")
        
        //如果外部没有传递Comparator实例，将key强转为Comparable
        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; //没有找到则返回null
    }

`getEntryUsingComparator(Object key)` 方法源码如下：

过程与 `getEntry(Object key)` 方法类似，区别是使用 `comparator` 接口中的 `compare` 方法进行比较

final Entry<K,V> getEntryUsingComparator(Object key) { 
        @SuppressWarnings("unchecked")
        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); //根据comparator接口中的compare方法进行比较
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

根据上述源码，可以得到get元素时的过程如下：

*  从root遍历整个树
 *  如果待查找的key比当前遍历的key小，则在其左子树中查找
 *  如果待查找的key比当前遍历的key大，则在其右子树中查找
 *  如果待查找的key与当前遍历的key相等，则找到了该元素，直接返回
 *  如果遍历了整棵树也没有找到，则返回null

### 5. put(K key, V value)方法 ###

插入元素，如果元素在树中存在，则替换value；如果元素不存在，则插入到对应的位置，再平衡树

public V put(K key, V value) { 
        Entry<K,V> t = root;
    
        //如果没有根节点，新插入的元素成为根节点
        if (t == null) { 
            compare(key, key);
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
    
        int cmp; //记录比较的结果值，大于0，小于0，等于0三种情况
        Entry<K,V> parent; //待插入节点的父节点
    
        //根据是否传入comparator而使用不同的分支
        Comparator<? super K> cpr = comparator;
    
        //如果传入comparator比较器
        if (cpr != null) { 
    
            //从根节点开始遍历寻找
            do { 
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0) //如果小于0从左子树寻找
                    t = t.left;
                else if (cmp > 0)
                    t = t.right; //如果大于0从右子树寻找
                else
                    return t.setValue(value); //如果等于0，说明插入的节点已经存在了，直接更换其value值并返回旧值
            } while (t != null);
        }
    
        //如果没有传入comparator比较器
        else { 
            if (key == null)
                throw new NullPointerException(); //key为null抛出异常
    
            @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            do { 
    
                //从根节点开始遍历寻找
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0) //如果小于0从左子树寻找
                    t = t.left;
                else if (cmp > 0) //如果大于0从右子树寻找
                    t = t.right;
                else
                    return t.setValue(value); //如果等于0，说明插入的节点已经存在了，直接更换其value值并返回旧值
            } while (t != null);
        }
    
        //如果此节点在树中不存在，那么新建一个节点，并插入到树中
        //经过上述过程的遍历，parent已经成为了待插入节点的父节点
        Entry<K,V> e = new Entry<>(key, value, parent);
    
        if (cmp < 0) //如果小于0插入到左子节点
            parent.left = e;
        else // 如果大于0插入到右子节点
            parent.right = e; 
    
        //插入节点之后做变色 + 旋转的操作使树平衡
        fixAfterInsertion(e); 
    
        size++;
        modCount++;
    
        //如果插入了新节点，返回null
        return null;
    }

根据上述源码，可以得到如下结论：

*  新增节点时，利用了红黑树左小右大的特性，从根节点不断往下查找，直到找到节点是 null 为止，节点为 null 说明到达了叶子结点
 *  查找过程中，发现 key 值已经存在，直接覆盖并返回旧值；如果不存在，插入新节点到合适的位置，然后变色 + 旋转，返回null
 *  TreeMap 禁止 key 为 null 值

具体的平衡操作详见关于红黑树的博客 / 文档，传送地址：[快速理解红黑树，从二叉排序树 → AVL树 → 红黑树的演变][_ AVL_ _]

### 6. 删除节点 ###

红黑树节点的删除遵从二叉排序树的删除规则，具体过程详见关于二叉排序树的博客 / 文档，传送地址：[快速理解红黑树，从二叉排序树 → AVL树 → 红黑树的演变][_ AVL_ _]

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

### 7. 总结 ###

（1）TreeMap的存储结构只有一颗红黑树

（2）TreeMap中的元素是有序的，按key的顺序排列

（3）TreeMap比HashMap要慢一些，因为HashMap前面还做了一层桶，寻找元素要快很多

（4）TreeMap没有扩容的概念

[_ AVL_ _]: https://blog.csdn.net/weixin_49343190/article/details/107818395
[image-20210427134033648]: /images/20221021/d4a3de94085641a5a711f23c0879dc63.png
[image-20210427133500956]: /images/20221021/14ea3eed9fa8401f95e79b5035d85a40.png