java 集合源码探究之 treemap 如何保证有序，put过程， get过程。

TreeMap

PUT 过程

public V put(K key, V value) {
        // 目前的根节点
        Entry<K,V> t = root;
        // 第一次添加节点
        if (t == null) {
            // 检查类型和null值
            compare(key, key); // type (and possibly null) check
            // 新建一个  Entry节点, 作为 root 节点
            root = new Entry<>(key, value, null);
            // map中节点的数量
            size = 1;
            // 修改次数
            modCount++;
            return null;
        }
        // 往后都是 非首次添加节点了
        int cmp;
        Entry<K,V> parent;
        // tree map的比较器
        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 {
             //没有指定节点之间的比较器
            // 检查 key 是否 null值 
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            // 得到key的比较器
                Comparable<? super K> k = (Comparable<? super K>) key;
            // 进入循环,遍历整棵树, 寻找存放位置
            do {
                // 此时 t 为根节点
                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 的位置
        // 新建一个 Entry
        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;
        }
    }
           

调整树过程

fixAfterInsertion

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

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

GET过程

public V get(Object key) {
        // 得到节点
        Entry<K,V> p = getEntry(key);
        // 返回节点的 value 
        return (p==null ? null : p.value);
    }
           

getEntry(Object key)

final Entry<K,V> getEntry(Object key) {
        //  有指定的比较器的话, 就是用指定的比较器来获得元素
        if (comparator != null)
            return getEntryUsingComparator(key);
        // 抛出异常
        if (key == null)
            throw new NullPointerException();
        // 得到比较器
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        // p 是根节点
        Entry<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;
    }
           

getEntryUsingComparator(Object key)

final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        // 得到比较器
        Comparator<? super K> cpr = comparator;
        // 比较器不为空
        if (cpr != null) {
            // p 是根节点
            Entry<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;
    }
           

总结

• 是用树作为存储单位
  • 内部红黑树
• 是一个有序的map
• 可以指定元素的比较器
  • 也可以不指定