【Java Map】简述TreeSet

2021-12-15 12:08:20

一、引出正题

提出需求：
需要对一组数据进行排序，并剔除重复数据。

解决思路：
①：首先你可能会想到使用 List + Comparator，当然这是一种很普遍常用的实现方式。
②：然后在排序的同时剔除重复数据，那这时候你肯定会跟已有的节点做比较（循环比较，或者将节点存放在一个map中再通过containsKey()的方式比较）。

上述解决思路也挺好，那我们能不能换种思路呢？
当然，仔细思考一下，上述思路其实和Java中现有的 TreeSet 还挺像的，那我们何妨不直接拿来使用呢！

二、TreeSet登场

1. 示例

public class TreeSetDemo {
    public static void main(String[] args) {
        int[] nums = { 3, 2, 5, 1, 7, 0, 1 };
        TreeSet<Integer> treeSet = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            treeSet.add(nums[i]);
        }

        System.out.println(treeSet);
    }
}

执行结果：这不就是我们想要的嘛！

[0, 1, 2, 4, 6]

2. 原理分析

TreeSet类图

从类图中很直观的就可以看出，TreeSet 是一个支持排序（可以自定义实现排序算法，实现 Comparator）的集合。

TreeSet源码分析

TreeSet.java

添加元素动作

/**
* The backing map.
*/
private transient NavigableMap<E,Object> m;

// 添加元素
// 使用map那很容易的就能联想到不支持重复数据
public boolean add(E e) {
    return m.put(e, PRESENT)==null;	//真正实现在TreeMap中
}

TreeMap.java

判断是否第一次添加，第一次则初始化Entry节点；
非第一次添加则根据Comparator算法，循环比较其所在位置，并建立好左右节点关系；
非重复节点返回null，重复节点则返回虚拟对象（PRESENT）；

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {	// 第一次put操作
        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) {
        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);	// 循环比较排序
    }
    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);
    }
    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;
}

Entry的结构：

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;

    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}

三、总结

在Java世界中，已经封装了非常多非常完善的数据结构API，我们在使用的时候可以多思考，不要仅仅局限于只使用最常规的ArrayList、HashMap 这两个最最常见的API。

感谢阅读，下次再见。ヾ(￣▽￣)Bye_Bye！

码农公寓