剖析Java 集合框架(八)-TreeMap

作者: 李元霸抢貂蝉 | 来源:发表于2021-01-03 17:10 被阅读0次

前面介绍过ConcurrentSkipListMap,支持排序(基于跳表)，线程安全的Map。现在介绍一种同样支持排序，但是非线程安全，使用更频繁的类-TreeMap。

红黑树

TreeMap支持排序的原理在于底层使用红黑树，本篇不详细手撕红黑树，简易的分析下原理。

下面基于《算法 4》定义的红黑树的特点，

根节点必为黑色；
节点分为红色或者黑色；
连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
新加入到红黑树的节点为红色节点；

为保证每次操作之后，这些特性不变，需要维护该平衡，该算法的的核心操作如下:
下面就插入的几种情况画图分析：

变色：在不违反上述红黑树规则特点情况下，将红黑树某个 node 节点颜色由红变黑，或者由黑变红。
如果插入之后的父节点（10）和父节点同级的节点(20)都为红色，则将父级节点都变为黑的。父级节点的父级节点(19)变为红色，则以（19）节点为起点重新自平衡。
红黑树-插入-变色
如果插入节点为左节点，则进行右旋。右旋：顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点。
红黑树-插入-右旋

3.如果插入节点为右节点，则先对父级节点进行左旋，再对祖父节点进行右旋。左旋: 逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点。

红黑树-插入-左右旋

TreeMap 源码分析

一、TreeMap 数据结构

先看下 TreeMap 的定义

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap 继承了 AbstractMap，所以它是一个 Map，即一个 key-value 集合。并且它是一个有序的，通过 红黑树（R-B tree) 实现
TreeMap 实现了 NavigableMap 接口，意味着它一系列的导航定位以及导航操作的方法。
TreeMap 实现了 Cloneable 接口，可被克隆，实现了 Serializable 接口，可序列化。
再来看下 TreeMap 的主要成员

    // 比较器 用于保存map的排序，为空时 使用key的自然顺序排序
    private final Comparator<? super K> comparator;
   // 红黑树的 根节点
    private transient Entry<K,V> root;
   // 红黑树中 节点个数 容器大小 
    private transient int size = 0;
   // 红黑树 调整次数 快速失败(fail-fast) 关键
    private transient int modCount = 0;
   // 定义的红黑树的节点颜色-红色
    private static final boolean RED   = false;
   // 定义的红黑树的节点颜色-黑色
    private static final boolean BLACK = true;

Entry是个内部类

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;          // 当前节点的key
        V value;            // 当前节点的值
        Entry<K,V> left;        // 左子节点
        Entry<K,V> right;      // 右子节点
        Entry<K,V> parent;     // 父节点
        boolean color = BLACK; // 颜色

下面画下类图和数据结构图

TreeMap 类图

[图片上传失败...(image-fd9ac7-1609665042157)].png)

二、TreeMap 构造方法

TreeMap 有4个构造方法

// 默认构造方法， 按照 key 的自然顺序排序
    public TreeMap() {
        comparator = null;
    }

// 传入比较器的构造方法  按照该规则排序
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

//传入一个map对象创建TreeMap，按照key的自然顺序排序
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
// 遍历逐个插入
public void putAll(Map<? extends K, ? extends V> m) {
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
} 
// 传入一个按照特定方式排好序了的map，创建一个新的TreeMap, 线性时间
    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插入方法

插入是map的核心方法，TreeMap 的插入也就是向红黑树里面插入，大概分为两大步，1.插入新值，2.平衡红黑树。
先来看第一步 插入新值:

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 如果跟节点为空 新建个节点 并赋值给root
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }

    int cmp;
    // 插入新值的 父节点
    Entry<K,V> parent;
    // 区分比较器：是用自定义的  还是使用key自带的
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        // 使用二分法查找
        do {
            parent = t;
            // 使用自定义比较器 进行对比遍历到的key和新key
            cmp = cpr.compare(key, t.key);
            // 对比结果小于0  说明往左子树继续查找
            if (cmp < 0)
                // 将当前节点置为 左子节点
                t = t.left;
            // 大于0  说明需要往右子树继续查找
            else if (cmp > 0)
                // 将当前节点置为 右子节点
                t = t.right;
            else
                // 找到了 直接更新改节点的value
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        // 使用key的比较器 步骤同上
        @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);
    }
    // 说明上面没有找到 得需要插入一个新值
    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;
}

大概步骤如下：

根节点为空，则构建一个节点做完跟节点,并返回。
以根节点为起点，使用二分搜索法，找到一样的则替换值，并返回。
未找到则在正确位置的叶子节点插入子节点。
然后进行调整。

下面看下插入之后，自平衡红黑树：

private void fixAfterInsertion(Entry<K,V> x) {
    // 新节点 都是红色
    x.color = RED;

    //只有父级节点为红色时  才需要调整
    while (x != null && x != root && x.parent.color == RED) {
        // 如果父节点 是左节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 获取父节点的父节点的右子节点 如果也是红色 则执行变色操作
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                // 将父节点和叔父节点设置为黑色
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                // 将祖父节点 设置为 红色
                setColor(parentOf(parentOf(x)), RED);
                // 将祖父节点置为当前节点 继续循环调整
                x = parentOf(parentOf(x));
            } else {
                // 如果当前节点为右节点
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    // 先对父节点左旋
                    rotateLeft(x);
                }
                // 对祖父节点进行右旋
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        // 父节点 是右节点
        } else {
            // 父节点 和 叔父节点都是 红色  变色操作
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                // 如果是当前节点是左节点  现在对父节点 进行右旋转
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                // 对祖父节点 进行左旋
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    // 跟节点 黑色
    root.color = BLACK;
}

就是根据父节点，叔父节点，祖父节点的位置和颜色，然后变色，左旋，右旋操作。

四、 get方法

获取方法就跟二叉搜索树一样，二分法查找。

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

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;
    // 从root开始遍历查找
    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;
}

// 使用自定义的 比较器 也是使用而二分查找法
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);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

五、TreeMap的遍历

TreeMap提供多种遍历方法:map.values(), map.keySet()，map.entrySet()，map.forEach(),都挺简单的遍历，特别的是还提供逆序/方向遍历，刚兴趣的同学可以去了解下。

总结

本文简单介绍了TreeMap基本特点和几个方法，没有说到删除方法，很多情况需要考虑，打算放到算法分析红黑树的时候再细讲。有错误或者不清楚的地方还请评论指出。

量变引发质变，经常进步一点点，期待蜕变的自己。

剖析Java 集合框架(八)-TreeMap

红黑树

TreeMap 源码分析

一、TreeMap 数据结构

二、TreeMap 构造方法

三、 put插入方法

四、 get方法

五、TreeMap的遍历

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

剖析Java 集合框架(八)-TreeMap

红黑树

TreeMap 源码分析

一 、TreeMap 数据结构

二、TreeMap 构造方法

三、 put插入方法

四、 get方法

五、TreeMap的遍历

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

一、TreeMap 数据结构