排序的K-V结构实现 – TreeMap、TreeSet源码分析

@创建时间 2022年11月21日 23:34:48
@更新时间 2022年11月21日 23:34:48

综述

TreeMap、TreeSet集合类中的元素是有序存储的，底层数据结构是红黑树
TreeMap是覆盖式插入，相同Key值的(Key, Val)更新Val为最新值
TreeSet底层实现基于TreeMap

TreeMap

Constructor

默认空参构造函数，根据Key类型实现的Comparable.compareTo()升序排序

public TreeMap() {
    comparator = null;
}

指定排序的构造方法，使用指定的Comparator.compare()升序排序

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

put()方法

public V put(K key, V value) {
    Entry<K, V> t = root;
 
    // 首次添加设置为根节点
    if (t == null) {
        compare(key, key);
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
 
    int cmp;
    Entry<K, V> parent;
 
    // 1.1 按照构造函数指定的Key类型排序规则，依据BST性质找到插入位置
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            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);
    }
 
    // 1.2 默认构造函数未指定Key类型排序规则，指定排序规则使用Key类型默认规则，依据BST性质找到插入位置
    else {
        // * 空参构造函数不允许Key为null
        if (key == null) throw new NullPointerException();
        // 按照BST性质找到插入位置
        @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);
    }
 
    // 新建待插节点，插入到BST中，并进行平衡调整维护RBT性质
    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;
}

发表回复取消回复