TreeMap 原理与源码解析

1、原理

2、源码解析

2.1、构造方法

//空参的构造方法，比较器设为空
public TreeMap() {
    comparator = null;
}

2.2、put 方法

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        //放入Map的为第一个元素，为红黑树的跟节点
        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;
            //使用比较器对key进行比较，沿左右子树向下查询，相同的则匹配掉值
            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;
}

2.3、get 方法

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}
//获取Entry数组
final Entry<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;
    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;
}

2.4、containsKey 方法

//判断根据key能否获取到Entry对象
public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

2.5、containsValue 方法

public boolean containsValue(Object value) {
    //从跟节点递归循环遍历，判断值是否相同
    for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
        if (valEquals(value, e.value))
            return true;
    return false;
}
//获取红黑树的跟节点，沿左分支查找最终的叶子节点
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    //没有了左子节点，但是却有右子节点
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    //t没有右子结点
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        //t有右边的兄弟
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

2.6、remove 方法

public V remove(Object key) {
    //根据key获取到Entry数组
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;
    V oldValue = p.value;
    //删除要删除的Entry数组
    deleteEntry(p);
    return oldValue;
}
//等待仔细分析，红黑树操作
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    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.
    //替换指针
    Entry<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;
        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;
        // Fix replacement
        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;
        }
    }
}

2.7、replace 方法

public V replace(K key, V value) {
    //根据key获取指定Entry数组
    Entry<K,V> p = getEntry(key);
    //值替换
    if (p!=null) {
        V oldValue = p.value;
        p.value = value;
        return oldValue;
    }
    return null;
}