1、概述

当我们需要把插入的元素进行排序的时候，就需要使用的TreeMap。从名字我们可以看出TreeMap的实现肯定和树这种数据结构有关，当然TreeMap的实现是基于红黑树的。

2、示例

package com.liutao.collection;import java.util.Map;import java.util.TreeMap;/** * @Author:LIUTAO * @Description: * @Date:Created in 16:24 2018/5/6 * @Modified By: */public class TreeMapDemo {    public static void main(String[] args) {        Map
   
     maps = new TreeMap
    
     ();        maps.put(2, "aa");        maps.put(1, "cc");        maps.put(4, "bb");        for (Map.Entry
     
       entry : maps.entrySet()) {            System.out.println(entry.getKey() + " : " + entry.getValue());        }    }}

输出结果如下

1 : cc2 : aa4 : bb

我们可以砍价输出结果根据key进行了排序。

3、数据结构

红黑树的数据结构比较高效。

4、源码分析

4.1、类的继承关系

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

继承了抽象类AbstractMap，AbstractMap实现了Map接口，实现了部分方法。不能进行实例化，实现了NavigableMap,Cloneable,Serializable接口，其中NavigableMap是继承自SortedMap的接口，定义了一系列规范。

4.2内部类

static final class Entry
   
     implements Map.Entry
    
      {        K key;        V value;        Entry
     
       left;        Entry
      
        right;        Entry
       
         parent;        boolean color = BLACK;        //根据key、value、父节点初始化一个节点        Entry(K key, V value, Entry
        
          parent) { this.key = key; this.value = value; this.parent = parent; } /** * Returns the key. * * @return the key */ public K getKey() { return key; } /** * Returns the value associated with the key. * * @return the value associated with the key */ public V getValue() { return value; } /** * Replaces the value currently associated with the key with the given * value. * * @return the value associated with the key before this method was * called */ public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } public boolean equals(Object o) { 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() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } public String toString() { return key + "=" + value; } }

4.3、类的属性

public class TreeMap
   
        extends AbstractMap
    
         implements NavigableMap
     
      , Cloneable, java.io.Serializable{    // 比较器，用于控制Map中的元素顺序    private final Comparator
       comparator;    // 根节点    private transient Entry
      
        root;    // 树中结点个数    private transient int size = 0;    // 对树进行结构性修改的次数    private transient int modCount = 0;}

我们可以看出上面比较重要的一个属性就是比较器，这个比较器决定了如何对TreeMap中的键进行排序。

4.4、构造函数

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

从上面我们可以看出所有的构造器最终都是是否设置比较器并且是否向Map中添加初始元素。

4.5、核心函数分析

4.5.1、put函数

public V put(K key, V value) {        // 记录根节点        Entry
   
     t = root;        // 根节点为空        if (t == null) {            // 比较key            compare(key, key);             // 新生根节点            root = new Entry<>(key, value, null);            // 大小加1            size = 1;            // 修改次数加1            modCount++;            return null;        }        int cmp;        Entry
    
      parent;        // 获取比较器        Comparator
      cpr = comparator;        // 比较器不为空        if (cpr != null) {            // 找到元素合适的插入位置，如果找到插入位置，就说明位置之前存在元素，所以就直接替换。            do {                // parent赋值，赋值为根节点                parent = t;                // 比较key与元素的key值，在Comparator类的compare方法中可以实现我们自己的比较逻辑                cmp = cpr.compare(key, t.key);                // 小于结点key值，向左子树查找                if (cmp < 0)                    t = t.left;                // 大于结点key值，向右子树查找                else if (cmp > 0)                    t = t.right;                // 表示相等，直接更新结点的值                else                    return t.setValue(value);            } while (t != null);        }        // 比较器为空        else {            // key为空，抛出异常            if (key == null)                throw new NullPointerException();            @SuppressWarnings("unchecked")                // 取得K实现的比较器                Comparable
      k = (Comparable
     ) 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);        }        // 新生一个结点        Entry
     
       e = new Entry<>(key, value, parent);        // 根据比较结果决定存为左结点或右结点        if (cmp < 0)            parent.left = e;        else            parent.right = e;        // 插入后进行修正        fixAfterInsertion(e);        // 大小加1        size++;        // 进行了结构性修改        modCount++;        return null;    }

我们可以看见，当根节点为空的时候，就将当前节点设置成根节点。当根节点不为空的时候，就需要使用比较器来比较当前需要插入节点的key值与从根节点开始遍历的key值的大小，如果大就放右边，如果小就放左边。当然如果存在，那么就直接替换。

4.5.2、getEntry函数

final Entry
   
     getEntry(Object key) {        // 判断比较器是否为空        if (comparator != null)            // 根据自定义的比较器来返回结果            return getEntryUsingComparator(key);        // 比较器为空        // key为空，抛出异常        if (key == null)            throw new NullPointerException();        @SuppressWarnings("unchecked")            // 取得K自身实现了比较接口            Comparable
     k = (Comparable
    ) key;        Entry
    
      p = root;        // 根据Comparable接口的compareTo函数来查找元素        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;    }

从上面我们依然可以看出其实对于getEntry函数最终也要依靠比较器来决定到底是往左还是往右寻找，当比较的结果为0的时候就表明已经找到元素，直接返回。

4.5.3、deleteEntry函数

private void deleteEntry(Entry
   
     p) {        // 结构性修改        modCount++;        // 大小减1        size--;        // p的左右子结点均不为空        if (p.left != null && p.right != null) {            // 找到p结点的后继            Entry
    
      s = successor(p);            // 将p的值用其后继结点的key-value替换，并且用s指向其后继            p.key = s.key;            p.value = s.value;            p = s;        }         // 保持红黑树的特性，提高性能        Entry
     
       replacement = (p.left != null ? p.left : p.right);        if (replacement != null) {            // Link replacement to parent            replacement.parent = p.parent;            if (p.parent == null)                root = replacement;            else if (p == p.parent.left)                p.parent.left  = replacement;            else                p.parent.right = replacement;            // Null out links so they are OK to use by fixAfterDeletion.            p.left = p.right = p.parent = null;            // Fix replacement            if (p.color == BLACK)                fixAfterDeletion(replacement);        } else if (p.parent == null) { // return if we are the only node.            root = null;        } else { //  No children. Use self as phantom replacement and unlink.            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;            }        }    }

deleteEntry函数会在remove函数中被调用，它完成了移除元素的主要工作，删除该结点后会对红黑树进行修正，同时，在此函数中需要调用successor函数，即找到该结点的后继结点。具体函数代码如下　

// 找到后继    static 
   
     TreeMap.Entry
    
      successor(Entry
     
       t) {        // t为null，直接返回null        if (t == null)            return null;        // 右孩子不为空        else if (t.right != null) {            // 找到右孩子的最底层的左孩子，返回            Entry
      
        p = t.right;            while (p.left != null)                p = p.left;            return p;        } else { // 右孩子为空            // 保存t的父节点            Entry
       
         p = t.parent;            // 保存t结点            Entry
        
          ch = t; // 进行回溯，找到后继，直到p == null || ch != p.right while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }

当结点的右子树为空的时候，进行回溯可以找到该结点的后继结点。

那么在这个地方我们就有个疑问了，如何找到小于指定节点的最大节点？参考getLowerEntry函数源码

final Entry
   
     getLowerEntry(K key) {        // 保存根节点        Entry
    
      p = root;        // 根节点不为空        while (p != null) {            // 比较该key与节点的key            int cmp = compare(key, p.key);            if (cmp > 0) { // 如果该key大于结点的key                // 如果结点的右子树不为空，与该结点右结点进行比较                if (p.right != null)                    p = p.right;                else // 右子树为空，则直接返回结点；因为此时已经没有比该结点key更大的结点了(右子树为空)                    return p;            } else { // 如果该key小于等于结点的key                // 结点的左子树不为空，与该结点的左结点进行比较                if (p.left != null) {                     p = p.left;                } else { // 结点的左子树不为空，则开始进行回溯                    Entry
     
       parent = p.parent;                    Entry
      
        ch = p;                    while (parent != null && ch == parent.left) {                        ch = parent;                        parent = parent.parent;                    }                    return parent;                }            }        }        return null;    }

5、总结

可以看出TreeMap的实现最终是依靠红黑树的数据结构，针对红黑树这中数据结构还需要进一步学习。

6、参考

你可能感兴趣的文章