源码解析java集合框架，TreeMap源码

你的名字 2022-02-26 00:08 432阅读 0赞

### 一、TreeMap剖析 ###

TreeMap是Map接口下一个实现类，基于键值对来存储每个数据，TreeMap是一个有序集合，顺序是key值的插入顺序，每个元素对象必须实现比较器，底层数据结构是一颗**红黑树**，之前在介绍HashMap时也有提到过红黑树，HashMap底层是数组链表红黑树，而TreeMap只包含红黑树一种数据结构类型。红黑树插入、检索、移除元素操作时间复杂度都是O(logn)，性能较高。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyODEyNDYyNDA_size_16_color_FFFFFF_t_70][] 红黑树，TreeMap数据结构

TreeMap树中每个节点都是一个Entry<K,V>对象，Entry是TreeMap类中的内部类，Entry包含的属性有键值K key，值V value，左子树Entry<K,V> left，右子树Entry<K,V> right，父节点Entry<K,V> parent，颜色属性boolean color。

![2019032911475861.png][] TreeMap节点Entry

### 二、源码解读 ###

**2.1 构造方法**

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

TreeMap构造方法只是对比较器comparator赋值，没有其他新建操作。

**2.2 TreeMap添加元素，put(k,v)方法**

public V put(K key, V value) {
            Entry<K,V> t = root; //根节点
            if (t == null) {  //如果根节点为空，则把当前数据放在根节点
                compare(key, key); // type (and possibly null) check
    
                root = new Entry<>(key, value, null); //新建Entry赋值给根root
                size = 1;
                modCount++;
                return null;
            }
            int cmp;
            Entry<K,V> parent;
            // split comparator and comparable paths
            Comparator<? super K> cpr = comparator; //外部比较器
            //如果存在外部比较器，就使用外部比较器比较key大小
            //确定存放位置在左子树、右子树还是覆盖根节点的值
            if (cpr != null) { 
                do { //迭代整个树
                    parent = t;
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0) //key小，放于左子树
                        t = t.left;
                    else if (cmp > 0) //key大，放于右子树
                        t = t.right;
                    else    //与根节点key值相等，则覆盖根节点value值
                        return t.setValue(value);
                } while (t != null);
            }
            else { 
                if (key == null)
                    throw new NullPointerException();
                @SuppressWarnings("unchecked")
                    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);
            }
    
            //比较完，找到要插入位置的parent
            Entry<K,V> e = new Entry<>(key, value, parent);
            if (cmp < 0) //放在parent的左子树
                parent.left = e;
            else    //放在parent的右子树
                parent.right = e;
    
            //修复，红黑树的左旋、右旋，保证树的平衡
            fixAfterInsertion(e);
            size++;
            modCount++;
            return null;
        }

TreeMap添加元素就是不断的比较key大小的过程，最终找到key相等或者相对应存放位置，红黑树添加元素后会有个自平衡的操作，利用左旋右旋来保持树的平衡。

**2.3 TreeMap获取元素，get(k)方法**

public V get(Object key) {
            Entry<K,V> p = getEntry(key);
            return (p==null ? null : p.value);
        }

final Entry<K,V> getEntry(Object key) {
          
            if (comparator != null)
                return getEntryUsingComparator(key);
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            Entry<K,V> p = root;
            while (p != null) {  //p为当前搜索的根节点，动态赋值
                int cmp = k.compareTo(p.key); 
                //传入key与当前根节点key对比，相等则当前根节点就为查询的数据
                //传入key小，则进入根的左子树，继续迭代
                //传入key大，则进入根的右子树，继续迭代
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
            return null; //迭代完，没有找到，返回空
        }

get(k)方法传入查询key参数，查找算法中使用key值与树中每个节点key对比，根据大小选择根节点、左子树、右子树。

**2.4 TreeMap移除元素，remove(k)方法**

public V remove(Object key) {
            Entry<K,V> p = getEntry(key); //根据key查找到节点
            if (p == null)
                return null;
    
            V oldValue = p.value;
            deleteEntry(p);    //从树中删除节点，树自平衡
            return oldValue;
        }

> TreeMap底层就是一颗红黑树，每个节点都是key-value键值对，检索、添加元素效率较高，且元素有保持有序，与HashMap相比，TreeMap性能稍微低一点，但HashMap元素无序。一般在需要排序的map中使用TreeMap。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyODEyNDYyNDA_size_16_color_FFFFFF_t_70]: /images/20220226/f8dd6f3259474cd5a35f34f6379e6e23.png
[2019032911475861.png]: /images/20220226/780450835b804b50a76b34dc3729c7cb.png