TreeMap源码解析

作者: 103style | 来源:发表于2019-07-18 13:53 被阅读8次

转载请以链接形式标明出处：
本文出自:103style的博客

base on jdk_1.8.0_77

红黑树简介

红黑树就是一种平衡的二叉查找树，说他平衡的意思是他不会变成“瘸子”，左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外，还具体下列的特性：

节点是红色或者黑色
根节点是黑色
每个叶子的节点都是黑色的空节点（NULL）
每个红色节点的两个子节点都是黑色的。
从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

红黑树示例

TreeMap简介

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

TreeMap 是一个 有序的key-value集合，它是通过红黑树实现的。
TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。
TreeMap 实现了NavigableMap接口，意味着它 支持一系列的导航方法。比如返回有序的key集合。
TreeMap 实现了Cloneable接口，意味着 它能被克隆。
TreeMap 实现了java.io.Serializable接口，意味着 它支持序列化。

TreeMap基于红黑树 实现。该映射根据 其键的自然顺序进行排序，或者根据 创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n)。
另外，TreeMap是 非同步 的。它的iterator 方法返回的 迭代器是fail-fastl 的。

排序默认是升序的，数字比较大小，字符串比较首字母，其他类型则需要自己实现Comparable接口，否则排序时会报错。

测试代码：

public static void main(String[] args) {
    List<Integer> s = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        int t = (int) (Math.random() * 1000);
        s.add(t);
    }
    
    for (int i = 0; i < s.size(); i++) {
        System.out.print(s.get(i) + "----");
    }
    System.out.println();

    TreeMap<Integer, Integer> treeMap = new TreeMap<>();
    for (int i = 0; i < s.size(); i++) {
        treeMap.put(s.get(i), s.get(i));
    }

    Iterator<Map.Entry<Integer, Integer>> iterator = treeMap.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<Integer, Integer> next = iterator.next();
        System.out.println(next.getKey() + "--" + next.getValue());
    }
}

输出结果：

953----411----437----516----461----238----201----365----345----191----
191--191
201--201
238--238
345--345
365--365
411--411
437--437
461--461
516--516
953--953

数据类型修改为String之后输出结果为：

65----296----701----75----278----650----507----71----839----547----
278--278
296--296
507--507
547--547
65--65
650--650
701--701
71--71
75--75
839--839

TreeMap的成员变量介绍

private final Comparator<? super K> comparator;//key的比较器
private transient TreeMapEntry<K,V> root;//数的根节点
private transient int size = 0;//treemap节点的数量
private transient int modCount = 0;//树修改的次数
private transient EntrySet entrySet;//键值对集合
private transient KeySet<K> navigableKeySet;//键集合
private transient NavigableMap<K,V> descendingMap;//降序的NavigableMap

TreeMap的构造函数

TreeMap的构造函数主要是处理 key 的比较器。

public TreeMap() {
    comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}
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) {
    }
}

TreeMap相关的函数

public V get(Object key)
public Map.Entry<K,V> ceilingEntry(K key)
public Map.Entry<K,V> floorEntry(K key)
public Map.Entry<K,V> higherEntry(K key)
public Map.Entry<K,V> lowerEntry(K key)
public V put(K key, V value)
public V replace(K key, V value)
public V remove(Object key) 
public void clear()
public Map.Entry<K,V> firstEntry()
public Map.Entry<K,V> lastEntry()
private void rotateLeft(TreeMapEntry<K,V> p)
private void rotateRight(TreeMapEntry<K,V> p)
private void fixAfterInsertion(TreeMapEntry<K,V> x)
private void fixAfterDeletion(TreeMapEntry<K,V> x)

get(Object key) and getEntry(Object key)

从根节点开始，比较节点的目标的key的大小，

目标key>节点key：查找节点的右子树
目标key<节点key：查找节点的左子树
目标key=节点key：返回节点

当在没有设置comparator的时候，get方法的key = null会抛出NullPointerException.

public V get(Object key) {
    TreeMapEntry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}
final TreeMapEntry<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;
    TreeMapEntry<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 TreeMapEntry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        TreeMapEntry<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;
}

ceilingEntry(K key)

获取 大于等于 key的最小节点。当 key比树中最大的key大时返回null。

public Map.Entry<K,V> ceilingEntry(K key) {
    return exportEntry(getCeilingEntry(key));
}
final TreeMapEntry<K,V> getCeilingEntry(K key) {
    TreeMapEntry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) {
            if (p.right != null) {
                p = p.right;
            } else {
                TreeMapEntry<K,V> parent = p.parent;
                TreeMapEntry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}

floorEntry(K key)

获取 小于等于 key的最大节点。当 key比树中最小的key小时返回null。

public K floorKey(K key) {
    return keyOrNull(getFloorEntry(key));
}
final TreeMapEntry<K,V> getFloorEntry(K key) {
    TreeMapEntry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else if (cmp < 0) {
            if (p.left != null) {
                p = p.left;
            } else {
                TreeMapEntry<K,V> parent = p.parent;
                TreeMapEntry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;

    }
    return null;
}

higherEntry(K key)

获取大于 key的最小节点，不存在则返回 null

public K higherKey(K key) {
    return keyOrNull(getHigherEntry(key));
}
final TreeMapEntry<K,V> getHigherEntry(K key) {
    TreeMapEntry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                TreeMapEntry<K,V> parent = p.parent;
                TreeMapEntry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

lowerEntry(K key)

获取小于 key的最大节点，不存在则返回null.

public K lowerKey(K key) {
    return keyOrNull(getLowerEntry(key));
}
final TreeMapEntry<K,V> getLowerEntry(K key) {
    TreeMapEntry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else {
            if (p.left != null) {
                p = p.left;
            } else {
                TreeMapEntry<K,V> parent = p.parent;
                TreeMapEntry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

put(K key, V value)

如果树为null，则构建一个TreeMapEntry设置为当前的root.
检查之前TreeMap的comparator是否为空，不为空则用comparator去对比key,否则用k.compareTo(t.key)比较，然后遍历当前树，找到对应的key则修改对应的value。
如果遍历树没找到，则通过new TreeMapEntry<>(key, value, parent); 添加到树上，然后执行fixAfterInsertion(e)保证root还是一颗红黑树。fixAfterInsertion(e)下面会介绍。

红黑树执行插入操作之后，要执行“插入修正操作”。
目的是：保红黑树在进行插入节点之后，仍然是一颗红黑树

public V put(K key, V value) {
    TreeMapEntry<K, V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new TreeMapEntry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    TreeMapEntry<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);
    }
    TreeMapEntry<K, V> e = new TreeMapEntry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

replace(K key, V value)

通过getEntry(key)获取对应的节点，如果节点不为空，则更新值。

public V replace(K key, V value) {
    TreeMapEntry<K,V> p = getEntry(key);
    if (p!=null) {
        V oldValue = p.value;
        p.value = value;
        return oldValue;
    }
    return null;
}

remove(Object key)

通过getEntry(key)获取对应的节点，如果节点不为空，通过deleteEntry删除节点，并通过fixAfterDeletion(TreeMapEntry<K,V> x)重排树使之还是一颗红黑树。fixAfterDeletion下面会介绍。

红黑树执行删除之后，要执行“删除修正操作”。
目的是保证：红黑树删除节点之后，仍然是一颗红黑树

当p有左右子树的时候，successor(p)，及返回右子树上的最左边的树节点，即大于p的key的最小值。所以 replacement即为右子树上的最左边的树节点的右子树。否则 replacement即为p的左右子树中的一个。
然后根据 replacement 不为空、是否是根节点、为空且不是根节点 3种情况删除节点p.

public V remove(Object key) {
    TreeMapEntry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}
private void deleteEntry(TreeMapEntry<K, V> p) {
    modCount++;
    size--;
    if (p.left != null && p.right != null) {// p has 2 children
        TreeMapEntry<K, V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    TreeMapEntry<K, V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {
        // 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;

        p.left = p.right = p.parent = null;
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

clear()

置空root，修改 size 为 0.

public void clear() {
    modCount++;
    size = 0;
    root = null;
}

firstEntry()

返回最左端的节点的key-value构建的SimpleImmutableEntry

public Map.Entry<K, V> firstEntry() {
    return exportEntry(getFirstEntry());
}
final TreeMapEntry<K, V> getFirstEntry() {
    TreeMapEntry<K, V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}
static <K, V> Map.Entry<K, V> exportEntry(TreeMapEntry<K, V> e) {
    return (e == null) ? null :
            new AbstractMap.SimpleImmutableEntry<>(e);
}

lastEntry()

返回最右端的节点的key-value构建的SimpleImmutableEntry

public Map.Entry<K,V> lastEntry() {
    return exportEntry(getLastEntry());
}
final TreeMapEntry<K,V> getLastEntry() {
    TreeMapEntry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}
static <K, V> Map.Entry<K, V> exportEntry(TreeMapEntry<K, V> e) {
    return (e == null) ? null :
            new AbstractMap.SimpleImmutableEntry<>(e);
}

rotateLeft(TreeMapEntry<K,V> p)

红黑树的左旋

p 相当与上图的X.

private void rotateLeft(TreeMapEntry<K,V> p) {
    if (p != null) {
        TreeMapEntry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

rotateRight(TreeMapEntry<K,V> p)

红黑树的右旋

p 相当与上图的X.

private void rotateRight(TreeMapEntry<K,V> p) {
    if (p != null) {
        TreeMapEntry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

fixAfterInsertion(TreeMapEntry<K,V> x)

插入的节点，默认设置为红树。当x.parent.color == RED时，则需要进行旋转知道满足红黑树的条件。旋转的过程可以参考链接中的示例。

private void fixAfterInsertion(TreeMapEntry<K, V> x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            TreeMapEntry<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 {
            TreeMapEntry<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;
}

fixAfterDeletion(TreeMapEntry<K,V> x)

删除的节点只有是 黑树 时，才需要进行旋转重新满足红黑树的条件。旋转的过程可以参考链接中的示例。

private void fixAfterDeletion(TreeMapEntry<K, V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            TreeMapEntry<K, V> sib = rightOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(sib)) == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // symmetric
            TreeMapEntry<K, V> sib = leftOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }
            if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }

    setColor(x, BLACK);
}

小结

TreeMap是有序的key-value集合。
HashMap不保证数据有序，LinkedHashMap保证数据可以保持插入顺序，而TreeMap可以保持key的大小顺序的时候。

参考文章

以上