TreeMap及Set源码解析

2018-08-04 本文已影响28人某昆

1、本文主要内容

TreeMap及Set介绍
TreeMap源码解析
Set源码解析

2、TreeMap及Set介绍

首先我们查看Set接口，Set接口定义了add方法，remove方法，唯独没有定义get方法，用户是无法单独获取set的某元素，只能通过遍历获取。

Set是接口，本期主要讲述其中两个实现，HashSet以及TreeSet。顾名思义，HashSet使用哈希表存储元素，而TreeSet使用树结构存储元素。接下来的源码分析可以知道，HashSet利用了成员变量HashMap存储元素，而TreeSet使用成员变量TreeMap来存储元素，这也是本文要介绍TreeMap的原因。

TreeMap使用红黑树来存储元素，不过它实现的接口是Map，它存储的是键值对。

3、TreeMap源码解析

红黑树前期已有介绍，本文不再重复红黑树添加修复以及删除修复内容的介绍了，不过先回忆下红黑树的5大特性：

节点非黑即红
根节点为黑
叶结点（NIL结点，空结点）为黑
红色结点的子结点一定是黑色的，也就是说没有两个相连的红色结点
从根结点开始到每一个叶结点（NIL结点，空结点）之间的黑色结点数量相等

以上是红黑树的5大特性，依靠着上述特性，红黑树成为了相对平衡的二叉搜索树。

//put方法，存储元素
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
    //如果比较器不为null，则使用比较器来比较key之间的大小
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            //如果key小于当前节点key，则将当前节点置为它的左子节点，反之则右子节点
            //这是二叉搜索树的性质，左子节点小于父节点，父节点小于右子节点
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        //如果比较器为null，则将key转化为Comparable比较，逻辑同上一样
        if (key == null)
            throw new NullPointerException();
        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);
    }
    //此时找到的parent即是新节点的parent节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    //最后根据cmp的结果，确认新节点是左还是右子结点
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    //修复红黑树
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

put方法比较简单，结合二叉搜索树的性质，找到正确的位置，插入新节点即可。在红黑树中，为了尽量少违背那5条特性，一律将新插入的节点颜色置为红色，最后修复红黑树，使之仍然是一颗正常的红黑树，如何修复新增节点的红黑树，请参考以前写的红黑树一文。

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    //删除节点，所以size减一
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    //如果删除的节点左右子树都不为空，则需要找出中序遍历中的后续节代替当前节点
    //后继节点可以是左子树中的最大结点，也可以是右子树中的最小节点
    //最后删除后继节点
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    //经过上面的判断，此时p不可能左右子树都存在，将存在的其中一个或者空指针，替换要被删除的节点
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        //如果替换的节点不为空，则将替换节点代替p结点
        // Link replacement to parent
        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结点的关系斩断
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            //如果p结点是黑色的，现在删除p，性质5会违背，所以需要修复红黑树
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        //如果p没有父节点，则说明p结点为根结点，将root置空
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            //同理，p颜色为黑色，那么修复红黑树
            fixAfterDeletion(p);

        if (p.parent != null) {
            //p的替代节点为null，但父节点不为null的情况下，处理p父节点相关信息
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

删除节点比添加节点稍复杂一些，尤其需要理解后继节点的含义，在删除节点p时，并不是直接删除节点p，如果p的两个子节点都存在的情况下，需要找出中序遍历下的p的后继节点，用后继节点代替p节点，最后删除的其实是后续节点。因为后继节点肯定最多只有一个子节点，位于树的底层，更加好删除一些。但删除后红黑树的修复更加复杂了，情况更多了。

4、Set源码解析

Set是接口，本期主要讲两个实现类，HashSet和TreeSet，但阅读源码后才知道，这两个实现类超级简单，因为它们所有的逻辑都是基于自身的成员变量HashMap和TreeMap，存、删除等都是调用成员变量的实现。

另外Set存储的不是键值对，但它们的成员变量存储的都是键值对，这是因为Set只用到了key值，value是一个默认值。

下面看看HashSet的存储和删除：

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {
    return map.containsKey(o);
}

代码实在太简单了，就不再介绍了。现在来看看TreeSet的方法：

private transient NavigableMap<E,Object> m;
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
public TreeSet() {
    this(new TreeMap<E,Object>());
}

由上述方法可知，TreeSet中的成员变量其实是TreeMap。

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

添加和删除同HashSet一样。

那么HashSet和TreeSet之间有什么不同呢？TreeSet它是基于红黑树的，红黑树是二叉搜索树，如果采用中序遍历的话，它的key会从大到小按顺序排列，所以TreeSet它是有序的。

TreeMap及Set源码解析

猜你喜欢

热点阅读