08-TreeMap 核心源码解析(集合)

注:源码系列文章主要是对某付费专栏的总结记录。如有侵权,请联系删除。

1 知识储备

在了解 TreeMap 之前,我们来看看日常工作中排序的两种方式,作为我们学习的基础储备,两种方式的代码如下:

@Data
class Entry implements Comparable<Entry> {
    private final Integer id;

    Entry(Integer id) {
        this.id = id;
    }

    @Override
    public int compareTo(Entry o) {
        // 默认从小到大排序
        return id - o.id;
    }
}

@Test
public void execute() {
    // 第一种排序,从小到大排序,实现  Comparable 的 compareTo 方法进行排序
    List<Entry> list1 = new ArrayList<>();
    for (int i = 5; i > 0; i--) {
        list1.add(new Entry(i));
    }
    Collections.sort(list1);
    System.out.println("list1: " + JSON.toJSONString(list1));

    // 第二种排序,从大到小排序,利用外部排序器 Comparator 进行排序
    List<Entry> list2 = new ArrayList<>();
    for (int i = 5; i > 0; i--) {
        list2.add(new Entry(i));
    }
    Collections.sort(list2, new Comparator<Entry>() {
        @Override
        public int compare(Entry o1, Entry o2) {
            return o2.id - o1.id;
        }
    });
    System.out.println("list2: " + JSON.toJSONString(list2));
}

执行结果:

list1: [{"id":1},{"id":2},{"id":3},{"id":4},{"id":5}]
list2: [{"id":5},{"id":4},{"id":3},{"id":2},{"id":1}]

以上两种就是分别通过 Comparable 和 Comparator 两者进行排序的方式,而 TreeMap 利用的也是此原理,从而实现了对 key 的排序。

2 TreeMap 整理架构

TreeMap 底层的数据结构就是红黑树,和 HashMap 的红黑树结构一样。

不同的是,TreeMap 可利用了红黑树左节点小,右节点大的性能,根据 key 进行排序,使每个元素都能够插入到红黑树大小适当的位置,维护了 key 的大小关系,适用于 key 需要排序的场景。

因为底层使用的是平衡红黑树的结构,所以 containsKey、get、put、remove 等方法的时间复杂度都是 log(n)。

2.1 属性

TreeMap 常见的属性有:

// 比较器。
// 如果外部有传进来 Comparator 比较器,则用外部的
// 如果外部比较器为空,则使用 key 自己实现的 Comparable#compareTof 方法
private final Comparator<? super K> comparator;

// 红黑树的根节点
private transient Entry<K,V> root;

// 红黑树已有元素大小
private transient int size = 0;

// 树结构变化的版本号
private transient int modCount = 0;

// Red-black mechanics
private static final boolean RED   = false;
private static final boolean BLACK = true;
// 红黑树的节点
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;

    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}

2.2 新增节点

TreeMap 新增节点源码:

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);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        // 自旋找到 key 应该新增的位置,就是应该挂载到哪个节点的子节点上
        do {
            // 一次循环结束时,parent 就是上次比过的对象
            parent = t;
            // 通过 compare 来比较 key  和当前对比节点 t 的大小
            cmp = cpr.compare(key, t.key);
            // key 小于 t,把 t 左边的节点赋值给 t,因为红黑树左边的值比较小,循环再比
            if (cmp < 0)
                t = t.left;
            // key 大于 t,把 t 右边的节点赋值给 t,因为红黑树右边的值比较小,循环再比
            else if (cmp > 0)
                t = t.right;
            // 如果相等则表示当前节点 t 和要新增的节点相同,直接赋值当前节点 t 的值即可
            else
                return t.setValue(value);
        // t 为空说明已经到叶子节点了
        } 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);
    }
    // 到这一步时已经找到了当前要新增节点 key 的父节点 parent 了
    Entry<K,V> e = new Entry<>(key, value, parent);
    // cmp 代表最后一次对比的大小,小于 0,代表 e 在上一个节点的左边
    if (cmp < 0)
        parent.left = e;
    // cmp 代表左后一次对比的大小,大于 0,代表 e 在上一个节点的右边
    else
        parent.right = e;
    // 相等的情况上面寻找 parent 时已经做过了

    // 着色旋转,达到平衡
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

从源码中,我们可以看到:

  1. 新增节点时,就是利用了红黑树左小右大的特性,从根节点不断往下查找,直到找到节点是 null 为止,节点为 null 说明到达了叶子节点;
  2. 查找的过程中,发现 key 值已经存在,直接覆盖值;
  3. TreeMap 是禁止 key 是 null 值的。

类似的,TreeMap 查找也是类似的原理。

2.3 小结

TreeMap 相对来说比较简单,红黑树和 HashMap 比较类似,比较关键的是通过 compare 来比较 key 的大小,然后利用红黑树左小右大的特性,为每个 key 找到自己的位置,从而维护了 key 的大小排序顺序。

------------------------------------- END -------------------------------------

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,686评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,668评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,160评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,736评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,847评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,043评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,129评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,872评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,318评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,645评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,777评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,470评论 4 333
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,126评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,861评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,095评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,589评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,687评论 2 351

推荐阅读更多精彩内容