类前注释

      基于红黑树的NavigableMap实现。Map的key根据自然排序或在创建时提供的Comparator对key进行排序。
      TreeMap为containsKey，get，code put和remove操作保证了log(n)时间成本。算法是对Cormen，eiserson和Rivest的算法简介中的算法的改编。
      注意，此实现不是同步的。 如果多个线程同时访问一个地图，并且至少所述修改的线程中的一个的映射结构，它必须保持外部同步。(结构上的修改是指添加或删除一个或多个映射的操作;仅改变与现有键关联的值是不是结构修改)。这通常是通过一些对象上同步自然封装该地图来实现的。 如果该对象不存在时，地图应当"包装"使用Collections.synchronizedSortedMap方法。 这最好在创建时完成，以防止对映射进行意外的不同步访问：

     SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

      在返回的迭代器iterator的所有此类的"collection方法"返回集合的方法是快速失败的：如果集合随时修改创建迭代器之后，以任何方式除非通过迭代器自身的remove方法，迭代器将抛出ConcurrentModificationException。 因此，在并发的修改时，迭代器很快就会失败，而不是在将来不确定的时间发生不确定性的行为。
      注请注意，不能保证迭代器的快速失败行为。通常来说，在存在不同步的并发修改的情况下，不可能做出任何严格的保证。 快速迭代器会尽最大努力抛出ConcurrentModificationException，因此，编写依赖于此异常的程序的正确性是错误的：迭代器的快速故障行为仅应用于检测错误。

类图

成员变量

/**
 * 我们前面提到TreeMap是可以自动排序的，默认情况下comparator为null，这个时候按照key的自然顺序进行排
 * 序，然而并不是所有情况下都可以直接使用key的自然顺序，有时候我们想让Map的自动排序按照我们自己的规则，
 * 这个时候你就需要传递Comparator的实现类
 */
private final Comparator<? super K> comparator;

/**
 * TreeMap的存储结构既然是红黑树，那么必然会有唯一的根节点。
 */
private transient Entry<K,V> root;

/**
 * Map中key-val对的数量，也即是红黑树中节点Entry的数量
 */
private transient int size = 0;

/**
 * 红黑树结构的调整次数
 */
private transient int modCount = 0;

private static final boolean RED   = false;
private static final boolean BLACK = true;

      TreeMap中的每个节点定义如下所示：

static final class Entry<K,V> implements Map.Entry<K,V> {
    //key,val是存储的原始数据
    K key;
    V value;
    //定义了节点的左孩子
    Entry<K,V> left;
    //定义了节点的右孩子
    Entry<K,V> right;
    //通过该节点可以反过来往上找到自己的父亲
    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;
    }

    /**
     * 获取节点的key值
     */
    public K getKey() {return key;}

    /**
     * 获取节点的value值
     */
    public V getValue() {return value;}

    /**
     * 用新值替换当前值，并返回当前值
     */
    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;
    }
}

构造方法

/**
 * 构造一个新的，空的TreeMap，使用键的自然顺序。 
 * 插入到TreeMap中的所有Key都必须实现Comparable接口。
 * 另外，所有这些Key必须是可比较的:任何在地图上的键k1和k2，k1.compareTo(k2)不得抛出ClassCastException。
 */
public TreeMap() {
    comparator = null;
}
/**
 * 构造一个新的，空的TreeMap，传递自定义比较器。 
 */
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

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

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

put

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        //第一次put元素，root为空，创建根节点
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    /**
     * 如果节点不为null,定义一个cmp，这个变量用来进行查找时的比较；
     */
    int cmp;
    //定义parent，是new Entry时必须要的参数
    Entry<K,V> parent;
    //cpr表示有无自己定义的排序规则，分两种情况遍历执行
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            /**
             * 从root节点开始遍历，通过逐步向下找
             * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
             * cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么
             * 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key,
             * 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key，
             * 那么直接更新root节点的value值即可。
             * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
             *
             * 需要注意的是：这里并没有对key是否为null进行判断，建议自己的实现Comparator时应该要考虑在内
             */
            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 {
        //默认排序时TreeMap不支持key为NULL
        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);
    }
    /**
     * 执行到这里，说明前面并没有找到相同的key,节点已经遍历到最后了，我们只需要new一个Entry放到
     * parent下面即可，但放到左子节点上还是右子节点上，就需要按照cmp来。
     */
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    /**
     * 一般情况下加入节点都会对红黑树的结构造成
     * 破坏，需要通过一些操作来进行自动平衡处置，如【变色】【左旋】【右旋】
     */
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

get

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

/**
 * 从root节点开始遍历，通逐步向下找
 * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过k.compareTo(p.key)比较传入的key和
 * 根节点的key值；
 * 如果传入的key<root.key, 那么继续在root的左子树中找，从root的左孩子节点（root.left）开始；
 * 如果传入的key>root.key, 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;
 * 如果恰好key==root.key，那么直接返回root节点即可。
 * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
 */
final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    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) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

remove

public V remove(Object key) {
    //找到待删除节点
    Entry<K,V> p = getEntry(key);
    //不存在对应节点直接返回null
    if (p == null)
        return null;
    //保存旧值供后续返回
    V oldValue = p.value;
    //删除节点
    deleteEntry(p);
    return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // 当左右子节点都不为null时，通过successor(p)遍历红黑树找到前驱或者后继
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        //将前驱或者后继的key和value复制到当前节点p中，然后删除节点s(通过将节点p引用指向s)
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    /**
     * 至少有一个子节点不为null，直接用这个有值的节点替换掉当前节点，给replacement的parent属性赋值,给
     * parent节点的left属性和right属性赋值，同时要记住叶子节点必须为null,然后用fixAfterDeletion方法
     * 进行自平衡处理
     */
    if (replacement != null) {
        //将待删除节点的子节点挂到待删除节点的父节点上。
        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;

        /**
         * p如果是红色节点的话，那么其子节点replacement必然为红色的，并不影响红黑树的结构
         * 但如果p为黑色节点的话，那么其父节点以及子节点都可能是红色的，那么很明显可能会存在红色相连的情
         * 况，因此需要进行自平衡的调整
         */
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else {
        /**
         * 如果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的遍历可以使用map.values(), map.keySet()，map.entrySet()，map.forEach().

public static void main(String[] args) {
    TreeMap<Integer,Integer> map = new TreeMap<>();
    map.put(1,1);
    map.put(3,3);
    map.put(2,2);
    map.put(5,5);
    map.put(4,4);

    Collection<Integer> values = map.values();
    values.forEach((m)-> System.out.print(m+" "));
    System.out.println();

    Set<Integer> keys = map.keySet();
    keys.forEach((k)-> System.out.print("key="+k+", v="+map.get(k)));

    Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
    System.out.println();
    for (Map.Entry<Integer, Integer> entry : entries) {
        System.out.println(entry.getKey()+"  "+entry.getValue());
    }
    System.out.println();
    map.forEach((k,v)-> System.out.print("key="+k+", v="+map.get(k)));
}

      如果我们想逆序遍历则可以调用descendingMap方法.

map.descendingMap().forEach((k,v)-> System.out.println(k+" "+v));//逆序打印
System.out.println(map.lastEntry().getKey());//获取最大值(即最后一个entry)

版权属于：带翅膀的猫

本文链接：https://www.chengpengper.cn/archives/116/

转载时须注明出处及本声明